资源描述：
《离散数学图论（128版）课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第8章图论8.1图的基本概念8.2路径和回路8.３图的矩阵表示8.４二部图8.5平面图8.6树8.7有向树8.8运输网络问题是要从这四块陆地中任何一块开始，通过每一座桥正好一次，再回到起点。欧拉在1736年解决了这个问题。判定法则：如果通奇数座桥的地方不止两个，那么满足要求的路线便不存在了。如果只有两个地方通奇数座桥，则可从其中任何一地出发找到所要求的路线。若没有一个地方通奇数座桥，则从任何一地出发，所求的路线都能实现定义8.1―1一个图G是一个三重组〈V(G),E(G),ΦG〉,其中V(G)是一个非空
2、的结点(或叫顶点)集合,E(G)是边的集合,ΦG是从边集E到结点偶对集合上的函数。一个图可以用一个图形表示。例1设G=〈V(G),E(G),ΦG〉,其中V(G)={a,b,c,d},E(G)={e1,e2,e3,e4,e5,e6,e7},ΦG(e1)=(a,b),ΦG(e2)=(a,c),ΦG(e3)=(b,d),ΦG(e4)=(b,c),ΦG(e5)=(d,c),ΦG(e6)=(a,d),ΦG(e7)=(b,b) 则图G可用图8.1―1表示。8.1图的基本概念8.1.1图定义中的结点偶对可以是有序的,
3、也可以是无序的。若边e所对应的偶对〈a,b〉是有序的,则称e是有向边。有向边简称弧,a叫弧e的始点,b叫弧e的终点,统称为e的端点。称e是关联于结点a和b的,结点a和结点b是邻接的。若边e所对应的偶对(a,b)是无序的,则称e是无向边。无向边简称棱,除无始点和终点的术语外,其它术语与有向边相同。每一条边都是有向边的图称为有向图,第三章中的关系图都是有向图的例子。每一条边都是无向边的图称为无向图；如果在图中一些边是有向边,而另一些边是无向边,则称这个图是混合图。我们仅讨论有向图和无向图,且V(G)和E(G
4、)限于有限集合。约定用〈a,b〉表示有向边,(a,b)表示无向边,既表示有向边又表示无向边时用［a,b］。有向图和无向图也可互相转化。例如,把无向图中每一条边都看作两条方向不同的有向边,这时无向图就成为有向图。又如,把有向图中每条有向边都看作无向边,就得到无向图。这个无向图习惯上叫做该有向图的底图。在图中,不与任何结点邻接的结点称为弧立结点；全由孤立结点构成的图称为零图。关联于同一结点的一条边称为自回路；自回路的方向不定。自回路的有无不使有关图论的各个定理发生重大变化,所以有许多场合都略去自回路。在有向
5、图中,两结点间(包括结点自身间)若同始点和同终点的边多于一条,则这几条边称为平行边。在无向图中,两结点间(包括结点自身间)若多于一条边,则称这几条边为平行边。两结点a、b间互相平行的边的条数称为边［a,b］的重数。仅有一条时重数为1,无边时重数为0。定义8.1―2含有平行边的图称为多重图。 非多重图称为线图。无自回路的线图称为简单图。在图8.1―3中,(a)、(b)是多重图,(c)是线图,(d)是简单图,关系图都是线图。图8.1―3定义8.1―3赋权图G是一个三重组〈V,E,g〉或四重组〈V,E,f,g
6、〉,其中V是结点集合,E是边的集合,f是定义在V上的函数,g是定义在E上的函数。右图给出一个赋权图。V={v1,v2,v3}E={e1,e2}={(v1,v2),(v2,v3)}f(v1)=5,f(v2)=8,f(v3)=11g(e1)=4.6,g(e2)=7.58.1.2结点的次数定义8.1―4在有向图中,对于任何结点v,以v为始点的边的条数称为结点v的引出次数(或出度),记为deg+(v);以v为终点的边的条数称为结点v的引入次数(或入度),记为deg-(v);结点v的引出次数和引入次数之和称为结点
7、v的次数(或度数),记作deg(v)。在无向图中,结点v的次数是与结点v相关联的边的条数,也记为deg(v)。孤立结点的次数为零。定理8.1―1设G是一个(n,m)图,它的结点集合为V={v1,v2,…,vn},则证因为每一条边提供两个次数,而所有各结点次数之和为m条边所提供,所以上式成立。在有向图中,上式也可写成:定理8.1―2在图中,次数为奇数的结点必为偶数个。证设次数为偶数的结点有n1个,记为(i=1,2,…,n1)。 次数为奇数的结点有n2个,记为(i=1,2,…,n2)。由上一定理得因为次数为
8、偶数的各结点次数之和为偶数。所以前一项次数为偶数;若n2为奇数,则第二项为奇数,两项之和将为奇数,但这与上式矛盾。故n2必为偶数。证毕。图8.1―5定义8.1―5各结点的次数均相同的图称为正则图,各结点的次数均为k时称为k―正则图。下图所示的称为彼得森(Petersen)图,是3―正则图。8.1.3图的同构定义8.1.6设G=〈V,E〉和G′=〈V′,E′〉是两个图,若存在从V到V′的双射函数Φ,使对任意a、b∈V,［a,b∈E当且仅当［Φ
