第五章 图论5
定理2 欧拉通路的充要条件 连通图有欧拉通路而无欧拉回 路恰有两个奇数度顶点 证明:定理1的直接推论 有向图的欧拉通路和欧拉回路:类似与无向图
5.5.2哈密顿图 定义2 哈密顿通路:含所顶点的基本通路(G中每个顶点 恰在此陆中出现一次) 半哈密尔顿图:有哈密尔顿路的图
哈密顿回路:含所有顶点的简单回路 (u1=un,而u2…un恰在此路中出现一次) 哈密顿图:有哈密顿回路的图
例1 在图7-47里,哪些无向图具有欧拉回路?在没有欧拉 回路的那些图里,哪些具有欧拉通路?
解 图G1具有欧拉回路,例如a, e, c, d, e, b, a。G2和G3 都没有欧拉回路。但是G3具有欧拉通路,即a, c, d, e, b, d, a, b。G2没有欧拉通路。 图H2具有欧拉回路,例如a, g, c, b, g, e, d, f, a。H1 和H3都没有欧拉回路。H3具有欧拉通路,即c, a, b, c, d, b,但是H1没有欧拉通路。
n(n 1) 1 2 n (n 2 n 2) 2 2
当n为奇数时,每个点的度为偶数,有欧拉回路;当n为偶数时,只有在n=2时有 欧拉路 定理 设G=(V,E)是弱连通有向图,则G 是欧拉图的充要条件是G为强连通图且每 个顶点的出度与入度相等
例 见P253
(接上页)
算法1 构造欧拉回路 procedure Euler(G :所有顶点有偶数度的连通多重图) circuit:=在G中任选的顶点开始连续地加入边所形成的回到 该顶点的回路 H:=删除这条回路的边之后的G while H还有边 begin subcircuit:=在既是H中的顶点也是circuit一条边 的端点开始的H中的一条回路 H:=删除subcircuit的边和所有孤立点之后的H Circuit:=在适当顶点上插入subcircuit之后的circuit end{circuit 是欧拉回路}
定理1 欧拉图的充要条件 连通图是欧拉图每个顶点 的度 都为偶数
证明:先直观描述
:显然 : 1.回路的存在性 从连通图G中的任一节点v0开始,取关联于v0的边 e1={v0,v1},因为d(v1)为偶数,所以可以在G中继续取关 联于v1的边e2={v1,v2},…,直到取到一条边ek+1={vk,v0}, 得到一条简单回路h1: (v0,e1, v1,e2,…,v1,ei+1,…, ek+1,v0)。这里,ei≠ej(i≠j)。显然,h1G。
例7 Kn(n>2)是哈密顿图 解 :从Kn中的任意一个顶点开始来形成哈密顿回路。以 所选择的任意顺序来访问顶点,只要求通路在同一个顶点 开始和结束,而且恰好访问其他每个顶点一次。这样做是 可能的,因为在Kn中任意两个顶点之间都有边。
定理 哈密顿图的充分条件 若G是n个节点的无向连通简单 图,其任一节点v满足d(v)≥n/2,则G是哈密顿图。 证明:①为证这个结论,我们先给出一个引理:若 G=(V,E)是有n个节点的无向简单图,对于每一对不相邻的 节点u,v,有d(u)+d(v)≧n,则G是哈密顿图的充分必要条 件是H=(V,E∪{e})为哈密顿图,这里e是与节点u,v关联 的无向边。 (接下页)
Байду номын сангаас
例 下图是欧拉图,试找出欧拉回路 . 1 .1 2. .6 .5 2. .6 .5 .7 .7 3. .4 3. .4
2. 3.
.1 .6 .7 .4
.5
解 从顶点1开始找一条路C(123451),然后删去C中的边得图G’,在G’中找一条回 路C’(137561),再在G’中删去C’中的边得图G”,再在G”中找一条回路C”(62746) 。在G”中删去C”中的边后已成为空图。 找C与C’的一个公共顶点,比如1,把C与C’拼成含边数更多的回路 D:(12345137561),再把D与C”拼成G的欧拉回路(找公共点6)(123451375627461). Fleury算法: 设G=(V,E)是欧拉图 1.取u0 ∈V,令l0=u0 2.li=u0e1u1e2…eiui是已求出的一条路,按以下方法从E-{e1,e2,…,ei}中选取ei+1: a ei+1与ui相关联 b 除非无别的边可选取,否则ei+1不应是图G’=(V,E-{e1,e2,…ei})中的割边; 3.当2不能再进行时,算法停止 那么,最后所得的简单回路lm=u0e1u1e2…emum(um=u0)为G的一条欧拉回路
. 1
2. 3. .6 .5
1 .
.3
.5
.4 2. .4 .6 这两图均为哈密尔顿图,(1234561),(1236541)分别为哈密尔顿回路 哈密尔顿回路有下列一些简单性质 1.哈密尔顿回路是简单回路 若G有n个顶点,则每条哈密尔顿路含有n-1条边,哈密尔顿回路喊有n条边 2.若G有孤立点,则G无哈密尔顿路;若G有某点的度为1(这样的点称为悬挂点) ,则G 不是哈米尔顿图 3.设u是G的一个顶点,且u的度为2,若G有哈密尔顿回路,则以u为端点的两条边 必须出现在哈密尔顿回路中。。因此,如果连接G的度为2的边已构成回路,且还有 不在该回路中的点,则G 不是哈密尔顿图。 下图中(1234561)已构成回路,但顶点7不在该回路中,该图不是哈密尔顿 图 .1 2. .6
哈密顿图的必要条件 – 没有1度的顶点 – 2度顶点的边必定在哈密顿回路上 – 与一个顶点关联的边中有且仅有两条在哈密顿回路上 – 哈密顿回路中没有小回路 – 对V的任意非空子集S,有(G-S)≤S。G-S是从G中删除S中的顶点及 其关联边 后余下的图,(G-S)表示图G-S的连通分支的数目。 证:设C为G的哈密尔顿回路,C视为G的子图,在回路C中,每删除S中的一个 点及与该点相邻的两条边,最多增加一个分支,且删除S的第一点时分支 数不变,故有: W(C-S) ≤|S| 又C是G的支撑子图(顶点数相同),故C-S是G-S的支撑子图,且 W(G-S) ≤W(C-S) 因此 W(C-S) ≤S 例 见P256 例 设G是有割边的连通图,试证G不是哈密尔顿图 证 设G 是连通图。e是G的一条割边,e的端点为u,v,令S={u},则W(G-S)=2 G不是哈密尔顿图
第五章 图论
5.5欧拉图和哈密顿图 哥尼斯褒七桥问题 5.5.1欧拉图 定义1 欧拉通路:含所有边的简单通路(恰包含G的每条边 一次的简单路) 具有欧拉路的图称为半欧拉图 欧拉回路:含所有边的简单回路 欧拉图:有欧拉回路的图 1. .1 .5 .4 .5 2 . .5 1. .4 3 . 4 2. .3 2. .3 以上均为欧拉图,(a)中12345135241是欧拉回路,(b) 中12435231是欧拉回路
②现在我们来证明:若G中对于每一对不相邻的节点u,v, 有d(u)+d(v)≧n,则G是哈密顿图。因为若在G中每一对不 相邻节点u,v之间连一条无向边,得到图H,则H是n阶无 向完全图,从而H是哈密顿图,由引理,可知G是哈密顿 图。 ③由2,我们可直接推出若任一节点v满足d(v)≥n/2,则G是 哈密顿图。 例8 格雷码及其应用:构造长度为n的2进制编码的序列, 使相邻的码仅相差1位 用Qn来建模 (接下页)
例 试用Fleury算法求下列欧拉图G的欧拉回路 e1 . 1 e7 e6 . 6 2. .4 e5 e2 .3 e3 e4 . 5 解 先取定一顶点,比如1,连接顶点1的边由两条,这两条均不是割边,可任取其 一,设取e1,则有简单路le12,与 顶点2相连的边只有e2,(尽管e2是G去掉e1所得 的图的割边),下一边只有取e2,这样,有简单路le12e23.类似的,下一条边只有取 e3,又有更长的简单路1e12e23e34,下一条边得选取可以是e4,也可以是e6,若选取 e4,则最后的欧拉回路为e1e2e3e4e5e6e7;若选取e6,则最后的欧拉回路为 e1e2e3e6e5e4e7.需要稍加注意的是,在选定简单路e1e2e3后,下一步不能选e7(e7是 G删去边e1,e2,e3后构成的图的割边),否则fluery算法不能进行下去,得不出欧拉 回路。 定理 设G是无向连通图,则G是半欧拉图的充要条件是G恰含有两个奇数度点 证 必要性 设G是半欧拉图,P=u1e1u2…umemum+1是G的一条欧拉路,u1 ≠um+1,只 有u1与um+1是奇数度点。 充分性 设G中只有u,v两个顶点为奇数度点。在图G中增加一条连接u,v的边得一 个新图G’,G’(欧拉图中每个顶点的度均为偶数),于是在G’中存在一条欧拉回路, 在该回路中删去刚添加的边即的一条欧拉路,图G是半欧拉图 例见P252
(接下页)
2.若h1=G,则G是欧拉图,否则转下一步。 3.记H=G-h1,因为G是连通图,所以H与h1至少有一个节点 重合,不妨记为vi,又因为h1中d(vi)是偶数,故在H中d(vi) 仍是偶数,从而从图H的节点vi出发,重复步骤1的做法, 又可得简单回路h2: (vi,e1’,v1,e2’,…,vi)这里ei’≠ ej’(i≠j),那么 h1∪ h2所对应的简单回路是:(v0,e1,v1,e2,…,vi, e1’,v1,e2’,…,vi,ei+1,…,ek+1,v0)。不妨将h1∪ h2仍记为 h2,转步骤2。 对于有限图G,我们总可以在有限步骤中构造出简单回路 h1,使得h1=G,故G是欧拉图。
.7 3 . .4 .5 4.设u是图G的一个顶点,且d(u)>2,G有哈密尔顿回路,则该回路仅用以u为端点的
哈密顿的智力题: 木质十二面体,有十二个正五边形表面,二十个顶点,顶 点标记为不同的城市,每个顶点上有钉子,另有一细线。 目标是从一个城市开始,沿十二面体的边旅行,访问其他 19个城市,每个恰好一次,回到第一个城市结束。旅行经 过的回路用钉子和细线来标记。
例 试问n个顶点的完全图Kn中有多少回路?有没有欧拉路或欧拉回路 3 Cn 解 在Kn中, 3条边可以组成一个回路,有 个; 4条边也可以组成一个回 4 n Cn Cn 路,有 个,以此类推,n条边构成的回路有 个,故Kn的回路总数为