L003 圈和遍历

圈和树

起点和终点相同的非平凡路线称作「闭路线」（closed walk），边不重复出现的闭路线称作「闭迹」（closed trail），又称「回路」（circuit、tour），顶点不重复出现的闭迹称作「圈」（cycle）。

Th.3.1 对于图 \(G=\left\langle V,E\right\rangle\) 和边 \(e\in E\)，\(e\) 是 \(E\) 的割边当且仅当 \(e\) 不在任何圈中。

图 \(G\) 中最短圈的长度称为 \(G\) 的「围长」（girth），最长圈的长度称作 \(G\) 的周长（circumference）。

不含圈的连通图称作「树」（tree），树中度为 \(1\) 的顶点称作「叶顶点」（leaf）。更一般地，不含圈的图称为「森林」（forest）。

Th.3.2 给出了一系列树的等价定义：对于图 \(G\)：

\(G\) 连通且不含圈。
\(G\) 中任意两个顶点间有且仅有一条路。
\(G\) 不含圈且 \(\epsilon(G)=\nu(G)-1\).
\(G\) 连通且 \(\epsilon(G)=\nu(G)-1\).
\(G\) 极小连通，即 \(G\) 连通，但删除任一条边均不连通。
\(G\) 极大无圈，即 \(G\) 不含圈，但增加任一条边均形成圈。

若连通图 \(G\) 的生成子图 \(H\) 是树，则 \(H\) 称为 \(G\) 的「生成树」（spanning tree）。

二分图

长度为奇数的圈称为「奇圈」（odd cycle），长度为偶数的圈称作「偶圈」（even cycle）。

对于图 \(G=\left\langle V,E\right\rangle\)，若顶点集 \(V\) 可划分为两个子集 \(X\) 和 \(Y\)，使每条边 \(e\in E\) 的两个端点分别属于 \(X\) 和 \(Y\)，那么称 \(G\) 为「二分图」（bipartite graph），记作 \(G=\left\langle X\cup Y,E\right\rangle\).

若顶点子集 \(X\) 每个顶点与 \(Y\) 中每个顶点都相邻，则 \(G\) 称为「完全二分图」（complete bipartite graph），记作 \(K_{|X|,|Y|}\).

Th.3.3 非平凡图 \(G\) 是二分图当且仅当 \(G\) 不含奇圈。

【Algo.3.1】

Th.3.4

欧拉图

经过图的每条边恰一次的迹称为「欧拉迹」（Eulerian trail），经过图的每条边恰一次的闭迹（回路）称作「欧拉回路」（Eulerian circuit）。含欧拉回路的图称为「欧拉图」（Eulerian graph）。

Th.3.5 非空连通图 \(G\) 含欧拉回路当且仅当 \(G\) 没有顶点的度为奇数。

「弗勒里算法」（Fleury's algorithm）

【Algo.3.2】

Th.3.6

「希尔霍尔策算法」（Hierholzer's algorithm）

【Algo.3.3】

Th.3.7 Th.3.8

哈密尔顿图

经过图的所有顶点的路称作「哈密尔顿路」（Hamiltonian path），经过图的所有顶点的圈称作「哈密尔顿圈」（Hamiltonian cycle）。含哈密尔顿圈的图称为「哈密尔顿图」（Hamiltonian graph）。

Th.3.9 若图 \(G=\left\langle V,E\right\rangle\) 是哈密尔顿图，则对于任一一个顶点子集 \(\varnothing \sub V'\sub V\)，图 \(G-V'\) 含至多 \(|V'|\) 个连通分支。

Th.3.10 对于阶为 \(n\) 的图 \(G=\left\langle V,E\right\rangle\)，若 \(n\ge 3\) 且任意两个不相邻顶点 \(u,v\in V\) 都满足 \(d(u)+d(v)\ge n\)，则 \(G\) 是哈密尔顿图。

Cor.3.3 对于阶为 \(n\) 的图 \(G=\left\langle V,E\right\rangle\)，若 \(n\ge 3\) 且 \(\delta(G)\ge n/2\)，则 \(G\) 为哈密尔顿图。

判定一个图是否含哈密尔顿路和判定一个图是否含哈密尔顿圈可互相规约，而这两个判定问题的复杂度都属于 NPC，且可归约为旅行商问题。