Mengzelev's Blog

图论学习笔记-旅行问题

Word count: 773 / Reading time: 3 min
2018/11/21 Share

Euler图

Euler回路(Euler cycle):图$G$的一条包含$G$的每一条边的回路$C$

Euler图(Euler graph):含有Euler回路的连通图

Euler迹(Euler trial)含有连通图$G$的每条边的开迹

当讨论图的Euler性质时,

定理6.1:一个非平凡连通图$G$是Euler的 当且仅当 $G$的每个顶点的度都为偶数

推论6.2:一个连通图$G$含有一条Euler迹当且仅当$G$恰有两个度为奇数的顶点,而且$G$的每一条Euler迹始于一个度为奇数的顶点而终止于另一个度为奇数的顶点。

例6.3结论:设$G$和$H$是两个非平凡的连通图,则$G\times H$是Euler的当且仅当$G$和$H$都是Euler的或者$G$和$H$的每个顶点度均为奇数。

Hamilton图

Hamilton圈(Hamiltonian cycle):一个含图$G$的每个顶点的圈

Hamilton图(Hamiltonian graph):一个含有Hamilton圈的图

Hamilton路(Hamiltonian path):一条含图$G$的每个顶点的路

有Hamilton圈, 一定有Hamilton路;
有Hamilton路,不一定有Hamilton圈

Hamilton图的特征

  • $n\ge 3$阶图的一个Hamilton圈$C$是$n$阶的连通2正则子图
  • $C$不含有阶小于$n$的圈作为子图
  • $G$也不含有有度大于等于3的子图
  • 如果$G$含有度为2的顶点,则与$v$关联的两条边一定位于$C$上

定理6.4:Peterson图不是Hamilton的

Hamilton图的性质

$k(G)$:图的连通分支数

定理6.5:如果$G$是一个Hamilton图,则对$G$顶点的任一非空真子集$S$,都有$k(G-S)\ge |S|$(一个图是Hamilton图的必要条件
逆否命题:设$G$为一个图。如果对$V(G)$的某个非空真子集$S$,有$k(G-S)>|S|$,则$G$不是Hamilton的(一个图为非Hamilton的充分条件)
如果图$G$含有一个割点$v$,则$G$不是Hamilton的

Hamilton图的充分条件

定理6.6(Ore 定理):设$G$为一个$n(n\ge 3)$阶的图,如果对于$G$的每对不邻接的顶点$u,v$,有$deg u +deg v\ge n$,则$G$是Hamilton的。
该定理给出的界是紧的

推论6.7:设$G$为一个$n\ge 3$的图,如果对于$G$的每个顶点$v$,均有$deg v\ge n/2$,则$G$是Hamilton的。

定理6.8:设$u$和$v$是一个$n$阶图$G$的两个不邻接的顶点,并且$deg u + deg v\ge n$,则$G+uv$是Hamilton的当且仅当$G$是Hamilton的。

闭包(closure):由$G$出发递归地连接度数之和至少为$n$的不邻接顶点对,记为$C(G)$

定理6.9:一个图是Hamilton的当且仅当它的闭包是Hamilton的。

推论6.10:如果$G$是一个阶至少为3的图,且它的闭包$C(G)$是一个完全图,则$G$是一个Hamilton图

定理 6.11:设$G$是一个$n(n\ge 3)$阶的图。如果对于每个整数$j(1\le j<\frac{n}{2})$,$G$中度至多为$j$的顶点数小于$j$,则$G$是Hamilton的。

CATALOG
  1. 1. Euler图
  2. 2. Hamilton图
    1. 2.1. Hamilton图的特征
    2. 2.2. Hamilton图的性质
    3. 2.3. Hamilton图的充分条件