图的基本概念

定义部分

图

• 无序积 :$A \& B=\{\{a,b\}|a\in A,b\in B\}$

• 无向图 :$G=<V,E>$

• 有向边:$D=<V,E>$ -$E$是笛卡尔积$V\times V$的有穷多重子集

  • 无相图为相应有向图的基图
  • 后继元集$\Gamma_D^+(v)=\{u|u\in V,<v,u>\in E,u\not= v\}$
  • 先驱元集$\Gamma_D^-(v)=\{u|u\in V,<u,v>\in E,u\not=v\}$
  • 邻域$N_D(v)=\Gamma_D^+\cup\Gamma_D^-$
  • 闭邻域$\bar{N}_D(v)=N_D\cup\{v\}$

• 如果一对关联顶点的无向边数或者方向相同的有向边数多于1，那么称这些边为平行边 ，平行边的条数称为重数，含平行边的图称为多重图,否则为简单图

• 子图、母图、真子图、生成子图:设$G=\langle V, E\rangle, G'=\langle V', E'\rangle$为两个图（同为无向图或同为有向图），若$V' \subseteq V$且$E' \subseteq E$，则称 $G'$ 为 $G$ 的子图，$G$ 为 $G'$ 的母图，记作$G' \subseteq G$。又若$V' \subset V$或$E' \subset E$，则称子图 $G'$ 为 $G$ 的真子图。若$V' = V$，则称子图 $G'$ 为 $G$ 的生成子图。

• 设$G=\langle V, E\rangle, V_1 \subseteq V$且$V_1 \neq \varnothing$，称以 $V_1$ 为顶点集，以 $G$ 中两个端点都在 $V_1$ 中的边组成边集 $E_1$ 的图为 $G$ 的 $V_1$ 导出的子图，记作$G[V_1]$。又设$E_1 \subseteq E$且$E_1 \neq \varnothing$，称以 $E_1$ 为边集，以 $E_1$ 中边关联的顶点为顶点集 $V_1$ 的图为 $G$ 的 $E_1$ 导出的子图，记作$G[E_1]$。

  • 导出子图（Induced Subgraph）是图论中的一个重要概念，指的是从原图中选择部分顶点，并保留这些顶点之间在原图中的所有边所形成的子图。其核心特点是：​边完全由顶点的选择决定，不能随意增减。

• 删除:$G-e,G-E',G-v,G-V'$

• 收缩:设$e=(u,v)\in G$,用$G\backslash e$表示去掉e后，用w代替两个端点$u,v$

• 设$G_1,G_2$为两个图：

  • 并图:$G_1\cup G_2$
  • 差图:以$E_1-E_2$为边集，$E_1- E_2$中关联的顶点组成的集合为顶点集的图为交图，记作$G_1- G_2$
  • 交图:以$E_1\cap E_2$为边集，$E_1\cap E_2$中关联的顶点组成的集合为顶点集的图为交图，记作$G_1\cap G_2$
  • 环和::以$E_1\oplus E_2$为边集，$E_1\oplus E_2$中关联的顶点组成的集合为顶点集的图为交图，记作$G_1\oplus G_2$

度数、通路与回路

