离散数学集合论图论chapter

第17讲欧拉图2021/7/12《集合论与图论》第17讲11.七桥问题,一笔画,欧拉通(回)路,欧拉图2.判定欧拉图的充分必要条件3.求欧拉回路的算法4.中国邮递员问题七桥问题七桥问题(Seven

bridges

of

Königsbergproblem):River

Pregel,Kaliningrad,Russia2021/7/12《集合论与图论》第17讲22021/7/123Leonhard

EulerLeonhard

Euler(1707~1783):人类有史以来最多产的数学家.1736年,“七桥问题”,图论和拓扑学诞生DcAdabfCg《集合论与图论》第17讲Be一笔画2021/7/12《集合论与图论》第17讲4欧拉图(Eulerian)2021/7/12《集合论与图论》第17讲5欧拉通路(Euler

trail):

经过图中所有边的简单通路欧拉回路(Euler

tour/circuit):经过图中所有边的简单回路欧拉图(Eulerian):有欧拉回路的图半欧拉图(semi-Eulerian):有欧拉通路的图无向欧拉图的充分必要条件定理1:设G是无向连通图,则G是欧拉图G中所有顶点都是偶数度G是若干个边不交的圈的并证明:(1)(2)(3)(1).(1)(2):若欧拉回路总共k次经过顶点v,则d(v)=2k.2021/7/12《集合论与图论》第17讲6定理1((2)(3))G中所有顶点都是偶数度G是若干个边不交的圈的并证明:(2)(3):若删除任意1个圈上的边,则所有顶点的度还是偶数,但是不一定连通了.对每个连通分支重复进行.2021/7/12《集合论与图论》第17讲7定理1((3)(1))(1)G是欧拉图(3)

G是若干个边不交的圈的并证明:(3)(1):有公共点但边不交的简单回路,总可以拼接成欧拉回路:在交点处,走完第1个回路后再走第2个回路.#用归纳法严格证明2021/7/12《集合论与图论》第17讲8无向半欧拉图的充分必要条件定理2:设G是无向连通图,则G是半欧拉图G中恰有2个奇度顶点证明:(1)(2):欧拉通路的起点和终点是奇数度,其余顶点都是偶数度.(2)(1):在两个奇数度顶点之间加1条新边,所有顶点都是偶数度,得到欧拉回路.从欧拉回路上删除所加边后,得到欧拉通路.#2021/7/12《集合论与图论》第17讲9有向欧拉图的充分必要条件定理3:设G是有向连通图,则G是欧拉图"

v˛

V(G),

d+(v)=d-(v)G是若干个边不交的有向圈的并证明:(1)(2)(3)(1).(1)(2):若欧拉回路总共k次经过顶点v,则d+(v)=d-(v)=k.其余与定理1类似.#2021/7/12《集合论与图论》第17讲10有向半欧拉图的充分必要条件定理4:设G是无向连通图,则G是半欧拉图G中恰有2个奇度顶点,其中1个入度比出度大1,另1个出度比入度大1,其余顶点入度等于出度.#2021/7/12《集合论与图论》第17讲11例2021/7/12《集合论与图论》第17讲12算法(algorithm)一组有限条指令,具有以下特征:输入:算法工作对象输出:算法工作结果确定性:算法根据输入和当前工作状态,决定下一步采用的指令可行性:算法的指令都是可以实现的终止性:算法工作有穷步后停止输入2021/7/12《集合论与图论》第17讲13输出指令组工作区Fleury算法2021/7/12《集合论与图论》第17讲14输入:连通图G,起点v,终点w.若v„w,则除

v,w外的顶点都有偶数度;若v=w,则所有顶点都有偶数度.输出:从v到w的欧拉通路/欧拉回路.算法:(下一页)Fleury算法(递归形式)2021/7/12《集合论与图论》第17讲15算法:if

d(v)>1

then

e:=v关联的任意非割边else

e:=v关联的唯一边u:=e的另一个端点.递归地求G-e的从u到w的欧拉通路把e接续在递归地求出的通路上Fleury算法(迭代形式)2021/7/12《集合论与图论》第17讲16算法:P0:=v;设Pi=v0e1v1e2…eivi已经行遍,设Gi=G-{e1,e2

,…,ei},ei+1:=Gi中满足如下2条件的边:ei+1与vi关联除非别无选择,否则ei+1不是Gi中的桥若Gi„Ni,则回到(2);否则算法停止Fleury算法(举例)2021/7/12《集合论与图论》第17讲17Fleury算法(正确性证明)定理5:设G是无向欧拉图,则Fleury算法终止时得到的简单通路是欧拉回路证明:

(1)

Pm是回路:

显然.(2)

Pm经过G中所有边:(反证)否则,G-Pm的连通分支还是欧拉回路,并且与

Pm相交.若v0是交点,则算法不应结束;若v0不是交点,则算法在最后离开交点回到

v0时走了桥;这都是矛盾!#2021/7/12《集合论与图论》第17讲18逐步插入回路算法2021/7/12《集合论与图论》第17讲19(0)

i:=0,

v*:=v,v:=v1,P0=v1,G0=G.

e:=在Gi中与v关联的任意边(v,v’),Pi+1:=“Pi”ev’.if

v’„v*

then

i:=i+1,

v=v’,

goto

(1).if

E(Pi+1)=E(G)then

结束else

Gi+1:=G-E(Pi+1),e:=Gi+1中与Pi+1上vk关联的任意边,Pi+1:=vk…vk.v*:=vk,v:=vk,

i:=i+1,

goto

(1).逐步插入回路算法(举例)2021/7/12《集合论与图论》第17讲20应用(轮盘设计)10110110000,001,010,011,100,101,110,1112021/7/12《集合论与图论》第17讲21abcca2021/7/12《集合论与图论》第17讲22应用(轮盘设计)01D=<V,E>,

V={00,01,10,11},E={

abc=<ab,bc>

|a,b,c˛

{0,1}

}0000010001010111011100101101110101101

110

0中国邮递员问题2021/7/12《集合论与图论》第17讲23中国邮递员问题(Chinese

postmanproblem):求邮递员走遍管区所有街道的最短回路管梅谷(Guan

Mei-gu),1962,中国运筹学(Operation

Research)组合优化(Combinatorial

Optimization)带权图(weighted

graph)带权图(weighted

graph):G=<V,E,W>,W:Efi

R,W(e)称为e的权AFB

CD59E38

14

10456ABFEDC510938