我的书签
添加书签
移除书签Knowledge Point - 知识要点
图
图 G = \lt V,E \gt 是由顶点集合 V 和边集合 E 组成的数据结构。一个边为连接两个顶点的曲线，若两个顶点 u 和 v 为一条边的两个端点，则称 u 和 v 相邻。
子图（Subgraph）
一个所有顶点和边都属于图 G 的图，称为 G 的子图。
完全图（Complete Graph）
所有顶点两两相邻的图称为完全图。
无向边
若无向边 e 的两端点是 u 和 v ，则可以从 u 出发到达 v ，也可以从 v 出发到达 u 。
有向边
若有向边 e 从 u 指向 v ，则只能从 u 出发到达 v ，而不能反向。无向边也可以看作相同两个端点之间的两条反向有向边的叠加。
出度
节点 u 的出度是从节点 u 出发的边的数量，也称为出度度数，从节点 u 出发的边也称为出弧边。对于无向边和无向图来说，节点 u 的所有边都可以看作出弧边，即边数等于出度。
入度
节点 u 的入度是到达节点 u 的边的数量，也称为入度度数，到达节点 u 的边也称为入弧边。对于无向边和无向图来说，节点 u 的所有边也都可以看作入弧边，即边数等于入度。无向图中每个节点的出度和入度相等。
度数
图 G 中的节点 u 所关联的边数，称作该节点的度数。无向图的任意节点 v_i 的度数等于出度度数，也等于入度度数。有向图的任意节点 v_i 的度数等于出度度数与入度度数之和。
上面两个图中，图 A 为有向图，节点 0 - 6 的出度分别为 2, 2, 1, 1, 2, 1 ，入度分别为 1, 1, 2, 2, 0, 2 。图 B 为无向图，节点 0 - 6 的出度分别为 3, 4, 3, 3, 2, 3 ，入度与出度一样。
n \times n 的矩阵 g 可以表示一个拥有 n 个节点的图，节点下标范围为 [1,n] 。 g[i,j] 表示从节点 i 到 j 的距离（ i,j \in [1,n] ），也可以是其他信息，比如节点 i 是否可以直接到达节点 j 等等。无向图中相连的两个节点，可以看作有向图中两个节点之间有权值相等，方向相反的两条边。图 A 和 B 可以表示为：
A =
\begin{bmatrix}
0{0,0} & 1{0,1} & 0{0,2} & 0{0,3} & 0{0,4} & 1{0,5} \
0{1,0} & 0{1,1} & 1{1,2} & 1{1,3} & 0{1,4} & 0{1,5} \
0{2,0} & 0{2,1} & 0{2,2} & 0{2,3} & 0{2,4} & 1{2,5} \
0{3,0} & 0{3,1} & 1{3,2} & 0{3,3} & 0{3,4} & 0{3,5} \
1{4,0} & 0{4,1} & 0{4,2} & 1{4,3} & 0{4,4} & 0{4,5} \
0{5,0} & 1{5,1} & 0{5,2} & 0{5,3} & 0{5,4} & 0{5,5}
\end{bmatrix}
\quad
B =
\begin{bmatrix}
0{0,0} & 1{0,1} & 0{0,2} & 0{0,3} & 1{0,4} & 1{0,5} \
1{1,0} & 0{1,1} & 1{1,2} & 1{1,3} & 0{1,4} & 0{1,5} \
0{2,0} & 1{2,1} & 0{2,2} & 1{2,3} & 0{2,4} & 1{2,5} \
0{3,0} & 1{3,1} & 1{3,2} & 0{3,3} & 1{3,4} & 0{3,5} \
1{4,0} & 0{4,1} & 0{4,2} & 1{4,3} & 0{4,4} & 0{4,5} \
1{5,0} & 1{5,1} & 1{5,2} & 0{5,3} & 0{5,4} & 0{5,5}
\end{bmatrix}
环
若图 G 中存在一个节点 i ，从它出发可以返回自己，则称这条路径为一个环。不存在环的图称为无环图。下图是一个五向有环图：
拓扑排序
不存在环的有向图中存在拓扑排序。在可以拓扑排序的有向图 G 中，节点可以分为三类：起点，终点和中间点。起点只有出弧边，没有入弧边；终点只有入弧边，没有出弧边；中间点既有出弧边也有入弧边。下图是一个有向无环图的拓扑排序：
欧拉路径（Eulerian Path）
图 G 中存在这样的一条路径，经过每条边一次且仅一次（同一个顶点可以经过多次），可以遍历图中的所有边，则这条路径称为欧拉路经。有向图 DG 中存在一个起始顶点 v1 满足 degree{out} = degree{in} + 1 （出度比入度大1），存在一个终止顶点 v_2 满足 degree{in} = degree_{out} + 1 （入度比出度大1），其余所有顶点的入度等于出度，则该有向图 DG 中存在欧拉路经。无向图 UG 中存在两个顶点 v_1 和 v_2 满足度数为奇数，其余节点的度数都是偶数，则该无向图 UG 中存在欧拉路经。
欧拉回路（Eulerian Cycle）
若图 G 中存在欧拉路经，且该路径为一个回路，则称该路径为欧拉回路。有向图 DG 的任意顶点 vi 满足 degree{in} = degree_{out} ，出度等于入度，则该有向图 DG 中存在欧拉回路。无向图 UG 的任意顶点 v_i 满足读数为偶数，则该无向图 DG 中存在欧拉回路。
欧拉图（Eulerian Diagram）
拥有欧拉回路的图 G 称为欧拉图。
汉密尔顿路径（Hamilton Path）
图 G 中存在这样的一条路径，经过每个顶点一次且仅一次（同一条边可以经过多次），可以遍历图中的所有顶点，则这条路径称为汉密尔顿路径。求解汉密尔顿路径是一个NP完全问题。
汉密尔顿回路（Hamilton Cycle）
图 G 中存在汉密尔顿路径，且该路径为一个回路，则称该路径为汉密尔顿回路。
汉密尔顿图（Hamilton Diagram）
拥有汉密尔顿回路的图 G 称为汉密尔顿图。完全图必然是汉密尔顿图。
