词汇
英文试卷,实在头大。
infinite graph:无限图
finite graph:有限图
simple graph:简单图
multiple edge:多重边
multigraph:多重图
pseudograph:伪图
undirected graph:无向图
directed graph:有向图
multiplicity:重数
Acquaintanceship Graph:表示人认识关系的无向图
Friendship Graph:同 Acquaintanceship Graph
Influence Graph:表示人相互影响的有向图
Collaboration Graph:表示协作关系的简单无向图
Call Graph:调用图,属于有向图。
Web Graph:属于有向图。
Citation Graph:引用图,有向,无多重边和圈。
underlying undirected graph:基本无向图,把有向图的方向忽略得到的图。
complete graph:完全图
cycle:圈图
wheel:轮图
n-cube:立方图
bipartite:二分图
complete bipartite graph:完全二分图
subgraph:子图
proper subgraph:真子图
subgraph induced:导出子图
edge contraction:通过合并点来构造新的图
基础概念
图(Graph):顶点(Vertex)加上顶点之间的连线(边(Edge))。
记作: $G = (V,E)$ 。顶点记作: $G(V)$,边记作 $G(E)$ 。
无限图:顶点或边有无数条
多重边:如果 $V_1\to V_2$ 有两条边,则是多重边。注意,下面这种情况不算多重边:
多重图: 有 多重边 的图。
重数:两结点间平行边的条数称为平行边的重数。
伪图: 有环或者多重边的图
上面的圈圈叫做环。
有向图:
简单图:没有 环 和 多重边 的图。
简单有向图:没有 环 和 多重边 的有向图。
邻接、相邻:一条边的两个顶点相邻。
邻居:与 $v$ 相邻的所有点的集合。记作 $N(A)$
度:进出 $v$ 的边数。比如环对度数的贡献是 2. 普通边的贡献是 1. (注意:无向图的边的度数贡献是 1,而不是当作双向的2)
孤立顶点:度数 0 的顶点。
悬挂顶点:度数 1 的顶点。
入度:进入顶点的边数。记作 $\operatorname{deg}^- (v)$ 。
出度:离开顶点的边数。记作 $\operatorname{deg}^+ (v)$ 。
完全图(Complete graph):任意对不同顶点都相连的简单无向图。根据顶点的个数 $k$ 记作 $K_n$ 。
圈图(Circle graph):自己看图就懂了:
记作 $C_n$ 。
轮图(Wheel graph):中间带个轴心。
记作 $W_n$
立方图(Cubic graph):
记作 $Q_n$
二分图(Bipartite graph):说白了就是能构成映射的图。
- 判断二分图的方法
完全二分图:
设 $G(V,E)$ 为某一图。
子图:节点集和边集分别是 $G$ 节点集的子集 和 边集的子集的图。
生成子图:含有 $G$ 所有顶点的子图。
导出子图:也称顶点导出的子图。给一组顶点,与这些顶点所带的边构成的图。
假设 $G$ 为:
则顶点 e, c, b 的导出子图是:(不一定刚好构成路径哈,下面只是巧合)
主子图:
匹配问题:
两个二分图的可能连线情况如下:
匹配:一个连线方式是上面的所有连线可能性的子集,每个顶点都直连向一个对面的顶点,则这种连接方式是一个匹配。
最大匹配:连接的边数最大的那种匹配。
完全匹配:连接刚好构成一一对应(双射)的匹配。
霍尔定理:记 $N(A)$ 是 A 的所有邻居。存在 $V_1 \to V_2$ 完全匹配的充要条件是:对于所有 $V_1$ 的子集, $\left| N(A) \right| \leqslant \left| A \right|$
邻接表:一种通过每个顶点的邻居的图表示法。
邻接矩阵:类似关系矩阵。 $a_{ij} = 1$ 表示 $v_i \to v_j$ 的边存在。
关联矩阵:通过顶点和边的连接关系矩阵来描述无向图。
图的同构:如果两个图能扭成一个模样就是同构。严谨点说是存在 $G_1 \to G_2$的映射 $f$ 使得顶点映射过去后,边的连接关系不变。
通路:经过一系列顶点的边的序列。
连通图和不连通图:看下面的图就懂了:
连通分支:看下面的图就懂了:
割点:如果一个顶点连同它的相关边删除掉,会产生更多连通分支,这个点就是割点。
比如这个 $c$ 点。
不可分割图:没有割点的图。
连通度:最少删除 $k$ 个割点能变成不连通图,那么这个图连通度是 $k$ 。
割边:如果一个边被删除之后,会产生更多连通分支,那么这个边就是割边。
边连通度:同理。
强连通:有向图任意 $a,b$ 两点均有 $a\to b, b\to a$ 的通路,则该图是强连通的。
弱连通:有向图去掉方向之后任意 $a,b$ 两点均存在通路,则是弱连通的。
强连通分支:有向图的极大强连通子图。
欧拉回路问题:能否从一个顶点出发,沿着图的边前进,恰好经过图的每条边一次并且回到出发点?
欧拉回路定理:连通多重图中存在欧拉回路当且仅当图中所有顶点的度数为偶数。
哈密顿回路问题:能否从一个顶点出发,沿着图的边前进,恰好经过图的每个顶点一次并且回到出发点?
加权图:给每条边赋予权重(例如表示距离)的图。
最短通路算法:就是寻找开销最小的路径的算法。(开销用权重之和表示)
- Dijkstra 算法
- Floyd 算法
- A* 算法
平面图:如果一个图存在一种表示形式使得其可以铺平后没有交叉,则是平面图。
平面图欧拉公式:设平面图 G,有 $e$ 条边,$v$ 个顶点,则 $v+r = e+2$。面数等于边数减顶点数加二。推荐阅读:经典证明:不用数学归纳法直接推导平面图的Euler公式。记忆的话可以用三角形这个特例,两面三点三边。
面的度:面的边界上的边数。
$e\leqslant 3v -6\ (v\geqslant 3)$
初等细分:通俗地说就是在平面图的某一条边上加个起到分割作用的顶点。
同胚:若 $G_1$,初等细分得到 $G_2,G_3$,则 $G_1, G_2, G_3$ 是同胚的。
库拉图斯基定理:一个图是非平面图 $\Leftrightarrow$ 它包含一个同胚于 $K_{3,3}$ 或 $K_5$ 的子图。(注:$K_5$ 是5阶完全图,$K_{3,3}$ 是各三个顶点的二部图)。
图着色:给每个顶点指定一种颜色,使得任意相邻顶点的颜色不同。
图着色数:给图着色所需的最少颜色数。记作 $\chi(G)$。
四色定理:平面图的着色数不超过 4.
- 完全二分图的着色数是 2.
常用算法
判断二分图
着色法:只用两种颜色,能否保证给所有点染色时,任何相邻两个点的颜色不同,可以的就是二分图。染色可以用广度优先和深度优先两种顺序。(原理:完全二分图的着色数是 2.)
Dijkstra 寻路算法的工作原理
详见此文。一句话解释就是:找到与起点相邻最近点,再把这个点与源点看做一个整体,作为新的起点,重复步骤,直到抵达目标。
Floyd 算法的工作原理
一句话解释就是:先用一个邻接矩阵,只存放相邻点的数据。不相邻的点记为 $\infty$。然后分别地使用各个点 $P_i$ 建立 $P_i$ 相邻点之间的线索,直到所有点完成这样的操作。可参考此文。
TSP(行商)问题
问题描述可直接看此处。
可以尝试写一点代码,有助于加深理解。
我学图论的时候太注重证明和各种定理了,导致算法功底没跟上。
关键还是要练。
谢谢前辈的建议,感觉平时时间太紧迫了,假期一定专门刷一刷相关的算法题。