欧拉图与哈密顿图

欧拉图
定义：
1. 若无向连通图G中有一条包含G中所有边的闭链，则称此链为欧拉闭链（欧拉链），G成为欧拉图
2. 若G中有一条包含G中所有边的开链，则称此开链为欧拉开链，G为半欧拉图。
注：半欧拉图一定不是欧拉图。

定理1. 无向连通图G是欧拉图的充分必要条件是G中各结点都是偶节点。
充分性证明：取G的最长链C，说明C是闭链，且G所有边在C上。

推论2: 无向连通图G是半欧拉图的充要条件是G恰有2个奇结点。
推论3: 设D是有向弱连通图，则D存在有向欧拉闭链额度充要条件是D中各节点正度和负度相等。

哈密顿图
定义：
1. 无向图G的一条过全部结点的回路（道路）成为G的哈密顿回路（道路），简记为H回路（道路）。包含H回路（道路） 的图成为哈密顿图（半哈密顿图），简称H图（半H图）。

定理4: 若无向图G是H图，则对于结点集的任意子集\(X\subseteq V(G)\)均有\[K(G-X)\le|X|\]其中\(K(\cdot)\)表示连通分支数。
证明：设C是G的一个H回路，只需证\(K(C-X)\le|X|\)。对\(|X|\)进行归纳。

下面给出H图的一个充分条件。
引理5: 对于无向简单图G的任意一条极长道路\(P=v_1\cdots v_l\)，若\(d(v_1)+d(v_l) >l-1\)，则G中存在回路C，使得\(V(C)=V(P)\)。
证明：注意极长道路的性质给出\(v_1,v_l\)的邻点都在P上。存在\(2\le s \le l\)使得\(v_s,v_1\)和\(v_{s-1}, v_l\)分别相邻。
定理6. 如果简单图G的任意两不同结点\(u,v\)都满足\(d(u)+d(v)\ge n-1\)，\(n=|V(G)|\)，则G中存在H道路。
证明：首先说明G是连通图。再取G的一条最长道路P，由引理5得G中存在回路C使得\(V(C)=V(P)\)。最后说明G中所有点在C上。

推论7. 如果简单图G的任意两不同结点\(u,v\)都满足\(d(u)+d(v)\ge n\)，则G中存在H回路。
推论8. 如果简单图G满足\(\delta(G)\ge \frac n 2\)，则G是H图。

引理9. 设G是无向简单图，u和v是G的不相邻结点且满足\(d(u)+d(v)\ge n\)。则G是H图的充要条件是\(G+(u,v)\)是H图。
定义：对无向简单图G，另\(G_0=G\)，再令\(G_{i+1}=G_i+(u_i,v_i)\)其中\(u_i,v_i\)是无向简单图\(G_i\)中的不相邻结点，且满足\(d_{G_i}(u_i)+d_{G_i}(v_i)\ge n\)，直到存在\(k\)使得\(G_k\)中不存在满足\(d(u)+d(v)\ge n\)的不相邻结点。则\(G_k\)成为G的闭合图，记作\(C(G)\)。
引理10. 无向简单图G的闭合图\(C(G)\)是唯一的，即与添加边的顺序无关。
定理11. 无向简单图G是H图，当且仅当\(C(G)\)是H图。

定义：若有向简单图D的每两个不同结点之间恰有一条边，则称D为竞赛图。
定理12. 任意竞赛图D必有H道路。
证明：对n归纳，分别取\(v_{n+1}\)的内、外邻点集的H道路，再通过\(v_{n+1}\)相连。
定理13: 任何强连通的竞赛图D是有向H图。

    所属分类：离散数学     发表于2022-08-21