14.1 无向图 有向图概念

1、1 图论图论 2图论部分前言图论部分前言 n图论图论(Graph theory)是一门古老而年轻的学科是一门古老而年轻的学科.n古老古老:早在早在18世纪世纪,学者们便运用图为工具来解决学者们便运用图为工具来解决一些实际问题一些实际问题.n年轻年轻:直到直到20世纪中后期世纪中后期,尤其是随着计算机科学尤其是随着计算机科学与技术的发展与技术的发展,图的理论和应用研究逐渐得到重视图的理论和应用研究逐渐得到重视,图论作为一个数学分支图论作为一个数学分支,才确立了它的地位才确立了它的地位.31 图论的起源n图论的起源可以追溯到1736年,n瑞士数学家欧拉(Eular)(1707-1783)成功解决了

2、当时很有名的哥尼斯堡七桥问题,n并发表了第一篇图论论文,欧拉成为图论的创始人.哥尼斯堡位于立陶宛的普雷格尔河畔河中有有两个小岛和七座桥.居民们提出的问题是:可否从城市或岛上的可否从城市或岛上的一点出发一点出发,经由七桥经由七桥,并且只经过每座桥一次并且只经过每座桥一次,然后回到原地然后回到原地.4n用结点表示两岸和小岛,用结点间的连线表示桥. 问题转化为:是否能从某一点出发经过每条线段恰好一次,然后再回到出发点. 最后,欧拉论证了七桥问题无解.n欧拉将该问题抽象下右图.抽象5 可以看到b)图是a)图的抽象,人们不注重结点的位置边的长短形状.只关心结点与边的联结关系. 这与几何学中的图形有本质区

3、别.a)b)像这样由结点和边组成的离散结构就是本章讨论的图.6图论的应用n图论广泛应用于建立和处理离散对象及其关系, 如:关系(关系图)网络运筹规划等在计算机科学领域:算法设计操作系统网络理论,都有广泛应用.其他领域:生物学经济控制论运筹学等7 第第5 5章章 图的基本概念图的基本概念 5.1 无向图及有向图无向图及有向图8基本概念基本概念无序积无序积A B :用来表示无向图的边用来表示无向图的边.设设A,B为两集合为两集合, A B=(x,y) | x A且且y B A B为为A与与B的无序积的无序积, (x,y)叫无序对叫无序对.例如:设A=a1,a2,B=b1,b2,则 A&B=(a1,

4、b1),(a1,b2),(a2,b1),(a2,b2) A&A=(a1,a1),(a1,a2),(a2,a2)注意与笛卡儿积的区别注意与笛卡儿积的区别AB=,AA=,跟有序对不同跟有序对不同,对无序对对无序对,无论无论x,y是否相同是否相同 ,有有(x,y)=(y,x). 如如: (3,5)=(5,3)9多重集合多重集合: 元素可以重复出现的集合元素可以重复出现的集合. 在多重集合中在多重集合中: 1,1,2,2,3 1,2,3在集合论中在集合论中,同一个元素在集合中多次出现被同一个元素在集合中多次出现被认为是一个元素认为是一个元素,如如: 1,1,2,2,3=1,2,3多重集合的概念引入是为

5、了表示图的平行边多重集合的概念引入是为了表示图的平行边.10无向图无向图定义定义 一个无向图一个无向图G是一个二元组是一个二元组,即即G=, 其中其中(1) V是一个非空集合是一个非空集合,称为称为G的顶点集的顶点集(vertex)，V中元素称为中元素称为顶点或结点顶点或结点.(2) E为无序积为无序积V V的一个多重子集的一个多重子集(元素可以重元素可以重复出现复出现)，称为，称为G的边集的边集,E中元素称为中元素称为无向边无向边，简称简称边边(edge).用无序对用无序对(a,b)表示表示连接顶点a和顶点b的边,(a,b)=(b,a).例如例如, G=如图所示如图所示, 其中其中V=v1,

