AbabCatのblog

有向道路与有向回路（有向图）#

• 有向道路: 有向图G中边序列 $P=(e_{i1},e_{i2},...,e_{iq})$,其中 $e_{ik}=\langle v_{l},v_{j}\rangle$ 满足: $v_{l}$ 是 $e_{i(k-1)}$ 的终点, $v_{j}$ 是 $e_{i(k+1)}$ 的始点,称边序列P是图G中的一条有向道路。
• 有向回路: $e_{iq}$ 的终点也是 $e_{i1}$ 的始点,则称边序列P是图G中的一条有向回路。
• 简单有向道路/回路: P中边不重复出现。
• 初级有向道路/回路: P中结点不重复出现。
• 初级有向道路/回路一定是简单有向道路/回路。

道路与回路 (无向图）#

• 道路/链: 无向图G中点边交替序列 $P=(v_{i_{1}},e_{i_{1}},v_{i_{2}},e_{i_{2}},...,e_{i_{q-1}},v_{i_{q}})$
  • 满足: $v_{ij}$ 和 $v_{ij+1}$ 是 $e_{ij}$ 的两个端点, 称序列P是图G中的一条链或道路。
• 回路/圈: 如果 $v_{i_{q}}=v_{i_{1}},$ 则称序列P是G中的一个圈或回路。
• 简单道路/回路: P中边不重复出现。
• 初级道路/回路: P中结点不重复出现。
• 简单图的道路可用结点来表示。

其它相关定义#

• 极大路径: P为一条初级道路,其始点与终点都不与P外的顶点相邻。 (路径: 初级道路)
• 短程线: 两结点间长度最短的道路。
• 距离: 短程线的长度 $d(v_{1},v_{2})$。
• 弦: 设C为简单图G中含结点数大于3的一个初级回路,如果结点 $v_{i}$ 和 $v_{j}$ 在C中不相邻,而边 $(v_{i},v_{j})\in E(G)$,则称 $(v_{i},v_{j})$ 是C的一条弦。
  • 若对每一个 $v_{k}\in V(G)$,都有 $d(v_{k})\ge3$,则G中必含有带弦的回路。

• 连通: 若无向图G的任意两个结点之间都存在道路,称G是连通的。
• (弱)连通: 对有向图G,若不考虑边的方向时是连通的,则称G是(弱)连通的。
• 单向连通图: 对有向图G,对任意 $v_{i}, v_{j}\in V$, $v_{i}\rightarrow v_{j}$ 与 $v_{j}\rightarrow v_{i}$ 至少成立其一,则称G为单向连通图。
• 强连通图: 对有向图G,对任意 $v_{i}, v_{j}\in V$, $v_{i}\rightarrow v_{j}$ 与 $v_{j}\rightarrow v_{i}$ 均成立,则称G为强连通图。
  • 有向图G是强连通图当且仅当在G中存在经过每个顶点至少一次的回路。
• 连通支: 若G的连通子图H不是G的任何连通子图的真子图,称H是G的极大连通子图,或称连通支。
  • G的每个连通支都是它的导出子图。
  • 任何非连通图都是2个以上连通支的并。
• 割点: 设 $v$ 是G的一个结点,若 $G-v$ 的连通支数比G多,则称 $v$ 是G的一个割点。（说人话就是删掉这个点，一个连通图变成两个了）
• 割边(也称作桥): 设 $e$ 是G的一条边,若 $G-e$ 的连通支数比G多,则称e是G的一个割边。（和割点的定义相似，把点换成边罢了）

二分图#

• 二分图: 若 $G=(V,E)$ 为无向图,如果 $V(G)$ 可划分成子集 $V_{1}$ 和 $V_{2}$,使得G中每条边的两个结点一个属于 $V_{1}$,另一个属于 $V_{2}$,则称G是二分图。
• 完全二分图: 若 $G=(V,E)$ 为简单二分图,如果 $V_{1}$ 中的每个结点均与 $V_{2}$ 中的所有结点相邻,则称G是完全二分图,记为 $K_{s,t}$,其中 $s=|V_{1}|,t=|V_{2}|$。
• 性质: 如果二分图G中存在回路,则它们都是由偶数条边组成的。
• 二分图判别定理: 无向图G为二分图的充分必要条件是 G中无奇数条边组成的回路。
  • 证明 (必要性): G为二分图 => 无奇数条边的回路
    • a) 若G中无回路,显然G无奇数条边的回路。
    • b) 若G中有回路,记为C,令 $C=v_{i1}v_{i2}...v_{il}v_{i1}, l\ge2$。不妨设 $v_{i1}\in V_{1}$,因为G为二分图,故 $v_{i2}\in V_{2}$, $v_{i3}\in V_{1}$,依次最后 $v_{il}\in V_{2}$ (因为 $v_{il}$ 与 $v_{i1}$ 相邻),故 $l$ 必为偶数 => 无奇数条边构成的回路。
  • 证明 (充分性): 无奇数条边构成的回路 => 二分图
    • 不妨设G为连通图: $v_{0}$ 为G中任意一点。定义两个集合:
    • $V_{1}=\{v|v\in V(G)$ 且与 $v_{0}$ 的距离为偶数}
    • $V_{2}=\{v|v\in V(G)$ 且与 $v_{0}$ 的距离为奇数}
    • 显然: $V_{1}\ne\emptyset$, $V_{2}\ne\emptyset$, $V_{1}\cap V_{2}=\emptyset$, $V_{1}\cup V_{2}=V(G)$
    • 只需证明 $V_{1}$ 中任意两点不相邻且 $V_{2}$ 中任意两点也不相邻。
    • 反证法:若存在 $v_{i},v_{j}\in V_{1}$ 且相邻,令 $e=(v_{i},v_{j})$。 令 $v_{0}$ 到 $v_{i}, v_{j}$ 的短程线分别为 $P_{i}, P_{j}$。 $\Rightarrow P_{i}$ 与 $P_{j}$ 与e构成长度为奇数的回路,与条件矛盾,得证。

