文档介绍：第8章 图论
图的基本概念
路径和回路
图的矩阵表示
二部图
平面图
树
有向树
运输网络
问题是要从这四块陆地中任何一块开始，通过每一座,…,n2)。
由上一定理得
因为次数为偶数的各结点次数之和为偶数。所以
前一项次数为偶数;若n2为奇数,则第二项为奇数,两项
之和将为奇数,但这与上式矛盾。故n2必为偶数。证毕。
编辑ppt
―5各结点的次数均相同的图称为正则图,各
结点的次数均为k时称为k―正则图。
下图所示的称为彼得森(Petersen)图,是3―正则图。
图 ―5
编辑ppt
图的同构
=〈V,E〉和G′=〈V′,E′〉是两个图,
若存在从V到V′的双射函数Φ,使对任意a、b∈V,
［a,b]∈E当且仅当［Φ(a),Φ(b)］∈E′,并且
［a,b］和［Φ(a),Φ(b)］有相同的重数,则称G和G′
是同构的。
上述定义说明,两个图的各结点之间,如果存在一一对
应关系,而且这种对应关系保持了结点间的邻接关系
(在有向图时还保持边的方向)和边的重数,则这两个图
是同构的,两个同构的图除了顶点和边的名称不同外实
际上代表同样的组合结构。
编辑ppt
例2 (a)、(b)两图是同构的。因为可作映射:g(1)=v3,
g(2)=v1,g(3)=v4,g(4)=v2。在这映射下,边〈1,3〉,
〈1,2〉,〈2,4〉和〈3,4〉分别映射到〈v3,v4〉,〈
v3,v1〉,〈v1,v2〉和〈v4,v2〉,而后面这些边又是(b)中
仅有的边。
图 ―6
编辑ppt
两图同构的必要条件:(1)结点数相等;(2)边数相等;(3)度
数相同的结点数相等。
但这不是充分条件。例如下图中(a)、(b)两图虽然满足以
上3条件,但不同构。(a)中的x应与(b)中的y对应,因为次
数都是3。但(a)中的x与两个次数为1的点u,v邻接,而(b)
中的y仅与一个次数为1的点w邻接。
图 ―7
编辑ppt
图的运算
图的常见运算有并、交、差、环和等,现分别定义于下:
―7设图G1=〈V1,E1〉和图G2=〈V2,E2〉
(1)G1与G2的并,定义为图G3＝〈V3,E3〉, 其中V3=V1∪V2,E3=E1∪E2,记为G3=G1∪G2。
(2)G1与G2的交,定义为图G3＝〈V3,E3〉, 其中V3=V1∩V2,E3=E1∩E2,记为G3=G1∩G2。
(3)G1与G2的差,定义为图G3＝〈V3,E3〉,记为G3=G1-G2。 其中E3=E1-E2,V3=(V1-V2)∪{E3中边所关联的顶点}。 (4)G1与G2的环和,定义为图G3＝〈V3,E3〉, G3=(G1∪G2)-(G1∩G2),记为G3=G1G2。
编辑ppt
除以上4种运算外,还有以下两种操作:
(1) 删去图G的一条边e; (2)删去图G的一个结点v。它的实际意义是删去结点v和与v关联的所有边。
图 ―9
编辑ppt
子图与补图
―8设G=〈V,E 〉和G′=〈V′,E′〉是两个图。
(1) 如果V′ V和E′ E,则称G′是G的子图。如果
V′ V和E′ E,则称G′ G的真子图。(注意:“G′
是图”已隐含着“E′中的边仅关联V′中的结点”的
意义。)
(2) 如果V′=V和E′ E,则称G′为G的生成子图。
(3) 若子图G′中没有孤立结点,G′由E′唯一确定,则
称G′为由边集E′导出的子图。
(4)若在子图G′中,对V′中的任意二结点u、v,当
［u,v］∈E时有［u,v］∈E′,则G′由V′唯一确定,
此时称G′为由结点集V′导出的子图。
编辑ppt
图 ―10
编辑ppt
―9在n个结点的有向图G=〈V,E〉中,如果E=V×V,
则称G为有向完全图;在n个结点的无向图G=〈V,E〉中,如
果任何两个不同结点间都恰有一条边,则称G为无向完全
图,记为Kn。
―11是4个结点的有向完全图和无向完全图的图示。
-11
编辑ppt
―10 设线图G=〈V,E〉有n个顶点,线图H =
〈V,E′〉也有同样的顶点,而E′是由n个顶点的完全
图的边删去E 所得,则图H称为图G的补图,记为 ,显然, 。
编辑ppt
路径和回路
路径和回路
―1在有向图中,从顶点v0到顶点vn的一 条路径是图的一个点边交替序列（v0e1v1e2v2…envn）,其中