图论基础概念
图
- 图是一个集族
G=\{V,E\} ,其中V 为点集,E 为边集。
点与点集
-
-
点可能有各种各样的信息,统称为点权。
-
一般用
u,v 表示点,w 表示点权。
边与边集
-
-
边可能有各种各样的信息,统称为边权。
-
边分为有向边和无向边。
-
一般用
e 表示边,s,t 分别表示起点/终点,l 表示边权。
点与边
-
度数
-
与一个点相连的边数称为点的度数。
-
形式化表述:
deg_u=\sum\limits_{e\in E}[e.s=u \text{ or } e.t=u] 。 -
图论基本定理(握手定理):
\sum\limits_{u\in V}deg_u=2|E| 。- 推论:任意图中,度数为奇数的点一定有偶数个。
-
有向图中,从
u 出发的边数为u 的出度,到u 截止的边数为u 的入度。
-
-
相邻
-
如果
u,v 之间有边,则称u,v 相邻。 -
形式化表述:如果
\exists e_{u,v} ,则u,v 相邻。 -
邻域
- 与
u 相邻的所有点的集合称为u 的邻域。
- 与
-
简单图
-
重边
- 若
\exists e_{u,v}=e_{u,v}'\in E ,则称它们为(一组)重边。一组重边的个数可能远多于2 。
- 若
-
自环
- 若
e_{u,v} 中u=v ,则其为一个自环。
- 若
-
简单图
- 不含重边和自环的图。
途径(walk),迹(trail)与路径(path)
-
途径(walk)
-
途径是连接一连串点的边的序列,即是一个有序的边集。
-
形式化地说,一条有限途径是一个边的序列
e_1,e_2,\dots,e_k ,使得存在一个点的序列v_1,v_2,\dots v_{k+1},\text{s.t.}e_i=(v_i,v_{i+1}) 。
-
-
迹(trail)
-
如果一条途径中的边两两不同,则它是一条迹。
-
形式化表述:一条迹是一个
\forall i\neq j,e_i\neq e_j 的途径。
-
-
路径(path)(又称简单路径(simple path))
-
如果一条迹中的点两两不同,则它是一条路径。
-
形式化表述:一条路径是一条
\forall i\neq j,v_i\neq v_j 的迹。
-
-
回路(circuit)
-
如果一条迹中的点首尾相同,则它是一个回路。
-
形式化表述:一条回路是一条
v_1=v_{k+1} 的迹。
-
-
环/圈(cycle)(又称简单回路/简单环(simple circuit))
-
如果一个回路中的点只有首尾相同,则它是一个环。
-
形式化表述:一个环是一条除了
v_1=v_{k+1} 外,\forall i\neq j,v_i\neq v_j 的回路。
-