第8章 几种特殊的图.ppt

1、第一章是一些特殊的图，第二章是一些特殊的图，第八章是8.1欧拉图8.2哈磨粉机顿图8.3二部图8.4平面图8.5树，3，七桥物kngsberg， 把这七座桥重复一遍又一遍，重复一遍，重复一遍，重复一遍，四遍，七桥，忽略不重要的细节，忽略更多的细节，抽象化研究方法，哥白尼5、a、d、c、b、e1、e3、e2、e4、e6、e5、e7，假定有一个起点和一个终点的通路，对于每一个“中间”顶点v必须有相同数量的入边和出边，所以顶点v的度数必须是双位数，问题：图中的一边只有一次Eulers Solution、6、Eulers Solution、a、d、c、b、e1、e3、e2、e4、e6、e5、e7具有起

2、点和终点，对于各个“中间”顶点v，由于具有相同数量的输入侧和输出侧，因此顶点v的度数被双位数定问题：有只通过图的各边一次的路径吗？ 因此，最大2顶点度数为奇数，在该图中，由于顶点度数全部为奇数，所以在图中的一边不存在只通过一次的通路，7、欧拉图、问题是围绕哥白尼堡城寻找7座桥，只通过一次桥最后返回到原来的出发点。 1736年瑞士数学家欧拉(莱昂海德欧拉)发表了关于“哥白尼堡七桥问题”的论文(图论的第一篇论文)。 他从一点开始反复走七桥，最后指出不可能回到原来的出发点。 欧拉称为“图论之父”，1736年多称为“图论元年”8、欧拉图、定义8.1欧拉通路3360通过所有顶点，各边正好一次通路欧拉回路

3、3360通过所有顶点，各边正好一次回路欧拉回路上述定义适用于无向图和有向图，平凡图是欧拉路是简单通路，欧拉电路是简单电路，9，欧拉图判别定理8.1无向图g具有欧拉路，仅g连通，具有无特异度顶点，无向图g具有欧拉路，仅g连通，具有特异度的顶点推论无向图g是欧拉路径的端点，仅g连通，没有特异度的顶点、1.0，例如(1)没有欧拉路径和欧拉路径，没有欧拉路径，有欧拉路径，没有欧拉路径，(3)没有欧拉路径没有欧拉路、(4)有欧拉路、没有欧拉路、a、b、c、d、a、b、c、d、b、c、d、e、f、a、b、c、d、e、f、f、g、h、I、 关于1.1欧拉格拉夫判别定理(续)、定理8.2，图d具有欧拉电路相当

4、，仅d连通，所有顶点的入度等于出度，图d具有欧拉电路，但没有欧拉电路相当，仅d连通，一个顶点的入度大于出度1， 在推论中，有向图d是欧拉格拉夫，只有d连通，所有顶点的入度都是出度. 1.2，实例，(1)没有欧拉电路和欧拉电路，没有欧拉电路，没有欧拉图(3)具有欧拉电路，是欧拉图。(a、b、c、d、b、c、b、a、d、d、a、 哈磨粉机顿电路3360仅一次通过图中所有顶点，哈磨粉机顿电路3360仅一次通过图中的所有顶点。 在W.W.Hamilton电路：中，一次电路不一定具有Hamilton电路，而是具有环球旅行的问题(W.Hamilton，110 ) 存在哈磨粉机顿电路(通路)的一盏茶条件，定

5、理8.3为n(n3)次无向单纯图，如果任意2个不邻接的顶点的频数之和为n1以上，则如果g中存在哈磨粉机顿通路的任意2个不邻接的顶点的频数之和为n以上，则在g中存在哈磨粉机顿电路，即g是哈磨粉机顿图根据推论，g是n(n3 )次无向简图，G)n/2，g是哈磨粉机图，1.6，应用，一次会议有2.0人参加，其中每个人有1.0人以下的朋友。 这个2.0人围成一个圆圈出席了。 有把相邻坐着的两个人小伙伴的可能性吗？ 为什么？解：可。 做个无向图，每个人都是顶点，两个人之间有朋友。 众所周知，图中各顶点的度数等于或大于1.0。 即，图中的任意2个不邻接的顶点的频度是2.0以上，即顶点数。此图为哈磨粉机顿格拉

