离散数学I-图论-优秀PPT.pptx

《离散数学I-图论-优秀PPT.pptx》由会员分享，可在线阅读，更多相关《离散数学I-图论-优秀PPT.pptx（189页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第七章第七章 图的基本概念的基本概念2绪论abdccabd 哥尼斯堡七桥问题哥尼斯堡七桥问题:3绪论n周游世界问题周游世界问题4绪论n网络布线问题网络布线问题5绪论n印刷线路板布线问题印刷线路板布线问题bcdef6绪论12乙丙3甲n匹配问题匹配问题7图(graph)graph)cabdn（无向）图（无向）图：G=(VG=(V，E)E)nV V：顶点顶点集集 nE E：边集边集8有向有向图(directed graph)directed graph)abce1e2V=a,b,cE=,=e1,e2n有向边有向边:带有方向的边（用序偶表示）带有方向的边（用序偶表示）n有向图：全部的边都是有向边的图

2、。有向图：全部的边都是有向边的图。9图图的一些概念和的一些概念和的一些概念和的一些概念和规规定定定定 (P107)(P107)nV(G)，E(G)分分别别表示表示G的的顶顶点集和点集和边边集。集。n若若|V(G)|n，则则称称G为为n阶图阶图。n若若|V(G)|与与|E(G)|均均为为有限数，有限数，则则称称G为为有有限限图图。n若若边边集集E(G)，则则称称G为为零零图图，此，此时时，又若，又若G为为n阶图阶图，则则称称G为为n阶阶零零图图，记记作作Nn，特殊，特殊地，称地，称N1为为平凡平凡图图。10标定定图与非与非标定定图、基、基图 (P108)n将将图的集合定的集合定义转化成化成图形表

3、示之后，常用形表示之后，常用ek表示表示无向无向边(vi,vj)（或或有向有向边），），并称并称顶点或点或边用字母用字母标定的定的图为标定定图，否，否则称称为非非标定定图。n将有向将有向图各各有向有向边均改成无向均改成无向边后的无向后的无向图称称为原来原来图的的基基图。11关关联与关与关联次数、次数、环、孤立点、孤立点 n设G为无向无向图，ek(vi,vj)E，称称vi,vj为ek的端点的端点,ek与与vi或或ek与与vj是彼此相是彼此相关关联的。的。若若vivj，则称称ek与与vi或或ek与与vj的的关关联次数次数为1。若若vivj,则称称ek与与vi的的关关联次数次数为2,并称并称ek为环

4、。无无边关关联的的顶点均称点均称为孤立点孤立点。12相相邻与与邻接接 n设无向无向图G，vi，vj V，ek，el E。若若 et E，使得使得et(vi，vj)，则称称vi与与vj是是相相邻的的若若ek与与el至少有一个公共端点至少有一个公共端点，则称称ek与与el是是相相邻的的n设有向有向图D，vi，vj V。若若 et E，使使得得et，则称称vi为et的的始点始点，vj为et的的终点点abce1e2abc13邻域域n设无向无向图G，v V，称称u|u V(u,v)E uv为v的的邻域域，记做做NG(v)或或N(v)。abcN(N(a)a)=b,c14邻域域n设有向有向图D，v V，称称

5、u|u V E uv为v的的后后继元集元集，记做做+D(v)。称称u|u V E uv为v的的先先驱元集元集，记做做-D(v)。称称+D(v)-D(v)为v的的邻域域，记做做ND(v)。abce1e2N N+(a)a)=b,cN N-(a)=a)=15简洁图与多重与多重图 定定义(P109,定定义7.5)在无向在无向图中，关中，关联一一对顶点的无向点的无向边假如多于假如多于1条，条，则称称这些些边为平行平行边，平行，平行边的条数称的条数称为重数。重数。在有向在有向图中，关中，关联一一对顶点的有向点的有向边假如多于假如多于1条，并且条，并且这些些边的始点和的始点和终点相同点相同(也就是也就是它它

6、们的方向相同的方向相同)，则称称这些些边为平行平行边。含平行含平行边的的图称称为多重多重图。既不含平行既不含平行边也不含也不含环的的图称称为简洁图。16abce1e2abce1e3e2e417顶点的度数点的度数定定义(P109,定义7.6)设G为一无向一无向图，v V，称称v作作为边的端点次数之和的端点次数之和为v的度的度数数，简称称为度度，记做做 dG(v)或或d(v)。设D为有向有向图，v V，称称v作作为边的始点次数之和的始点次数之和为v的出度的出度，记做做d+D(v)，简记作作d+(v)。称称v作作为边的的终点次数之和点次数之和为v的入度的入度，记做做d-D(v)，简记作作d-(v)。

