离散数学图论与关系中有图题目 下载本文

S4?{c,e,d},S5?{g},S6?{a,e,f,c},S7?{b,d,e,f}

图中的点割集为V1?{v4}

(有割点的连通图不能是哈密尔顿图。因而若是G连通图且有割点v,则G?v中至少有两个连通分支,即p?G?v???v?,与定理矛盾。) 七、例1 如图G

v1142v363795v5811v6131012v714v2

图中的一个对集为边集(5,12,3).一个最大对集为M*=(1,3,11,14),

完美对集有:(1,3,11,14),(1,3,10,12),(1,6,9,14),(1,7,8,14),(2,4,11,14),(2,4,10,12), (2,5,7,14),(1,7,10,13)

G的全体结点是一个覆盖,一个最小覆盖为K*?(v5,v8,v1,v4,v6)

*独立集有如I?(v1,v6),最大独立集为I?(v7,v1,v6)

v4v8边覆盖有如L?(1,6,9,13,14),最小边覆盖为L*?(1,7,8,14) 可以验证定理I*?K*?3?5?8?V,M*?L*?4?4?8?V 由于该无孤立点的图中K*?M*,I*?L*,从而不是二分图。 例 2 如右彼得森图。

红点集合为一最小点覆盖集,白点集合为最大点独立集,点覆盖数?0?6,点独立数?0?4;

绿边组成最小边覆盖集,这里也是一个最大匹配,边覆盖数

aejdfigbhc?1?5,边独立数(匹配数)?1?5

(彼得森图不是平面图,因为它的顶点数n?10,边数m?15,而它的每个面至少由5条边组成,由n?m?r?2有推论m?55n?2?15??8矛盾) ??33例3 现有4名教师:张、王、李、赵,要求他们去教4门课程:数学、物理、电工和计算

机科学。已知张能教数学和计算机科学,王能教物理和电工,李能教数学、物理和电工,而赵只能教电工。如何安排才能使4位教师都能授课,而且每门课都有人教?共有几种方案?(画出二部图,满足相异性条件,王张李赵因而存在完备匹配。

该题匹配也是完美的,方案只有一种)

数学物理计算机电工

八、作出下列度数列的非同构图

1、度数列d为2,2,2,3,3,4,5,5的八阶13边。可作图以下两图为例:

2、度数列d为2,3,3,3,4,4,5的七阶12边。可作图以下两图为例:

3、度数列d为1,3,3,4,6,6,7的七阶无向图。可作图以下两图为例:

4、6阶2-正则图只有两种非同构情况

5、6阶3-正则图也只有两种非同构情况

九、求最短通路的过程演示

a4372b2aw43723b2v3c332vdb22[0](3)2w(4)a[4]7323b2v[3]cd[7]2[0](3)2w[3]cd[7]2(4)a[4]7v[0](3)[3]c(3)2w(4)a[4](7)3b2v[6]d[0](3)[3]c(3)2w(4)a[4](7)3b2v[6]d[0](3)[3]c(3)(2)w[8][6]d

1、Dijkstra算法(1959年提出)是公认的好算法:第一步,给始点v1标上P标号d?v1???,给其它的点标上T标号dvj?w1j,2?j?n(vi,vj没有边时wij??);第二步,在所有的T标号中取最小者,设结点vk的T标号d?vk?最小,则将vk的T标号改为P标号,并计算具有T标号的其它各个结点的T标号:新的dvj?min旧的dvj,d?vk?+wkj;第三步,若终点已具有P标号,则此标号,即为所求最短路径的权,算法终止;否则转到第二步。

2、Warshall算法:第一步,令W造

?0????0??W??wij??wij;第二步,从W出发,依次构

0???????????k?n阶矩阵W?1?,W?2?,L,W?n?。各W?k??wij??个的定义为:

?k??k?1??k?1??k?1??k?wij?minwij,wik?wkj,wij是从vi到vj中间结点仅属于?v1,v2,L,vk?的通路中

??权最小的通路之权。最后得到的W?n?的元素wij就是是从vi到vj的最短路径的权。

?n?27824125736278241257362782412573634362178412234361782412343621784122573657361346

13u04u04234613u04u0434657363u04u041、对右图给出的附权图G,求出结点v1到其余个节点的最短路径

v2371v4852v64d?v1? d?v2? d?v3? d?v4? d?v5? d?v6? ?* ?* ?* ?* ?* 3 9 *d?v7? ? ? v192? ? 3/v1 3*/v1 3*/v1 *5/v2 10/v2 5*/v2 9/v5 5*/v2 9/v5 4/v2 4/v2 ? ? v3749v5v713/v5 ? ? 4*/v2 13/v5 3*/v1 3*/v1 3*/v1 5*/v2 9*/v5 5*/v2 9*/v5 5*/v2 9*/v5 4*/v2 11/v4 17/v4 ?* ?* 4*/v2 11*/v4 15/v6 4*/v2 11*/v4 15*/v6 注:例如对v3,新的d?v3??min旧的d?v3?,d?v2?+w23?min?9,2+3??5,故v3的临时T标号改为5。在5的右下方记上v2,表明是因为结点v2的标号成为固定标号P而引起v3*的T标号的改变。最后回溯,由第7列15/v6找到v6,再由第6列11*/v4找到v4,再由

??**第4列9/v5找到v5,再由第5列4/v2找到v2,…, 得到最短路径v1v2v5v4v6v7。

2、对右图所示的有向图,用Warshall算法求任意两结点之间的最短路径的权。

??????0???W?W?????2??????7???????1W??????4?29???1???7???????3W??????4?29???1??96??39???5W?????74?28??41?7??42????4???1?422???1????????24?81?5271???1124???8?2593?25410???795244692????1???3?? ?????????????????????3??2???,W????????2??????????14?????7???3??4???,W???11????25?????8???12??9??6??33??6??7,W???10??7?25????47????6?v127v2124v331v442v5v6????4?1??????3??

48?5??92410???15?2???6102713???4?17?????3??

48?511?82495??15?28??692712??73516?47953??

479510?62475??14627???0??1?71128注:因为所给图是强连通的,所以W中不出现?。例如w52??,而w52?9,因为

?1??0??0??0?w52?minw52,w51?w12?min??,2?7??9,这对应通路v5v1v2,通路中间结点属于?4??3??3??3??min?w52,w54?w42?v1?,k?1;再如w52??min?9,4?4??8,这对应通路v5v1v4v2,

??这时通路中间结点属于?v1,v2,v3,v4?,k?4。

十、求关键通路示例