Chapter 04 : 图论模型¶
图¶
-
图是一个有序二元组 \(G=(V,E)\)，其中 \(V\) 是顶点（Vertex）集合，\(E\) 是边（Edge）的集合。\(E\) 中每条边 \(e\) 与 \(V\) 中两个顶点关联（Incident）。
- 若与边关联的两个顶点有序，则称图为有向图（Digraph），否则称为无向图
- 图可以用以点表示顶点，以曲线段表示边的图形来表示，但图与图形表示（Diagrammatic Representation）中点和曲线段在图形中的相对位置无关
-
度：无向图 \(G\) 中与顶点 \(v\) 关联的边的数目称为 \(v\) 的度，记为 \(d(v)\) 或 \(deg_G(v)\)
- 图的所有顶点的度的最大值与最小值分别称为最大度和最小度， 记为 \(\Delta(G)\) 和 \(\delta(G)\)
- （握手定理）所有顶点的度之和等于边数的两倍，即 \(\sum\limits_{v\in V}d(v)=2|E|\)
-
子图
- 图 \(G'=(V',E')\) 称为图 \(G=(V,E)\) 的一个子图（Subgraph），若 \(V'\subseteq V,E'\subseteq E\)，且 \(G'\) 中边的关联关系在 \(G'\) 中保持不变
- 生成子图：\(V'=V\)
- 导出子图：\(G(V'),G\textbackslash V',G(E'),G\textbackslash E'\)
- 图 \(G'=(V',E')\) 称为图 \(G=(V,E)\) 的一个子图（Subgraph），若 \(V'\subseteq V,E'\subseteq E\)，且 \(G'\) 中边的关联关系在 \(G'\) 中保持不变
-
树
- 连通的无圈图称为树（Tree）
简单图¶
两端点相同的边称为环（Loop），两端点分别相同的多条边称为平行边（Parallel Edges）
既没有环，也没有平行边的图称为简单图（Simple Graph）。不是简单图的图称为多重图（Multigraph）
- 完全图
- 任何两个不同顶点之间都有边相连的简单图称为完全图（Complete Graph）
- \(n\) 个顶点的完全图记为 \(K_n\)， \(K_n\) 的边数为 \(\frac{n(n−1)}{2}\)
- 简单图的顶点数与边数
- 若 \(G=(V,E)\) 为简单图，则边数的上下界为 \(|V|−1\leq |E|\leq\frac{|V|(|V|−1)}{2}\)
- 边数接近上界的称为稠密图（Dense Graph），边数远离上界的称为稀疏图（Sparse Graph）
路¶
- 顶点和边交替出现的序列 \(v_{i_0}e_{i_1}v_{i_1}e_{i_2}...e_{i_k}v_{i_k}\)，且序列中与每条边相邻的两个顶点为该边的两个端点，称为连接顶点 \(v_{i_0}\) 和 \(v_{i_k}\) 的途径（Walk）
- 若图为简单图，可省略途径中边的符号
- 经过边互不相同的途径称为迹（Trail）
- 起点和终点相同的迹称为闭迹
- 经过顶点互不相同的途径称为路（Path）
- 起点和终点相同，其余顶点互不相同，也不与起点和终点相同的途径称为圈（Cycle）
- 边赋权图中一条路所含边的权之和称为它的长度
二部图与连通¶
- 二部图
- 若图的顶点集可以划分为两个非空集合 \(X\) 和 \(Y\)，使得图中任一条边的两个端点分属 \(X,Y\) 两个集合，则称该图为二部图（Bipartite Graph），记为 \(G=(X\bigcup Y,E)\)
- \(X\) 中所有顶点与 \(Y\) 中所有顶点都有边相连的二部图称为完全二部图
- \(G\) 是二部图当且仅当 \(G\) 中不存在奇圈
- 若图的顶点集可以划分为两个非空集合 \(X\) 和 \(Y\)，使得图中任一条边的两个端点分属 \(X,Y\) 两个集合，则称该图为二部图（Bipartite Graph），记为 \(G=(X\bigcup Y,E)\)
- 连通
- 若无向图中两顶点 \(u,v\) 之间有路相连，则称 \(u,v\) 连通（Connected）
- 无向图中任意两顶点均连通的图称为连通图（Connect Graph）