7、称称d+(v)+d-(v)为v的的度数度数，记做做d(v)。18abce1e2abce1e219图的度数的相关概念的度数的相关概念 (P110)n在无向在无向图G中，中，最大度最大度(G)maxd(v)|v V(G)最小度最小度(G)mind(v)|v V(G)n在有向在有向图D中，中，最大出度最大出度+(D)maxd+(v)|v V(D)最小出度最小出度+(D)mind+(v)|v V(D)最大入度最大入度-(D)maxd-(v)|v V(D)最小入度最小入度-(D)mind-(v)|v V(D)20图的度数的相关概念的度数的相关概念n称度数称度数为1的的顶点点为悬挂挂顶点点，与它关，与它关

8、联的的边称称为悬挂挂边。度。度为偶数偶数(奇数奇数)的的顶点称点称为偶度偶度(奇度奇度)顶点点。abce1e221握手定理握手定理ab2 4 6 2 4 6 abcabcn注：遇到环要加注：遇到环要加2 2。n计算以下各图中顶点度之和。计算以下各图中顶点度之和。22握手定理握手定理定理定理(P110,定理定理7.1)设G为随意无向随意无向图，Vv1,v2,vn，|E|m，则定理定理(P110,(P110,定义定义7.2)7.2)设设D D为随意有向为随意有向图，图，V Vv1,v2,vnv1,v2,vn，|E|E|m m，则，则 23握手定理握手定理n推论：奇度点（度数为奇数）有偶数个。推论：

9、奇度点（度数为奇数）有偶数个。abce1e2奇度点为奇度点为2 2个。个。K K4 4abcde奇度点为奇度点为4 4个。个。24度数列度数列(P110)设G为一个一个n阶无向无向图，Vv1,v2,vn，称，称d(v1)，d(v2)，d(vn)为G的度数列。的度数列。对于于顶点点标定的无向定的无向图，它的度数列是唯一的。，它的度数列是唯一的。反之，反之，对于于给定的非定的非负整数列整数列dd1,d2,dn，若存在，若存在Vv1,v2,vn为顶点集的点集的n阶无向无向图G，使得，使得d(vi)di，则称称d是可是可图化的。化的。特殊地，若所得特殊地，若所得图是是简洁图，则称称d是可是可简洁图化的

