【离散数学-学习日记】2024-3-23

标签：2024 通路哈密顿 23 离散数学 V1 哈密尔顿回路顶点

有向欧拉图的判别法
【定理4-3】有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度。
【定理4-4】有向图D是半欧拉图当且仅当D是单向连通的，且D中恰好有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度。
【定理4-5】G是非平凡图当且仅当G是连通的且为若干个边不重的圈之并。在这里插入图片描述

在这里插入图片描述

//分成两个连通图，两个连通图之间有结点，可以使之构成回路。
在这里插入图片描述

//从起始位置开始，每三个位置为一个点位，转动鼓轮，得到的二进制数都不相同→转换成欧拉图
在这里插入图片描述

//难点：知道可以用欧拉图，并且构造出欧拉图

哈密顿图

哈密尔顿图定义

[哈密尔顿通路]经过图中所有顶点一次仅一次的通路。
[哈密尔顿回路]经过图中所有顶点一次仅一次的回路。
[哈密尔顿图(H图)]具有哈密尔顿回路的图。
[半哈密尔顿图]具有哈密尔顿通路且无哈密尔顿回路的图。
几点说明:

平凡图是哈密尔顿图;
哈密尔顿通路是初级通路，哈密尔顿回路是初级回路;
环与平行边不影响哈密尔顿性;
哈密尔顿图的实质是能将图中的所有顶点排在同一个圈上。

无向哈密顿图的必要条件
【定理5-1】设无向图G=<V,E>是哈密顿图，对于任意V₁⊂V且V₁≠∅,均有p(G-V₁)≤|V₁|
证明： 设C为G中的一条哈密顿回路
(1)p(C-V₁)≤|V₁| //删除一个顶点，不影响连通性
(2)p(G-V_{1</subp(C-V₁)≤|V₁|(因为C⊆G)
推论：设无向图G=<V,E>是半哈密顿图，对于任意的V₁⊂V且V₁≠∅,均有p(G-V₁)≤|V₁|+1
证明：令Γuv为G中哈密顿通路，令G’=G⋃(u,v),则G‘为哈密顿图，于是p(G-V₁)=p(G’-V₁-(u,v))≤|V₁|+1
说明}

定理5-1中的条件是哈密顿图的必要条件，但不是充分条件（彼得松图）
常利用定理5-1判断某些图不是哈密顿图。
例2 设G为n阶无向连通简单图，若G中有割点或桥，则G不是哈密顿图。
//割点：删掉这个顶点，原来的连通图就不连通了
//桥：删去这条边就不连通了
证明： 设v为个点，则p(G-v) ≥2＞|{v}|=1.
K₂有桥，它显然不是哈密顿图。除K₂外，其他有桥的图（连通的）均有割点。
其实，本例也实用于非简单连通图。

无向哈密顿图的充分条件

【定理5-2】设G是n阶无向基督徒，若对于任意不相邻的顶点v_i，v_j，均有d(v_i)+d(v_j)≥n-1,则G中存在哈密顿通路。
【证明】：(1)证明G连通；(2)构造H通路
推论设G为n(n≥3)阶无向简单图，若对于G中任意两个不相邻v_i，v_j，均有d(v_i)+d(v_j)≥n,则G中存在哈密顿回路，从而G为哈密顿图。
说明

定理5-2是半哈密顿图的充分条件，但不是比哟啊条件。长为n-1（n≥4）的路径构成的图不满足条件，但它显然是半哈密顿图。
定理5-2的推论同样不是哈密顿图的必要条件，G为长为n对的图，不满足条件，但它当然是哈密顿图。
有定理5-2的推论可知，K_n均为哈密顿图。//K为n阶正则呢图

有向哈密顿图的充分条件

【定理5-3】若D为n(n≥2)阶竞赛图，则F中具有哈密尔顿通路。
证明思路： 注意，竞赛图的基图是无向完全图。对n(n≥2)做归纳，只需观察下面两个图。
在这里插入图片描述

汉密尔顿回路判定方法
求图中的哈密顿回路或判断某图是否有哈密顿回路至今还是一个难题。算法具有最坏时间复杂性。可行方法:

观察出哈密顿回路;
满足充分条件;
必要条件判定不含有H回路。

最短通路问题

给边赋权值的建模

航线系统建模

给边赋予权值，权值可以是近距离、时间、价格等等。
在这里插入图片描述

基本概念

[带权图]给每条边赋权值为一个数的图。
[带权图中一条通路的长度]通路上各边权值的总和。
[最短通路]在两个给定顶点之间长度最短的通路。
求最短通路的算法
迪克斯屈拉算法

Procedure Digjstra(G:权值大于0的带权连通简单图)
{G中顶点a=v1,v2,...vn=z,权值w(vi,vj),其中若(vi,vj)不是G中的边，则w(vi,vj)=∞}
F偶然 i：1 to n
	L(vi): = ∞ //其余顶点权值为无穷大
L(a) = 0; S: = Φ
while z∉S
begin
	u:=不属于S的L(u)最小的一个顶点； S:=S⋃{u}
	for 所有不属于S的顶点v
		if L(u)+w(u,v)<L(v)then L(v)=L(u)+w(u,v)
end{L(z)=从a到z的最短通路长度}
![请添加图片描述](/i/ll/?i=direct/f0a92f2c941748e0b7b385e463f25a76.png)

在这里插入图片描述