欧拉道路与回路#

• 欧拉回路: 连通图G中一条经过所有边的简单回路。
• 欧拉图: 具有欧拉回路的图。
• 欧拉道路: 连通图G中一条经过所有边的简单道路。
• 欧拉半图: 具有欧拉道路但无欧拉回路的图。

欧拉图判定定理#

• 定理1: 无向连通图G中存在欧拉回路的充要条件是 G中各结点的度都是偶数。
  • 证明 (必要性): 令P是欧拉图G的欧拉回路。 当P经过任意一顶点时,该点总有进出两个方向的边; 每条边仅经过一次,所以每个顶点必是偶数度数。
  • 证明 (充分性): 对图G的边数m进行归纳证明。
    • 当 $m=1$ 时,图G只能是个环,因此图G总是欧拉图。
    • 假设当 $m\le k$ 时结论成立,证明 $m=k+1$ 时结论也成立。
    • 1). 连通图G顶点度数为偶数 => 图G中含有一条简单回路C;
    • 2). 去掉简单回路C的边,生成p个连通分支 $G_{i} (i=1,2,...,p)$,连通分支 $G_{i}$ 边小于等于k且顶点度数为偶数 => 欧拉图;
    • 3). 从C中任意一点出发,沿边走到与连通分支 $G_{i}$ 的公共点 $u_{i}$, 然后通过 $G_{i}$ 的欧拉回路回到 $u_{i}$;;依次继续进行到另一个连通分支,最后到达出发点,得到G的欧拉回路。
• 定理2: 无向连通图G中存在欧拉道路(欧拉半图)的充要条件是 G中只有两个度为奇数的结点。
  • 证明: 连接这两顶点,则有欧拉回路;再删去这条边。(欧拉道路的始点和终点必须选在奇数度点)
• 定理3: 有向连通图G是欧拉图的充分必要条件是图中各点的 入度和出度相等。
• 定理4: 有向连通图 G是欧拉半图的充分必要条件是图中至多有两个顶点,其中一个顶点的入度比出度多1,另一个顶点的出度比入度多1,其它顶点入度和出度相等。（这些都和无向图相关的条件相似）

寻找欧拉回路#

• 逐步插入回路: 根据定理1中证明过程。
• Fleury 算法
  • 基本思想: 能不走桥就不走桥。
  • 输入: 欧拉图G
  • (1) 任取 $v_{0}\in V(G)$, 令 $P_{0}=v_{0}$, $i=0$;
  • (2) 令 $P_{i}=v_{0}e_{1}v_{1}e_{2}v_{2}\cdot\cdot\cdot e_{i}v_{i}$。 如果 $E(G)-\{e_{1},e_{2},\cdot\cdot\cdot,e_{i}\}$ 中没有与 $v_{i}$ 关联的边,计算停止; 否则按下述条件从 $E(G)-\{e_{1},e_{2},\cdot\cdot\cdot,e_{i}\}$ 中任取一条边 $e_{i+1}$:
    • (a) $e_{i+1}$ 与 $v_{i}$ 相关联;
    • (b) 除非无别的边可供选择,否则 $e_{i+1}$ 不应该选 $G-\{e_{1},e_{2},\cdot\cdot\cdot,e_{i}\}$ 的桥。
  • 设 $P_{i+1}\leftarrow v_{0}e_{1}v_{1}e_{2}v_{2}\cdot\cdot\cdot e_{i}v_{i}e_{i+1}v_{i+1}$;
  • (3) 令 $i=i+1$,返回(2).

哈密顿道路与回路#

• 哈密顿回路(道路): 无向图G中的一条经过全部结点的 初级 回路(道路)。
• 哈密顿回路(道路): 简称为H回路(道路)。
• 哈密顿图: 具有H回路的图。
• 哈密顿半图: 具有H道路但无H回路的图。

H回路问题说明#

• H回路是初级回路。
• 要求 $V(G)=n\ge3$。
• 只需考虑简单图,因为重边和自环不起作用。
• 完全图 $K_{n}(n\ge3)$ 中存在H回路。
• H回路的判定比较困难,没有发现充分必要的条件,只有若干充分条件。

判定定理与推论#