10、。化的。25可可图化的充要条件化的充要条件定理定理(P110,定理7.3)设非非负整数列整数列d(d1，d2，dn)，则d是可是可图化的当且化的当且仅当当 26定理定理定理定理 设G为随意随意n阶无向无向简洁图，则(G)n-1例例 推断下列各非推断下列各非负整数列哪些是可整数列哪些是可图化的？哪些化的？哪些是可是可简洁图化的？化的？(1)(5,4,4,3,3,2)(2)(5,3,3,2,1)27定理定理定理定理(P112,定理定理7.5)设非非负整数列整数列d(d1，d2，dn)，且且n-1 d1 d2 dn 0,则d是是可可简洁图化的当且化的当且仅当当d(d2-1，d2-1dd1+1-1，d

11、d1+2，dn)可可简洁图化。化。例例 推断下列各非推断下列各非负整数列哪些是可整数列哪些是可图化的？哪些化的？哪些是可是可简洁图化的？化的？(1)(5,5,4,4,2,2)(2)(4,4,3,3,2,2)28同构同构(isomorphic)isomorphic)abcdG1234G29图的同构的同构定义定义(P113,定义7.7)设设G G1 1V，G G2 2V 为两个无向图，若存在双射函数为两个无向图，若存在双射函数f f：V V1 1VV2 2，对于对于vi,vjVV1 1，(vi,vj)E)E1 1 当且仅当当且仅当(f(f(vi),f(),f(vj)E)E2 2，并且并且(vi,v

12、j)与与(f(f(vi),f(),f(vj)的重数相同，的重数相同，则称则称G G1 1与与G G2 2是同构的是同构的，记做，记做G G1 1G G2 2。30同构同构GGabcdefbcdefaG与与G是否同构？是否同构？31彼得森彼得森(Petersen)图图32完全完全图定定义7.8(P114)设G为n阶无向无向简洁图，若，若G中中每个每个顶点均与其余的点均与其余的n-1个个顶点相点相邻，则称称G为n阶无向完全无向完全图，简称称n阶完全完全图，记做做Kn(n1)。设D为n阶有向有向简洁图，若，若D中每个中每个顶点都点都邻接接到其余的到其余的n-1个个顶点，又点，又邻接于其余的接于其余的

13、n-1个个顶点，点，则称称D是是n阶有向完全有向完全图。设D为n阶有向有向简洁图，若，若D的基的基图为n阶无向完无向完全全图Kn，则称称D是是n阶竞赛图。33完全完全图举例例n阶无向完全无向完全图的的边数数为：n阶有向完全有向完全图的的边数数为：n阶竞赛图的的边数数为：K5 53 3阶有向完全图阶有向完全图4 4阶竞赛图阶竞赛图34正正则图定定义(P114,定定义7.9)设G为n阶无向无向简洁图，若若vV(G)，均有，均有d(v)k，则称称G为k-正正则图。举例例 n阶无向完全无向完全图彼得森彼得森图35K K正正则图abcd2正则图abcd3正则图36二部二部图定定义(P114定定义7.10

14、)设G为一一个个无无向向图，若若 能能 将将 V划划 分分 成成 V1和和 V2(V1V2V,V1V2)，使使得得G中中的的每每条条边的的两两个个端端点点都都是是一一个个属属于于V1，另另一一个个属属于于V2，则称称G为二二部部图（或或称称二二分分图，偶偶图等等），称称V1和和V2为互互补顶点子集。点子集。常将二部常将二部图G记为。若若G是是简洁二二部部图，V1中中每每个个顶点点均均与与V2中中全全部部顶点点相相邻，则称称G为完完全全二二部部图，记为Kr,s，其中，其中r|V1|，s|V2|。37二部二部图n以下是否为二部图？一个图G为二部图iff图G无奇圈。cdefbaccdef38二部二部

15、图cefdbacdbacefn推断以下各图是否为二部图？推断以下各图是否为二部图？39二分二分图n推断下图是否为二分图？推断下图是否为二分图？40完全二分完全二分图(1)(1)bcdfaK K2,22,2K2,3acbcdn完全二部图完全二部图 41子子图定定义(P116定义7.11)设G，G 为两个两个图(同同为无向无向图或同或同为有向有向图)，若，若V V且且E E，则称称G 是是G的的子子图，G为G 的的母母图，记作作G G。若若V V，则称称G 为G的的生成子生成子图。42子子图 设G为一一图，V1 V且且V1，称以称以V1为顶点集，以点集，以G中中两个端点都在两个端点都在V1中的中的

16、边组成成边集集E1的的图为G的的V1导出的子出的子图，记作作GV1。设E1 E且且E1，称以称以E1为边集，以集，以E1中中边关关联的的顶点点为顶点集点集V1的的图为G的的E1导出的子出的子图，记作作GE1。43导出子出子图举例例取取V1a,b,c，GV1为(2)中中图所示。所示。取取E1e1,e3，GE1为(3)中中图所示。所示。44定定义定定义(P116定定义7.12)设G为n阶无向无向简洁图，以，以V为顶点集，以全部使点集，以全部使G成成为完完全全图Kn的添加的添加边组成的集合成的集合为边集的集的图，称称为G的的补图，记作作G。若若图G G，则称称为G是自是自补图。(1)(1)为自补图为

17、自补图(2)(2)和和(3)(3)互为补图互为补图45定定义定定义(P117定定义7.13)设G为无向无向图。(1)设eE，用，用G-e表示从表示从G中去掉中去掉边e，称，称为删除除e。设E E，用，用G-E 表示从表示从G中中删除除E 中全部的中全部的边，称，称为删除除E 。(2)设vV，用，用G-v表示从表示从G中去掉中去掉v及所关及所关联的一的一切切边，称，称为删除除顶点点v。设V V，用，用G-V 表示从表示从G中中删除除V 中全部中全部顶点，称点，称为删除除V 。46定定义定定义 设G为无向无向图。(3)设边e(u,v)E，用，用Ge表示从表示从G中中删除除e后，后，将将e的两个端点

18、的两个端点u,v用一个新的用一个新的顶点点w(或用或用u或或v充当充当w)代替，使代替，使w关关联除除e外外u,v关关联的全部的全部边，称称为边e的收的收缩。(4)设u,vV(u,v可能相可能相邻，也可能不相，也可能不相邻)，用，用G(u,v)(或或G+(u,v)表示在表示在u,v之之间加一条加一条边(u,v)，称，称为加新加新边。47举例例48收收缩边(2)(2)nPetersenPetersen图及其一种收缩图图及其一种收缩图 49通路与回路通路与回路定定义(P119定定义7.18)设G为无无向向图，G中中顶点点与与边的的交交替替序序列列vi0ej1vi1ej2vi2ejivil称称为vi

19、0到到vil的的通通路路，其其中中，vir-1,vir为ejr的的端端点点，vi0，vil分分别称称为的的始始点点与与终点点，中中边的条数称的条数称为它的它的长度。度。若若vi0vil，则称通路称通路为回路。回路。若若的全部的全部边各异，各异，则称称为简洁通通(回回)路，路，若若的的全全部部顶点点(除除vi0与与vij可可能能相相同同外外)各各异异，则称称为初初级通通(回回)路或路径路或路径(圈圈)，将将长度度为奇奇数数的的圈圈称称为奇奇圈圈，长度度为偶偶数数的的圈圈称称为偶圈。偶圈。50abce1e3e2e4e3 e1 e2是简单通路但不是初级通路是简单通路但不是初级通路初级通路确定是简洁通

20、路，反之不确定。初级通路确定是简洁通路，反之不确定。通路与回路通路与回路51关于通路与回路的关于通路与回路的说明明n在有向在有向图中，通路、回路及分中，通路、回路及分类的定的定义与无与无向向图中特中特别相像，只是要留意有向相像，只是要留意有向边方向的方向的一一样性。性。bcdae1e2e3abcd不是通路，dcba是通路52通路与回路通路与回路n定理定理(P120定理7.6)在在n阶图G中，若从中，若从顶点点vi到到vj（vivj）存在通路，存在通路，则从从vi到到vj存在存在长度度小于或等于小于或等于n-1的通路。的通路。abce1e3e2e453无向无向图的的连通性通性定定义(P121定义

21、7.20)设无无向向图G，u,vV，若若u,v之之间存存在在通通路路，则称称u,v是是连通的通的，记作作uv。v V，规定定vv。无向无向图中中顶点之点之间的的连通关系通关系（u,v）|u,v V且且u与与v之之间有通路有通路是自反的、是自反的、对称的、称的、传递的，因而的，因而是是V上上的等价关系的等价关系。54连通通图与与连通分支通分支定定义(P122定定义7.21)若无向若无向图G是平凡是平凡图或或G中任何两个中任何两个顶点都是点都是连通的，通的，则称称G为连通通图，否，否则称称G是非是非连通通图或分或分别图。定定义(P122定定义7.22)设无向无向图G，V关于关于顶点之点之间的的连通

22、关系的商集通关系的商集V/V1,V2,Vk，Vi为等价等价类，称，称导出子出子图GVi(i1,2,k)为G的的连通分支，通分支，连通分支数通分支数k常常记为p(G)。连通分支也可定通分支也可定义为:极大极大连通子通子图。55abcabcG1G256无向无向图中中顶点之点之间的短程的短程线及距离及距离 定定义(P122定定义7.23)设u,v为无向无向图G中随意两中随意两个个顶点，若点，若uv，称，称u,v之之间长度最短的通路度最短的通路为u,v之之间的短程的短程线，短程，短程线的的长度称度称为u,v之之间的距离，的距离，记作作d(u,v)。当当u,v不不连通通时，规定定d(u,v)。距离有以下

23、性距离有以下性质：(1)d(u,v)0，uv时，等号成立。，等号成立。(2)具有具有对称性，称性，d(u,v)d(v,u)。(3)满足三角不等式：足三角不等式：u,v,wV(G)，则d(u,v)+d(v,w)d(u,w)57二部二部图的判定定理的判定定理定理定理7.8 一个无向一个无向图G是二部是二部图当且当且仅当当G中无奇圈（或奇数中无奇圈（或奇数长度的回路）。度的回路）。定理定理7.9 设G是是n阶无向无向连通通图，则G的的边数数m n-1。58无向无向图的点的点割割集集定定义7.25(P123)设无向无向图G，若存在，若存在V V，且，且V ，使得，使得p(G-V )p(G)，而，而对于

24、随意的于随意的V V ，均有，均有p(G-V )p(G)，则称称V 是是G的点割集。的点割集。若若V 是是单元集，即元集，即V v，则称称v为割点。割点。v2 2,v4 4,v3 3,v5 5 都是点都是点割集割集v3 3,v5 5都是割点都是割点v1 1与与v6 6不在任何割集中。不在任何割集中。59无向无向无向无向图图的的的的边边割集割集割集割集定定义(P123定定义7.26)设无向无向图G，若存在，若存在E E，且，且E ，使得，使得p(G-E )p(G)，而，而对于随意的于随意的E E，均有，均有p(G-E )p(G)，则称称E 是是G的的边割集，或割集，或简称称为割集。割集。若若E

25、是是单元集，即元集，即E e，则称称e为割割边或或桥。e6 6,e,e5 5,e2 2,e3 3,e1 1,e2 2,e3 3,e4 4,e1 1,e4 4,e1 1,e3 3,e2 2,e4 4 都是割集，都是割集，e6 6,e5 5是桥。是桥。60有向有向图的的连通性通性定定义7.30 设D为一一个个有有向向图。vi,vj V，若若从从vi到到vj存存在在通通路路，则称称vi可可达达vj，记作作vivj，规定定vi总是可达自身的，即是可达自身的，即vivi。若若vivj且且vjvi，则称称vi与与vj是是相相互互可可达达的的，记作作vi vj。规定定vivi。61有向有向图的的连通性通性定

26、定义(P129定义7.31)设D为有有向向图，vi,vj V，若若vivj，称称vi到到vj长度度最最短短的的通通路路为vi到到vj的的短短程程线，短短程程线的的长度度为vi到到vj的的距距离离，记作作d。62连通通图定定义(P129定义7.30)设D为一个有向一个有向图。若若D的基的基图是是连通通图，则称称D是是弱弱连通通图，简称称为连通通图。若。若vi,vj V，vivj与与vjvi至至少成立其一，少成立其一，则称称D是是单向向连通通图。若均有若均有vi vj，则称称D是是强连通通图。强连通图强连通图单向连通图单向连通图弱连通图弱连通图63强连通通图与与单向向连通通图的判定定理的判定定理定

27、理定理7.22 设有向有向图D，Vv1,v2,vn。D是是强连通通图当当且且仅当当D中中存存在在经过每每个个顶点点至至少少一次的回路。一次的回路。64第八章第八章 E E图和和H H图65欧拉欧拉图n一笔画问题一笔画问题66欧拉欧拉图abdccabdn哥尼斯堡七桥问题哥尼斯堡七桥问题67欧拉欧拉图(P132)(P132)n半半欧欧拉拉图图：假假如如G G的的一一条条简简洁洁通通路路含含有有G G中中全全部部的的边边，则则称称G G是是半半欧欧拉拉图图，该该通通路路称称为为欧欧拉通路。拉通路。n欧欧拉拉图图：假假如如G G的的一一条条回回路路含含有有G G中中全全部部的的边边，则则称称G G是是

28、欧欧拉拉图图（E E图图），该该回回路路称称为为欧欧拉拉回回路路68n有向欧拉有向欧拉图、有向半欧拉、有向半欧拉图可可类似定似定义欧拉图欧拉图69欧拉欧拉图(P132)(P132)n定理定理8.1 8.1 设设G G是无向连通图，则以下等价是无向连通图，则以下等价nG G是欧拉图是欧拉图nG G中全部顶点的度都为偶数。中全部顶点的度都为偶数。nG G是若干个边不重的圈的并。是若干个边不重的圈的并。n定理定理8.2 8.2 无向连通图无向连通图G G是半欧拉图当且仅当是半欧拉图当且仅当G G中中恰有两个奇度顶点。恰有两个奇度顶点。70欧拉欧拉图(P134)(P134)n定理定理8.3 8.3 有

29、向图有向图D D是欧拉图当且仅当是欧拉图当且仅当D D是强连通是强连通的且每个顶点的入度都等于出度。的且每个顶点的入度都等于出度。n定理定理8.4 8.4 有向图有向图D D是半欧拉图当且仅当是半欧拉图当且仅当D D是单向是单向连通的，且连通的，且D D中恰有两个奇度顶点，其中一个中恰有两个奇度顶点，其中一个的入度比出度大的入度比出度大1 1，另一个的出度比入度大，另一个的出度比入度大1 1，而其余顶点的入度都等于出度。而其余顶点的入度都等于出度。71求欧拉求欧拉图中欧拉回路的算法中欧拉回路的算法(P134)Fleury算法，能不走算法，能不走桥桥就不走就不走桥桥(1)任取任取v0V(G)，令

30、，令P0v0。(2)设设Piv0e1v1e2eivi已已经经行遍，按下面方法行遍，按下面方法来从来从 E(G)-e1,e2,ei中中选选取取ei+1：(a)ei+1与与vi相关相关联联；(b)除非无除非无别别的的边边可供行遍，否可供行遍，否则则ei+1不不应应当当为为GiG-e1,e2,ei中的中的桥桥。(3)当当(2)不能再不能再进进行行时时，算法停止。，算法停止。72求欧拉回路的算法求欧拉回路的算法n求欧拉回路的算法（一）：扩充回路法求欧拉回路的算法（一）：扩充回路法n从从G G中一点动身找一回路中一点动身找一回路C1C1n假如假如G-C1G-C1不是空图不是空图,则则C1C1中必有点中必

31、有点v v和和G-C1G-C1中中某边相连某边相连n从从v v动身在动身在G-C1G-C1中找一回路中找一回路C2C2n用用C2C2来代替来代替v v使使C1C1中含有更多的边中含有更多的边n重复这一过程便得一个欧拉回路重复这一过程便得一个欧拉回路73应用用n磁鼓定位磁鼓定位74磁鼓定位磁鼓定位75磁鼓定位磁鼓定位76磁鼓定位磁鼓定位77磁鼓定位磁鼓定位78哈密哈密顿图(P137)n18591859年年,哈密尔顿哈密尔顿:周游世界问题周游世界问题79哈密哈密顿图 定定义8.2 经过图（有向（有向图或无向或无向图）中全部）中全部顶点一次且点一次且仅一次的通路称一次的通路称为哈密哈密顿通路。通路。

32、经过图中全部中全部顶点一次且点一次且仅一次的回路称一次的回路称为哈哈密密顿回路。具有哈密回路。具有哈密顿回路的回路的图称称为哈密哈密顿图，具有哈密，具有哈密顿通路但不具有哈密通路但不具有哈密顿回路的回路的图称称为半哈密半哈密顿图。80定理定理定理定理8.6 设无向无向图G是哈密是哈密顿图，对于于随意随意V1 V，且，且V1，均有，均有p(G-V1)|V1|其中，其中，p(G-V1)为G-V1的的连通分支数。通分支数。81推推论 推推论 设无向无向图G是半哈密是半哈密顿图，对于于随意的随意的V1 V且且V1，均有，均有 p(G-V1)|V1|+1 82哈密哈密尔顿图n推断下列图是否为推断下列图是

33、否为H H图。图。83定理定理定理定理8.7 设G是是n(n 2)阶无向无向简洁图，若，若对于于G中随意不相中随意不相邻的的顶点点vi,vj，均有，均有d(vi)+d(vj)n-1则G中存在哈密中存在哈密顿通路。通路。84推推论推推论 设G为n(n3)阶无向无向简洁图，若，若对于于G中随中随意两个不相意两个不相邻的的顶点点vi,vj，均有，均有 d(vi)+d(vj)n(15.2)则G中存在哈密中存在哈密顿回路，从而回路，从而G为哈密哈密顿图。85定理定理定理定理8.8 设u,v为n阶无向无向图G中两个不相中两个不相邻的的顶点，且点，且d(u)+d(v)n，则G为哈密哈密顿图当且当且仅当当G(

34、u,v)为哈密哈密顿图(u,v)是加的新是加的新边)。定理定理8.9 竞赛图是半是半H图。定理定理8.10 强连通的通的竞赛图是是H图。86例例例例 在在某某次次国国际会会议的的预备会会议中中，共共有有8人人参参与与，他他们来来自自不不同同的的国国家家。已已知知他他们中中任任何何两两个个无无共共同同语言言的的人人中中的的每每一一个个，与与其其余余有有共共同同语言言的的人人数数之之和和大大于于或或等等于于8，问能能否否将将这8个个人人排排在在圆桌旁，使其任何人都能与两桌旁，使其任何人都能与两边的人交的人交谈。87定理定理定定理理8.9 若若D为n(n2)阶竞赛图，则D中中具具有有哈哈密密顿通路。

35、通路。定理定理8.10 强连通的通的竞赛图是哈密是哈密顿通通图。88第九章第九章 树89树的定的定义(144)(144)n树树：连连通通无无回回路路的的无无向向图图。树树中中的的1 1度度点点称称为为树叶树叶，其余称为，其余称为分支点分支点。90树的定的定义91树的定的定义n定定理理9.19.1：假假如如G G有有n n 2 2个个顶顶点点，m m条条边边，则则以以下等价：下等价：nG G是树，即无回路、连通。是树，即无回路、连通。nG G中任何两点间恰有一条路径中任何两点间恰有一条路径nG G无回路且无回路且m=n-1m=n-1nG G连通且有连通且有m=n-1m=n-1nG G连通且每条边

36、都是桥连通且每条边都是桥nG G无无回回路路且且添添加加任任何何一一条条边边恰恰好好构构成成一一个个含含新边的圈。新边的圈。n定理定理 非平凡树中至少有两片树叶。非平凡树中至少有两片树叶。92树的定的定义n例例 画出全部画出全部6 6阶非同构的树。阶非同构的树。n例例 7 7阶阶树树中中有有3 3片片树树叶叶和和1 1个个3 3度度点点，其其余余3 3个个顶顶点点的的度度数数均均无无1 1和和3 3，试试画画出出满满足足要要求求的的全全部非同构的树。部非同构的树。93树的定的定义n生生成成树树(P146(P146定定义义9.2)9.2)G=G=，假假如如树树T T是是G G的的生生成成子子图图

37、，则则称称T T是是G G的的生生成成树树。T T中中的的边边称称为为T T的的树树枝枝。称称G-TG-T为为T T的的余余树树，记记为为 。余余树树中的边称为中的边称为T T的弦。的弦。94树的定的定义n定定理理9.3 9.3 无无向向图图G G有有生生成成树树当当且且仅仅当当G G是是连连通通图。图。n例例 7 7阶阶树树中中有有3 3片片树树叶叶和和1 1个个3 3度度点点，其其余余3 3个个顶顶点点的的度度数数均均无无1 1和和3 3，试试画画出出满满足足要要求求的的全全部非同构的树。部非同构的树。95推论推论1 1G G为为n n阶阶m m条条边边的的无无向向连连通通图图，则则mnm

38、n 1 1。推论推论2 2 设设G G是是n n阶阶m m条条边边的的无无向向连连通通图图，T T为为G G的的生生成成树树，则则T T的的余余树树中中含含有有m-n+1m-n+1条条边边（即即T T有有m-n+1m-n+1条条弦弦）。推推论论3 3 设设T T是是连连通通图图G G的的一一棵棵生生成成树树，T T为为T T的的余余树，树，C C为为G G 中随意一个圈，则中随意一个圈，则E(T)E(C)E(T)E(C)推推论论 96定定理理9.4 9.4 设设T T为为无无向向连连通通图图G G中中一一棵棵生生成成树树，e e为为T T的的随随意意一一条条弦弦，则则TeTe中中含含G G中中

39、只只含含一一条条弦弦其其余余边边均均为为树树枝枝的的圈圈，而而且且不不同同的的弦弦对对应应的圈也不同。的圈也不同。定理定理 97定定义9.3 设T是是n阶m条条边的的无无向向连通通图G的的一一棵棵生生成成树，设e 1,e 2,e m n+1为T的的弦弦。设Cr为T添添加加弦弦e r产生生的的G中中只只含含弦弦e r，其其余余边均均为树枝枝的的圈圈，称称Cr为G的的对应T的的弦弦e r的的基基本回路本回路或或基本圈基本圈，r1,2,m n+1。称称C1,C2,Cm n+1为G对应T的的基基本本回回路路系系统，称称m n+1为G的圈秩的圈秩，记作作(G)。基本回路与基本回路系基本回路与基本回路系统

40、统的定的定义义98n求基本回路求基本回路设弦弦e=(u,v)，先先求求T中中u到到v的的路路径径(u,v)，再再并上弦并上弦e，即得即得对应e的基本回路。的基本回路。基本回路与基本回路系基本回路与基本回路系统统的定的定义义99无向连通图无向连通图G的圈秩与生成树的选取无关，但不同生成树对的圈秩与生成树的选取无关，但不同生成树对应的基本回路系统可能不同。应的基本回路系统可能不同。求下图中的求下图中的基本回路系统。基本回路系统。举举例例100定理定定理理9.5 设T是是连通通图G的的一一棵棵生生成成树，e为T的的树枝枝，则G中中存存在在只只含含树枝枝e，其其余余边都都是是弦弦的的割集，且不同的割集

41、，且不同的树枝枝对应的割集也不同。的割集也不同。101基本割集与基本割集系统的定义定定义9.4 设T是是n阶连通通图G的的一一棵棵生生成成树，e 1,e 2,e n 1为T的的树枝枝，Si是是G的的只只含含树枝枝e i的的割割集集，则称称Si为G的的对应于于生生成成树T由由树枝枝e i生成的基本割集生成的基本割集，i1,2,n 1。称称S1,S2,Sn 1为G对应T的的基基本本割割集集系系统，称称n 1为G的割集秩的割集秩，记作作(G)。102基本割集与基本割集系统的定义n求基本割集求基本割集设e 为生生成成树T的的树枝枝，T e 为两两棵棵小小树T1与与T2，令令Se e|e E(G)且且e

42、的的两两个个端端点点分分别属于属于T1与与T2，则Se 为e 对应的基本割集。的基本割集。103求下图中的求下图中的基本基本割集割集系统。系统。举举例例104最小生成最小生成树6241241GT:权为7n最最小小生生成成树树：G G是是带带权权图图，G G的的权权值值最最小小的的生生成成树树称称为为G G的的最最小小生生成成树树。（树树的的权权值值指指它它全全部的边的权值之和）部的边的权值之和）105最小生成最小生成树nKruskalKruskal算法算法nT=T=;nwhile(|T|n-1&Ewhile(|T|n-1&E)ne=Ee=E中最短边中最短边nE=E-eE=E-en若若T+eT+

43、e无回路，则无回路，则T=T+eT=T+en若若|T|n-1,|T|n-1,则失败退出，否则成功退出。则失败退出，否则成功退出。106最小生成最小生成树nPrimPrim算法（设算法（设G G连通连通,V,V是顶点集，是顶点集，v1v1V)V)1.1.t=v1;T=t=v1;T=;U=t;U=t;2.2.while(Uwhile(U V)V)a.a.w(t,u)=minw(t,v)|vw(t,u)=minw(t,v)|vV-UV-Ub.b.T=T+e(t,u)T=T+e(t,u)c.c.U=U+uU=U+ud.d.for(vV-U)w(t,v)=minw(t,v),w(u,v)for(vV-U

44、)w(t,v)=minw(t,v),w(u,v)3.3.输出输出T T。107第十章第十章 图的矩的矩阵表示表示108有向有向图的关的关联矩矩阵定定义 10.1 设有向有向图D中无中无环，Vv1,v2,vn，Ee1,e2,em，令令 则称则称(mij)nm为为D的的关联矩阵关联矩阵，记作，记作M(D)。109有向有向图的关的关联矩矩阵110图的矩的矩阵表示表示定定义10.2 设无向无向图G，Vv1,v2,vn，Ee1,e2,em，令令mij为顶点点vi与与边ej的关的关联次数，次数，则称称(mij)nm为G的的关关联矩矩阵，记作作M(G)。111有向有向图的的邻接矩接矩阵定定义10.4 设有向

45、有向图D，Vv1,v2,vn，Ee1,e2,，em，令令aij(1)为顶点点vi邻接到接到顶点点vj边的条数，称的条数，称(aij(1)nn为D的的邻接矩接矩阵，记作作A(D)，或或简记为A。112定理定理 设是有向是有向图，u1,u2,un，（mij)是的是的邻接矩接矩阵，则矩矩阵k（k=1,2,3)中中第第i行第行第j列的元素，等于从列的元素，等于从ui到到uj长度度为k的通路的条的通路的条数。数。113例：求图例：求图D中中u3到到u4长度为长度为3的的通路数通路数M2=M3=M1=u3到到u4长度为长度为3的的通路数有通路数有2条。条。114有向有向图的可达矩的可达矩阵定定义10.5

46、设D为有向有向图。Vv1,v2,vn，令令 pij1 1 vi 可达可达 vj0 0 否则否则称称(pij)nn为为D的的可达矩阵可达矩阵，记作，记作P(D)，简记为简记为P。115第十一章第十一章 平面平面图116平面平面图(P165)(P165)K4abcdK4abcd定义定义11.1 G可嵌入曲面可嵌入曲面S：假如图：假如图G能以这样的方式能以这样的方式画在曲面画在曲面S上，即除顶点处外无边相交。上，即除顶点处外无边相交。G是可平面图或平面图：若是可平面图或平面图：若G可嵌入平面。可嵌入平面。G的平面嵌入：画出的无边相交的平面图。的平面嵌入：画出的无边相交的平面图。非平面图：无平面嵌入的

47、图。非平面图：无平面嵌入的图。117平面平面图K5K5nK K5 5是否为平面图？是否为平面图？118平面平面图abcdefK3,3bcdefK3,3nK K3,33,3是否为平面图？是否为平面图？119平面平面图f1f2f3无穷面n面（域）：由闭曲线分割而成的区域。面（域）：由闭曲线分割而成的区域。n无穷面：面积为无穷的面。无穷面：面积为无穷的面。n边界：包围某个面的各条边称为该面的边界。边界：包围某个面的各条边称为该面的边界。n面的次数：该面的边界的长度。面的次数：该面的边界的长度。120平面平面图n定定理理 若若G G为为平平面面图图，则则在在G G中中加加平平行行边边或或环环所所得图还

48、是平面图。得图还是平面图。n定定理理11.2 11.2 平平面面图图G G中中全全部部面面的的次次数数之之和和等等于于边数边数m m的两倍。的两倍。K4abcd121极大平面极大平面图n定定义义11.3 11.3 若若在在简简洁洁平平面面图图G G中中的的随随意意两两个个不不相相邻邻的的顶顶点点之之间间加加一一条条新新边边所所得得图图为为非非平平面面图，则称图，则称G G为极大平面图。为极大平面图。122极大平面极大平面图n定理定理 极大平面图是连通的。极大平面图是连通的。n定定理理11.4 11.4 设设G G为为n(nn(n 3)3)阶阶简简洁洁连连通通的的平平面面图图，G G为为极极大大

49、平平面面图图当当且且仅仅当当G G的的每每个个面面的的次次数数均均为为3 3。123EulerEuler公式公式n定定理理11.6(Euler11.6(Euler公公式式-1750-1750）：连连通通平平面面图图G G有有n n个顶点，个顶点，m m条边和条边和r r个面，则个面，则n-m+r=2n-m+r=2。n定理定理11.711.7：平面图：平面图G G有有p p分图，则分图，则n-m+r=p+1n-m+r=p+1。n定定理理11.811.8：连连通通平平面面图图G G中中每每个个面面的的次次数数至至少少为为L(L2)L(L2)，则有，则有m m(n-2)L/(L-(n-2)L/(L-

50、2)2)。n推论：推论：K K5 5和和K K3 3，3 3都不是平面图。都不是平面图。124极大平面极大平面图定理定理11.1011.10：假如：假如G G是连通平面图，有是连通平面图，有n(2)n(2)个点，个点，m m条边，则条边，则m m 3n-63n-6。定理定理11.1111.11：假如：假如G G是极大连通平面图，有是极大连通平面图，有n(2)n(2)个点，个点，m m条边，则条边，则m=3n-6m=3n-6。定理定理11.1211.12：简洁平面图：简洁平面图G G的最小度的最小度5 5。125非平面非平面图n定定义义11.6 11.6 同同胚胚：假假如如图图H H可可以以通通