6、 v2, ,v5, E=(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) 注意注意:连接连接v2,v3的边有两条的边有两条. 无向图的边没有方向.11有向图有向图定义定义 有向图有向图D=, 其中其中(1) V是是顶点集顶点集, 元素也称为元素也称为顶点顶点(2) E是边集是边集,为笛卡儿积为笛卡儿积V V的多重子集，其元素的多重子集，其元素 称为称为有向边有向边，简称，简称边边.用有序对用有序对表示表示顶点a指向顶点b的边,注:在有向图中,有向边,是有方向方向的, 箭头从a指向b,表示a是起点,b是终点.右图是有向图，

7、试写出它的右图是有向图，试写出它的V和和E V=a,b,c,dE=, 注意注意:顶点顶点a指向指向b的边的边有两条有两条, ,是两条方向相反的边是两条方向相反的边.12为了表示的方便为了表示的方便,边的还有另一种表示法边的还有另一种表示法:用用ek表示表示无向边或有向边无向边或有向边. 如下图如下图e1=(v1,v1), e2=(v1,v2)E=e1,e2,e3,e4,e5,e6,e7E=e1,e2,e3,e4,e5,e6,e7边的另一种表示方法:13相关概念与规定相关概念与规定nn 阶图阶图: n个顶点的图个顶点的图n有限图有限图: V, E都是有穷集合的图都是有穷集合的图,本书只讨本书只讨

8、论有限图论有限图n零图零图: 边集边集E=n平凡图平凡图: 1 阶零图阶零图n空图空图: 顶点集顶点集V=D(Directed graph)表示有向图表示有向图,也常用也常用G泛指无向图和有向图泛指无向图和有向图,通常用通常用G(Graph)表示无向图表示无向图.145.5例题分析: p134n例5.7 给定图的集合表示,画出图形.152 2 顶点和边的关系顶点和边的关系- -关联关联定义定义 设设ek=(vi, vj)是无向图是无向图G=的一条的一条边边, 称称vi, vj为为ek的的端点端点, ek与与vi ( vj)关联关联. 若若vi vj, 则称则称ek与与vi ( vj)的的关联次

9、数为关联次数为1; 若若vi = vj, 则称则称ek为为环环, 此时称此时称ek与与vi 的的关关联次数为联次数为2; 若若vi不是不是ek端点端点, 则称则称ek与与vi 的的关联次数关联次数为为0. 无边关联的顶点称作无边关联的顶点称作孤立点孤立点.ekvivj问:e1与v1的关联次数是多少e2与v1和v2的关联次数是多少?16对对无向图无向图G=, vi,vj V, ek,el E, 若若(vi,vj)组成一条边组成一条边, 则称则称vi,vj相邻相邻(点相邻点相邻); v1和v2点相邻 若若ek,el至少有一个公共端点至少有一个公共端点, 则称则称ek,el相邻相邻(边相邻边相邻).