6、夫，存在哈磨粉机顿电路。 只要采取哈磨粉机顿电路，按照电路通过的顶点顺序配置对应的人的座位，就能满足要求。 1.7，应用，例子是7人，a是英语，b是英语和对外汉语，c是英语，意大利语和露西亚语，d是日语和对外汉语，e是德意志语和意大利语，f是法语，日语和露西亚语，g是法语和德意志语的解说，无向图，每个人都是顶点，两人之间有共同的语言。 ACEGFDBA是哈磨粉机顿电路，按照这个顺序坐就可以了。 1.8，应用，如七天安排七门考试，确保同一人民教师所属的两门考试不在连续的两天内排队，如果人民教师不负责四门以上的课程，就验证经常存在符合上述要求的考试。 证明：假设g是有7个节点的图，各节点对应1个授

7、课测试，如果任2个节点对应的授课测试由不同的人民教师负责，则这2个节点之间有1条边。 因为每个人民教师的课程数目不超过4，每个节点的频率至少是3，所以任何两个节点的频率之和至少是6，g始终存在哈磨粉机顿通路，其对应于一个7个测试课程的合适安排。1.9、二部格拉夫、定义8.3是无向图G=、V1V2=V、V1V2=、且g的各边的两个端点能够以属于V1、V2的方式分成V1和V2，则将V1和V2称为互补顶点子定径套，将g称为二部格拉夫，另外，g为简单图，V1的各顶点为V2的各顶点其中，将r=|V1|、s=|V2|.2.0、非二部格拉夫、非二部格拉夫、定理8.4无向图G=(V，e )设为二部格拉夫的满足

8、条件，g的全环长是双位数。 如果能够在顶点外不交叉地在平面上描绘2.1、平面图和非平面图、定义8.4图g，则将g称为平面图，将该描绘出的无边缘交叉的图称为g的平面埋入的平面嵌入.8.5.1无方向树无方向树的定义及其性质生成树最小生成树8.5.2棵树及其适用根树及其分类最佳树和霍夫曼算法最佳前缀、树、2.3、8.5.1无方向树、无方向树的定义及其性质生成树最小生成树最短路径问题、2.4、真实树、变换、 在计算机科学技术中非常重要的图称为树、抽象树、2.5的无方向树的定义，无方向树：连通无方向图平凡树：连通分支都是树的非连通无方向图树的叶：树的度数为1的顶点分支点：树的度数为2的顶点，例如G1、G

9、2、a、b、c、d、e、e 2.6，无向树的性质，定理8.5g=n次m条边的无向图，以下各命题等价： (1) G是树(连通) (2) G中的任意两个顶点之间存在唯一的路径(3) G连通，m=n1 (4) g没有环，m=n1； (5) G没有环，但是在不相邻的顶点之间加上一条边的图中有唯一的一次环。在a，b，c，d，e，f，g，h，2.7，定理8.5的证明，(1)(2)连通度，任意两个顶点之间有一个路径。 另外，可知如果在某两个顶点间存在两个路径，则这些个的两个路径合并为一个电路，与树的定义不符点. 假设在n=1时m=0结论成立. nk(k1)时结论成立，取n=k 1.边e=(u，v )，那么它

10、是u、v之间的唯一的通路，删除e、g分为2个连通分支，分别是n1、n2个顶点和m1、m2个边，n m2=n21 m=m1 m2 1=n1.2.8、定理8.5的证明(继续)、(3)、(4)假定有电路，删除电路的一边，得到的图仍然连接。 反复进行这样的操作，直到电路消失为止，得到一棵树，从r0.得到(1)(2)(3)，得到mr=n1的不符点。 假设没有g连通，则有p(p1)个连通分支。 假设在第k个连通分支中有nk个顶点和mk条边，则(1)(2)(3)，从mk=nk1 .到m=np，不符点.2.9，定理8.5的证明(续)，(1)(5)为(1)(2)，因为在任意两个不邻接的顶点之间存在唯一的路径，所

