Skip to content

图

:material-circle-edit-outline: 约 1868 个字 :material-clock-time-two-outline: 预计阅读时间 6 分钟

无序偶我们用的是花括号（就是集合），有序偶用的小括号，序偶默认都是有序偶

图的分类

无向图

  • simple graph 简单图：不同结点才有边，且只能有一条边
  • multigraph 多图：不同结点之间可以有多条边，被称为平行边
  • pseudograph 伪图：结点自己可以有边（loop）

有向图允许自己loop自己

  • directed graph ：不允许有平行边，注意有向边平行得方向一致
  • directed multigraph ：允许有平行边

总结，只有简单图和有向图两点之间最多只能一条边，只有前两个无向图不能有loop

还有其它的

  • subgraph 子图
  • spanning subgraph 生成子图：结点不变，边是子集
  • 简单图的 union ：边和点各自并

图的术语

无向图

  • adjacent/neighbor 点与点相邻，两个结点相邻表示他们之间有条边
  • incident with 点与边关联，边与其两端结点有关联，端点又叫 \(endpoint\)
  • degree 度数，一个结点的度数即其有的边
    • \(deg_{isolated\;vertex}=0\)，孤立点
    • \(deg_{pendant\;vertex}=1\)，悬挂点

无向图有个握手定理，就是所有顶点度数和等于边数的两倍

有向图

adjacent ：要求是起点与终点相邻，终点被起点相邻，有方向

image-20240606183536612

度也分 in-degree 入度 \(deg^-v\) 和 out-degree 出度 \(deg^+v\)

有向图也有个握手定理，就是所有顶点的两个度各自的和相等，且等于边数

特殊的图

完全图：无向简单图，已经无法增加任何边了，用 \(K_n\) 表示

image-20240606183749939

轮子，每个结点都是2度

image-20240607111310600

轮图是圆图基础上，有且只有一个顶点与cycle的所有顶点相连

image-20240607111336850

\(n\) 维立方体，我们知道二维立方体就行了，超立方体没学过

image-20240607114900075

两部图，结点分为两部分，所有边都是跨越这两个部分的，同一部分的顶点之间不存在边

image-20240607115421361

\(C_6\) 两个三角形顶点分别为一组即可

只要图里面含有奇数长度的回路，肯定不是两部图

完全的两部图叫完全两部图，记为 \(K_{m,n}\)，\(m\) 和 \(n\) 为两部分各自的度

image-20240607115740161

显然左边是 \(W_4\) ，右边是 \(K_6\)

图的表示与同构（isomorphism）

adjacency matrix 邻接矩阵，简单图必是 0-1对称矩阵，对角全0，度数=行/列之和

多图和伪图就不是0-1矩阵了，数字表示相连的边数

incidence matrix 关联矩阵，从 点x点 的方阵变成 点x边 的矩阵

一个边只 incidence with 一个点，或者说列向量只有一个1，那就是一个 loop

一列只有两个1，平行边对应相同的列向量

image-20240607122716663

两个图，结点一样多，边一样多，如果能找出一个结点对到结点对的双射，且任意边映射过去还是一样的，那这两个图就是同构的

这个 bijection 双射也叫同构映射 isomorphism

image-20240607123033186

连通性概念

无向图

image-20240607161429695

不简单就是有重复点的，多提一嘴，无向图用 \(f(e_1)=\{x_0,x_1\}\) 来描述边

无向图里面，任意两个结点都有道路，这个图就是连通的 （connected）

定理：连通无向图的任意两个顶点必定存在简单道路

有向图用 \(f(e_1)=(x_0,x_1)\) 来描述边，有向图的 circuit 就是起点与终点一致

在连通的有向图里，任意两顶点都有来回的两条道路就是强连通，否则就是弱连通

注意这两个概念的前提是连通图，有孤立点的图谈不上强弱连通

不连通 cut

不连通的图可以拆分为多个连通的子图，这些子图叫做 connected components

一个连通图里，那些只要被拿走就会产生 connected components 的顶点叫 cut vertices，边则叫做 cut edge / bridge，他们的消失导致连通性下降

image-20240607162314471

连通性计算

求两个顶点之间长度为 \(r\) 的道路的数量，算矩阵 \(A^r\)

无向图的连通性，只需要算 \(\Sigma A^i\) ，看对角线之外是否全部非0，有一个为0就说明不连通

有向图不用管

欧拉图

欧拉回路是一个包含图中所有边的简单回路，欧拉道路是一个包含所有边的简单道路

欧拉图是存在欧拉回路的图

能一笔画回到起点的就是欧拉图

欧拉图的充分必要条件：是连通图，且每个顶点都是偶数度

只有欧拉道路、没有欧拉回路的图的充要条件：奇数度的结点有且只有两个

哈密尔顿

哈密尔顿没有充要条件

哈密尔顿道路是一个访问了所有结点且均只访问一遍的道路，同理有哈密尔顿回路

一个存在 Hamilton 回路的连通图叫 Hamilton 图

n>3 时，\(K_n\) 必是哈密尔顿图

Hamilton 图的充分条件：

  1. 一个顶点数 \(n\ge3\) 简单连通图，每一个顶点的度 \(\ge n/2\)，则这个图是哈密尔顿图
  2. 一个有 \(n\) 个结点的简单图，如果任意一对节点的度数之和 \(\ge n\)，则这个图是哈密尔顿图

最短路径问题

加权图 （weighted graph） 每条边都有个权重，道路长度为权重和

dijkstra算法

  1. 首先将起点距离设置为0，其它为无穷，表示这些点在考虑范围之外/没有与起点相连，将起点加入解集
  2. 每轮先更新各点到起点的最短距离距离 \(L_k(a,v)\)，找出距离最小的点，需要判断原最短路和找出的点的距离哪个更小，取小值作为新最短路
  3. 迭代到包含终点为止

image-20240616150443925

平面图

如果一个图画在平面上，有办法不出现交叉的边，那就是是 planar graph，这么画的图叫原来的图的 planar representation，平面表示

image-20240616152022987

前两个是，\(Q\) 都是平面图，只需要放大其中一面，其它塞进去就行

33两部图不是

一个平面表示可以分为多个区域 region ，分为有界无界两种，无界就是外部包含无穷远的区域

欧拉公式

一个连通平面简单图，有 \(e\) 条边，\(v\) 个顶点，\(r\) 个 region，那么有欧拉公式： \(v-e+r=2\)

不是平面图就没有区域概念，更没有欧拉公式

推论 corollary

  1. 一个连通平面简单图，有 \(e\) 条边，\(v\ge 3\) 个顶点，则有 \(e\le3v-6\)
  2. 一个连通平面简单图，有 \(e\) 条边，\(v\ge 3\) 个顶点，没有长度为3的回路，则则有 \(e\le2v-4\)

区域的度即区域边界有几条边，所有区域度数之和等于 \(2e\)

有界区域需要至少4条边才能维持

图的着色

用最少的颜色，让任意相邻的区域颜色不同

可以转化为图的问题，每个区域看成点，相邻的区域画个边，变成了点的着色

这个新的图叫原来的平面图的对偶图（dual graph），最少的顶点颜色数量叫这个图的 chromatic number

四色理论：平面图的 chromatic number 不大于4

\(K_n\) 显然需要 \(n\) ，\(K_{m,n}\) 一定是 2，\(C_n\) 的 \(n\) 偶数时只需要2，奇数需要3