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。

十、求关键通路示例