11、以在这两个顶点之间新(5)(6)首先，不相邻的两个顶点之间有通道。 否则，不能在它们之间增加新的边来构成电路，所以g会连通。 其次，即使删除边g也连通，这边一定在一个电路上，g没有电路。 (6) (1)如果g没有电路，即使删除电路上的任意边，g也相连，3.0、无向树的性质(续)，定理8.6非无向树至少在两张叶证上有n(n1 )个顶点，x张叶为握手定理8.5，有解x2.31，例如画出满足有2个2度的顶点，其馀顶点都是叶的要求的非同族的的无向树.分解x片叶，设树的顶点数为1x=3x，树的边数为(3 x)-1=2 x，2(2 x)=13 22 x，分解x=3，所以t中有3片叶g定义为8.5，是无向连

12、通图，如果g的子图t为树，则t为g的生成树，位于t的边称为t的分支，不在t的边称为t的弦。例如，在图G2中，节点和黑边构成g的生成树否则，删除循环上的任一边，无损连通度，反复进行直到循环消失，得到图中的一个生成树。 在推论中，假设n阶无向连通图中有m条边，则mn1 .u、v、a、e、b、c、d、3.4、最小生成树、在图g的各边e上附加实数w(e )的被称为边e的权G1 W(G1)=19，g2w (G2 )=2.5，3.5，最小生成树：频带权利图中权重最小的生成树回避法(Kruskal) (1)按照权重从小到大的顺序排列所有的非循环边缘e1，e2， 在em(2)t=(3)fork=1tomdoe

13、k和t中的边缘不构成循环的情况下，将ek加在t上，求出3.6、事例、图的1个最小生成树的w (t )=1233418=3.8、3.7、g的最小生成树可能不唯一， g不同的最小生成树的权重值相同。例如图的1根最小生成树t和其权重w(t )，W(T1)=15，w (T2 )=1.5，3.8 w (T2 )=1.8，4.0，定理8.8对加权格拉夫G(n，m )是通过Kruskal算法得到的g的子格拉夫T*最合适的树。证明： T*不是最佳树，k是g的最佳树，T*是公共边数的最大值。 设t为最佳树，T*和k根为共通边的最佳树。 在tt*ek1333ek60e(t )中，ek 1E(T* )是定理8.5(

14、5)已知的。在T ek 1中包含唯一循环c的c的至少一边ek不在T*中。 设T=(T ek 1) ek，则t是n-1边的连通图。 t是g的生成树。 显而易见，w(T)=w(T) w(ek 1) w(ek ) .从算法中，w(ek 1) w(ek ) .这表示t也是g的最佳树。 t和T*是k 1边的共同边。 我不符点你。 T*是最合适的树。 4.1、印刷法(Prim )首先选择具有最小权利的边，并将其放入生成树中。 在树上具有最小权重的边相继增加，这些个的边与已经在树中的顶点相关联，与已经在树中的边没有形成简单的环。 添加n-1个边时停止。4.2，(旧金山，丹佛) $900 (旧金山，芝加哥)

15、$1200 (旧金山，亚特兰大) $2200 (丹佛，芝加哥) $1300 (丹佛，亚特兰大) $1400 (丹佛，纽约)， 亚特兰大) $700 (芝加哥)纽约) $1000 (亚特兰大，纽约) $800，一家公司计划建立这五个计算机中心的关通讯网络。 可以通过租用的电话线连接到这些个中心的任何一对。 您需要建立什么样的连接，以确保哪两个计算机中心之间有通道，并使网络组件最小化？ 可以使用4.3、频带图对该问题进行建模。 顶点代表计算机中心，代表可租用的电话线，边权是边代表的电话线的月租金。 只要找到最小的树，就能解决这个问题。 4.4，(旧金山，丹佛) $900 (旧金山，芝加哥) $1200 (芝加哥，亚特兰大) $700 (亚特兰大，纽约)