• 度：$v$作为边的端点的次数,记为$d_G(v)$
• 入度、出度:在有向图$D$中，$d_D^+(v),d_D^-(v)$
• 最大度、最小度:$\Delta(G)=max\{d(v)|v\in V(G)\}$ $\delta(G)=min\{d(v)\}$
• 另外，称度数为 1 的顶点为悬挂顶点，与它关联的边称作悬挂边。度为奇数的顶点称作奇度顶点，度为偶数的顶点称作偶度顶点。
• 设$G = \langle V, E \rangle$为一个$n$阶无向图，$V = \{v_1, v_2, \cdots, v_n\}$，称$d(v_1), d(v_2), \cdots, d(v_n)$为$G$的度数列。对于顶点标定的无向图，它的度数列是唯一的。反之，对于给定的非负整数列$d = (d_1, d_2, \cdots, d_n)$，若存在以$V = \{v_1, v_2, \cdots, v_n\}$为顶点集的$n$阶无向图$G$，使得$d(v_i) = d_i$，$i = 1, 2, \cdots, n$，则称$d$是可图化的。特别地，若得到的图是简单图，则称$d$是可简单图化的。对有向图还可以类似定义出度列和入度列。
• 同构:设$G_1 = \langle V_1, E_1 \rangle$和$G_2 = \langle V_2, E_2 \rangle$是两个无向图，若存在双射函数$f: V_1 \rightarrow V_2$，使得$\forall v_i, v_j \in V_1$，$(v_i, v_j) \in E_1$当且仅当$(f(v_i), f(v_j)) \in E_2$，并且$(v_i, v_j)$与$(f(v_i), f(v_j))$的重数相同，则称$G_1$与$G_2$同构，记作$G_1 \simeq G_2$。对有向图，可类似定义同构，即要求双射函数$f: V_1 \rightarrow V_2$，使得$\forall v_i, v_j \in V_1$，$\langle v_i, v_j \rangle \in E_1$当且仅当$\langle f(v_i), f(v_j) \rangle \in E_2$，且$\langle v_i, v_j \rangle$与$\langle f(v_i), f(v_j) \rangle$的重数相同。
• 彼得森图
• n阶完全图:$K_n$中$n\ge 1$,每个顶点都与其余的n-1个顶点相邻
  • 设$D$为$n$阶有向简单图，若$D$中每个顶点都邻接到其余的$n-1$个顶点，则称$D$为 $n$阶有向完全图。
  • 设$D$为$n$阶有向简单图，若$D$的基图为$n$阶无向完全图$K_n$，则称$D$为 $n$阶竞赛图。
  • 易知，n 阶无向完全图、n 阶有向完全图、n 阶竞赛图的边数分别为$\frac{n(n-1)}{2}$,$n(n-1)$,$\frac{n(n-1)}{2}$
• k-正则图:设$G$为n阶无向简单图，若$\forall v\in V(G)$，均有$d(v)=k$,则称G为
• 补图:设$G = \langle V, E \rangle$为$n$阶无向简单图，令$\overline{E} = \{(u, v) \mid u, v \in V, u \neq v, (u, v) \notin E\}$，称$\overline{G} = \langle V, \overline{E} \rangle$为$G$的补图。若图$G \cong \overline{G}$，则称$G$为自补图。
• 路：设$G = \langle V, E \rangle$为无向标定图。 -$G$中顶点与边的交替序列$\Gamma = v_{i_0}e_{j_1}v_{i_1}e_{j_2}\cdots e_{j_l}v_{i_l}$称作从$v_{i_0}$到$v_{i_l}$的通路，其中$v_{i_{r-1}}, v_{i_r}$为$e_{j_r}$的端点，$r = 1, 2, \cdots, l$。顶点$v_{i_0}, v_{i_l}$分别称为$\Gamma$的始点和终点，$\Gamma$中边的条数称作它的长度。 - 若又有$v_{i_0} = v_{i_l}$，则称$\Gamma$为回路。 - 若$\Gamma$的所有边互不相同，则称$\Gamma$为简单通路。 - 若又有$v_{i_0} = v_{i_l}$，则称$\Gamma$为简单回路。 - 若所有顶点（除$v_{i_0}$与$v_{i_l}$可能相同以外）互不相同，所有边也互不相同，则称$\Gamma$为初级通路或路径。 - 若又有$v_{i_0} = v_{i_l}$，则称$\Gamma$为初级回路或圈。将长度为奇数的圈称作奇圈，长度为偶数的圈称作偶圈。
  • 另外，若$\Gamma$中有边重复出现，则称为复杂通路或复杂回路

图的连通性

• ​连通分支：无向图$G = (V, E)$的连通分支是顶点集$V$关于连通关系$\sim$的一个等价类$V_i$，其导出子图$G[V_i]$称为一个连通分支。

• ​连通分支数：记作$p(G)$，满足：

  • 若$G$为连通图，则$p(G) = 1$
  • 若$G$为非连通图，则$p(G) \geq 2$

• ​极值性质：在所有$n$阶无向图中，n阶零图$N_n$的连通分支数最大，即$p(N_n) = n$。

• ​距离$d(u, v)$：对无向图$G$中任意两顶点$u, v$：

  • 若$u \sim v$，则$d(u, v)$为$u, v$之间最短通路的长度；
  • 若$u$与$v$不连通，规定$d(u, v) = +\infty$。 距离的性质 对任意$u, v, w \in V(G)$，满足：

1. ​非负性：
   $d(u, v) \geq 0$，等号成立当且仅当$u = v$
2. ​对称性：
   $d(u, v) = d(v, u)$
3. ​三角不等式：
   $d(u, w) \leq d(u, v) + d(v, w)$

点割集： 设无向图$G = (V, E)$，若存在顶点子集$V' \subset V$满足：