10、 e2和e3边相邻.相邻相邻(点相邻，边相邻，邻接到）点相邻，边相邻，邻接到）对对有向图有向图有类似定义有类似定义. 设设ek= vi,vj 是有是有向图的一条边向图的一条边,又称又称vi是是ek的的始点始点, vj是是ek的的终点终点, vi邻接到邻接到vj, vj邻接于邻接于vi. a邻接于邻接于b, a是起点是起点,b是终点是终点17邻域和关联集邻域和关联集 )(vN)(vD )()(vvNvNDD )(vD )()()(vvvNDDD 设无向图设无向图G, v V(G) v的邻域的邻域 N(v)=u|u V(G) (u,v) E(G) u v v的闭邻域的闭邻域 = N(v)v v的关

11、联集的关联集 I(v)=e|e E(G) e与与v关联关联设有向图设有向图D, v V(D) v的后继元集的后继元集 =u|u V(D) E(G) u v v的先驱元集的先驱元集 =u|u V(D) E(G) u v v的邻域的邻域 v的闭邻域的闭邻域18顶点的度数顶点的度数(Degree)-(Degree)-点作为边的端点次数之和点作为边的端点次数之和 设设G=为无向图为无向图, v V, v的度数的度数(度度) d(v): v作为边的端点次数之和作为边的端点次数之和 悬挂顶点悬挂顶点: 度数为度数为1的顶点的顶点 悬挂边悬挂边: 与悬挂顶点关联的边与悬挂顶点关联的边 G的最大度的最大度 (

12、G)=maxd(v)| v V G的最小度的最小度 (G)=mind(v)| v V例如例如 d(v1)=4, d(v2)=4, d(v3)=2, d(v4)=1, d(v5)=3, (G)=4, (G)=1, v4是悬挂顶点是悬挂顶点, e7是悬挂边是悬挂边, e1是环是环 19有向图有向图的度数的度数 设设D=为有向图为有向图, v V, v的出度的出度d+(v): v作为边的始点次数之和作为边的始点次数之和 v的入度的入度d (v): v作为边的终点次数之和作为边的终点次数之和 v的度数的度数(度度) d(v): v作为边的端点次数之和作为边的端点次数之和 d(v)= d+(v)+ d-

13、(v)D的最大出度的最大出度 +(D), 最小出度最小出度 +(D) 最大入度最大入度 (D), 最小入度最小入度 (D) 最大度最大度 (D), 最小度最小度 (D) 例如例如 d+(a)=4, d-(a)=1, d(a)=5, d+(b)=0, d-(b)=3, d(b)=3, +(D)=4, +(D)=0, (D)=3, (D)=1, (D)=5, (D)=3. 20顶点度数和边数的关系顶点度数和边数的关系握手定理握手定理n握手定理是图论中的基本定理.n它是欧拉在1736年给出的n主要包括两个定理,一个推论.要求能熟练应用.21握手定理握手定理 定理定理1 任意无向图和有向图的所有顶点度

14、数之和都任意无向图和有向图的所有顶点度数之和都等于边数的等于边数的2倍倍. 上图度数和为上图度数和为6,边为边为3定理定理2:有向图的所有顶点入度之和等于出度之和等有向图的所有顶点入度之和等于出度之和等于边数于边数.bc度数和:2+1+1=4边:2入度和:1=1=2出度和:2a顶点: a b c入度: 0 1 1出度: 2 0 022握手定理握手定理( (续续) ) 21)()()(2VvVvVvvdvdvdm 2)(Vvvd 1)(Vvvd推论推论 在任何无向图和有向图中，奇度顶点的个数必在任何无向图和有向图中，奇度顶点的个数必 为偶数为偶数.证证 设设G=为任意图，令为任意图，令 V1=v

15、 | v V d(v)为奇数为奇数 V2=v | v V d(v)为偶数为偶数则则V1V2=V, V1V2=，由握手定理可知，由握手定理可知 由于由于2m, 均为偶数，所以均为偶数，所以 也为偶数也为偶数, 但因为但因为V1中顶点度数都为奇数，所以中顶点度数都为奇数，所以|V1|必为偶数必为偶数. 23 设无向图设无向图G的顶点集的顶点集V=v1, v2, , vnG的度数列的度数列: d(v1), d(v2), , d(vn)如右图度数列如右图度数列:4,4,2,1,3(边数为边数为7)设有向图设有向图D的顶点集的顶点集V=v1, v2, , vn如右图如右图D度数列度数列:5,3,3,3

16、出度列出度列:4,0,2,1 入度列入度列:1,3,1,2(边数为边数为7)24n推论推论 在任何无向图和有向图中，奇度顶点在任何无向图和有向图中，奇度顶点的个数必为偶数的个数必为偶数.度数列度数列:4,4,2,1,3度数列度数列:5,3,3,325握手定理的应用握手定理的应用例例1 (3,3,3,4), (2,3,4,6,8)能成为图的度数列吗能成为图的度数列吗?解解 不可能不可能. 它们都有奇数个奇度数它们都有奇数个奇度数.例例2 一个无向图一个无向图G有有21条边条边,3个个4度顶点度顶点,其余都是其余都是3度顶点度顶点,问该图有几个顶点问该图有几个顶点? 解解 设设G有有n个个3度顶点

17、度顶点. 由握手定理由握手定理, 3 4+3 n=2 21解得解得 n=10, 该图有该图有13个顶点个顶点26握手定理的应用握手定理的应用(续续)例例3 证明不存在具有奇数个面且每个面都具有奇数证明不存在具有奇数个面且每个面都具有奇数条棱的多面体条棱的多面体.证证 用反证法用反证法. 假设存在这样的多面体假设存在这样的多面体, 作无向图作无向图G=, 其中其中V=v | v为多面体的面为多面体的面, E=(u,v) | u,v V u与与v有公共的棱有公共的棱 u v. 根据假设根据假设, |V|为奇数且为奇数且 v V, d(v)为奇数为奇数. 这与握这与握手定理的推论矛盾手定理的推论矛盾

18、.27n课堂练习-习题: 5.1 （1，2，3） 5.2 第1,2学时完28多重图与简单图多重图与简单图 定义定义 (1) (1) 在在无向图无向图中中, ,如果有如果有2 2条或条或2 2条以条以上的边关联同一对顶点上的边关联同一对顶点, , 则称这些边为则称这些边为平行边平行边, , 平行边的条数称为平行边的条数称为重数重数. .(2)(2)在有向图中在有向图中, ,如果有如果有2 2条或条或2 2条以上的边条以上的边具有相同的始点和终点具有相同的始点和终点, , 则称这些边为则称这些边为有向平行边有向平行边, , 简称简称平行边平行边, , 平行边的条平行边的条数称为数称为重数重数. .

19、(3) (3) 含平行边的图称为含平行边的图称为多重图多重图. .(4) (4) 既无平行边也无环的图称为既无平行边也无环的图称为简单图简单图. .注意注意: :简单图是极其重要的概念简单图是极其重要的概念 29多重图与简单图多重图与简单图( (续续) )例如例如e5和和e6 是平行边是平行边重数为重数为2不是简单图不是简单图e2和和e3 是平行边是平行边,重数为重数为2e6和和e7 不是平行边不是平行边(why?)不是简单图不是简单图30图的同构（了解）n用图解表示法来表示一个图时,结点在平面上排列的位置是没有限制的,因此,用一个事物之间的关系可能画出不同形状的图n这样的图叫同构(G1 G2

20、).设设A=a,b,c,R=,abcabc31同构同构的定义的定义定义定义 设设G1=, G2=为两个无向图为两个无向图,若存在双射函若存在双射函数数 f: V1V2, 使得对于使得对于任意任意的的vi,vj V1, (vi,vj) E1当且仅当当且仅当 (f(vi),f(vj) E2，并且并且, (vi,vj)与与 (f(vi),f(vj) 的重数相同，则称的重数相同，则称G1与与G2是是同构同构的，的，记作记作G1 G2. 例例: :v1v2v3v4v5u1u2u3u4u5设G1=,G2=,存在一个双射函数f: V1V2,使得使得f(vi)=ui.G1G232 如何判断图是否同构如何判断图

21、是否同构? ?同构的同构的必要条件必要条件, 但它们都不是充分条件但它们都不是充分条件: 边数相同，顶点数相同边数相同，顶点数相同 度数列相同度数列相同 对应顶点的关联集相同，等等对应顶点的关联集相同，等等若破坏必要条件，则两图不同构若破坏必要条件，则两图不同构 但这些都是必要条件但这些都是必要条件,不是充分条件不是充分条件.至今没有找到判断两个图是否同构的有效算法至今没有找到判断两个图是否同构的有效算法 ,还只能根据定义还只能根据定义来判断来判断 例例: :33例 :下图中G=(V,E),G=(V,E)是同构的.v1v2v3v4v5v6u1u2u3u4u5u6对任意vi,vj V,当当(vi

22、,vj) E时时,有有(ui,uj) E如如:(v1,v2) E,有有(u1,u2) Evi和ui一一对应.GG34n例例 下图中下图中G=（V，E）与）与G =（V ，E ）同）同构吗？构吗？n虽然有相同的结点,边数,但不满足同构的定义,原因是两个图边与结点的关联关系不同. G中度为中度为3的的4个结个结点构成一个长为点构成一个长为4的的回路回路,而而G中没有中没有.GG35课堂练习:n例例1 试画出试画出4阶阶3条边的所有非同构的无向简单图条边的所有非同构的无向简单图例例2 判断下述每一对图是否同构判断下述每一对图是否同构:度数列不同度数列不同不同构不同构3,4,3,22,5,2,336例

23、例2 (续续) (2)不同构不同构入入(出出)度列不同度列不同(3)度数列相同度数列相同但不同构但不同构为什么为什么?37完全图n定义定义 设G为n阶无向简单图,若G中每个顶点均与其余的n-1个顶点相邻,则称G为n阶无向完全图,记作Kn。 例例 下图分别给出了一个结点、二个结点、三个图分别给出了一个结点、二个结点、三个结点、四个结点和五个结点的完全图。结点、四个结点和五个结点的完全图。什么是简单图什么是简单图:不含平行边也不含环不含平行边也不含环.38n阶无向完全图阶无向完全图Kn性质性质: 边数边数m=n(n-1)/2, = =n-1右图为右图为5阶完全图阶完全图K5边数边数:m=5(5-1

24、)/2=10度数度数: = =439n阶有向完全图阶有向完全图: 每对顶点之间均有两条方向每对顶点之间均有两条方向相反的有向边的相反的有向边的n阶有向简单图阶有向简单图.性质性质: 边数边数m=n(n-1), = =2(n-1), += += -= -=n-1右图为3阶有向完全图.边数m=3(3-1)=6度数 = =2(3-1)=440n阶阶k正则图正则图: 设设G为为n阶无向简单图阶无向简单图,若对所有若对所有顶点顶点,均有均有d(v)=k,则称则称G为为n阶阶k正则图正则图.性质性质: 边数边数m=nk/2右图是右图是3 正则图正则图,也叫也叫彼得森图彼得森图. d(v)=3边数边数:m=

25、103/2=1541完全图与正则图完全图与正则图( (续续) ) (1) 为为5阶完全图阶完全图K5 (2) 为为3阶有向完全图阶有向完全图 (3) 为彼得森图为彼得森图, 它是它是3 正则图正则图 (1)(2)(3)彼得森图彼得森图42都有15条边，顶点数都是10，所有顶点的度数都是3，这样的图叫彼得森图。它的一般形状是下面的第一张图，与之同构的图多种多样，形状各异，共有100多种。43子图子图 定义定义 设设G=, G =是是2个图个图n若若V V且且E E, 则称则称G 为为G的的子图子图, G为为G 的的母图母图, 记作记作G G. 如如:G1,G2是是G的子图的子图.(2) 若若G

26、G 且且V =V，则称，则称G 为为G的的生成子图生成子图. G2是是G的生成子图的生成子图.(3) 若若V V 或或E E，称，称G 为为G的的真子图真子图. G1,G2是是G的真子图的真子图.GG1G244子图子图( (续续) )例例 画出画出K4的所有非同构的生成子图的所有非同构的生成子图 45导出子图导出子图(4) 设设V V 且且V , 以以V 为顶点集为顶点集, 以以两端两端点都在点都在V 中的所有边中的所有边为边集的为边集的G的子图称作的子图称作V 的导出子图的导出子图，记作，记作 GV 下图下图,V=a,b,G1是是V的导出子图的导出子图.G2呢呢?GG1G2练习:画出V=a,d,c的导出子图.46(5) 设设E E且且E , 以以E 为边集为边集, 以以E 中中边边关联的所有顶点关联的所有顶点为顶点集的为顶点集的G的子图称作的子图称作E 的导出子图的导出子图, 记作记作 GE .下图下图,E=e1,e2,e3,G1