1. ​连通性破坏：$p(G - V') > p(G)$
2. ​极小性：对任意$V'' \subsetneq V'$，均有$p(G - V'') = p(G)$ 则称$V'$为点割集。特别地：

• 当$V' = \{v\}$时，称$v$为割点

边割集（定义5.3.5： 设无向图$G = (V, E)$，若存在边子集$E' \subseteq E$满足：

1. ​连通性破坏：$p(G - E') > p(G)$
2. ​极小性：对任意$E'' \subsetneq E'$，均有$p(G - E'') = p(G)$ 则称$E'$为边割集。特别地：

• 当$E' = \{e\}$时，称$e$为割边（桥）​

点连通度 对于无向连通图$G$（非完全图）：

特殊规定：

• 完全图$K_n$的$\kappa(K_n) = n-1$
• 非连通图$\kappa(G) = 0$
• 若$\kappa(G) \geq k$，称$G$为k-连通图

边连通度： 对于无向连通图$G$：

特殊规定：

• 非连通图$\lambda(G) = 0$
• 若$\lambda(G) \geq r$，称$G$为r边-连通图

定义5.3.10 有向图连通性

设有向图$D=\langle V,E \rangle$：

1. ​​弱连通​​：基图是连通图
2. ​​单向连通​​：$\forall u,v \in V$，存在$u→v$或$v→u$路径
3. ​​强连通​​：$\forall u,v \in V$，存在双向路径$u↔v$
   ​​包含关系​​：强连通 ⇒ 单向连通 ⇒ 弱连通

定理5.3.2 强连通判别

有向图$D$是强连通图 ⇔ $D$中存在经过每个顶点至少一次的回路

定理5.3.3 单向连通判别

有向图$D$是单向连通图 ⇔ $D$中存在经过每个顶点至少一次的通路

扩大路径法

对n阶无向图$G=(V,E)$，​​极大路径​​指无法再延伸的路径。构造方法：

1. 任取初始路径
2. 反复延伸路径端点直到无法扩展
3. 所得路径即为极大路径
   此方法可用于证明图中特定结构的存在性

定义5.3.11 二部图

设无向图$G=(V,E)$，若存在顶点集$V$的划分$\{V_1,V_2\}$满足：

1. ​​完备性​​：$V_1 \cup V_2 = V$
2. ​​互斥性​​：$V_1 \cap V_2 = \emptyset$ 且 $V_1,V_2 \neq \emptyset$
3. ​​边特性​​：每条边的两个端点分别属于$V_1$和$V_2$
   则称$G$为​​二部图​​（或二分图、偶图），记作$G=\langle V_1,V_2,E \rangle$。

​​完全二部图​​：若$G$是简单二部图，且$V_1$中每个顶点与$V_2$所有顶点相邻，则称$G$为完全二部图，记作$K_{r,s}$，其中：
$r = |V_1|, \quad s = |V_2|$

​​特例​​：

• 当$n \geq 2$时，$n$阶零图（无边图）是二部图
• 星形图$K_{1,n}$是特殊的完全二部图

定理5.3.4 二部图判定定理

设$n \geq 2$，则$n$阶无向图$G$是二部图当且仅当$G$中不含长度为奇数的圈（简称​​奇圈​​）。

关键概念对比

定理部分

握手定理:在任何无向图中，所有顶点 的度数之和等于边数的2倍 在任何有向图中，所有顶点的度数之和等于边数的两倍，所有顶点的出度之和等于所有顶点的入度之和 推论5.2.1:任何图中，奇度顶点 个数是偶数 定理5.2.3：非负整数列$d=\{d_1,d_2,...d_n\}$是可图化的当且仅当$\Sigma_{i=1}^nd_i$为偶数 定理5.2.4:设$G$为任意n阶无向简单图，则$\Delta(G)\le n-1$

推论 5.2.2 在$n$阶图$G$中，若从顶点$u$到$v$存在通路，且$u \neq v$，则从$u$到$v$一定存在长度小于或等于$n-1$的初级通路（路径）。 定理 5.2.6 在$n$阶图$G$中，若存在从$v$到自身的回路，则一定存在从$v$到自身长度小于或等于$n$的回路。 推论 5.2.3 在$n$阶图$G$中，若存在从$v$到自身的简单回路，则一定存在从$v$到自身长度小于或等于$n$的初级回路。 长度相同的圈都是同构的，因此在同构意义下给定长度的圈只有一个。在标定图中，圈表示成顶点和边的标记序列。只要两个标记序列不同，就认为这两个圈不同，称这两个圈在定义意义下不同。