离散数学图论-图的基本概念课件

1、图 论图的基本概念图的基本概念七座桥所有的走法一共七座桥所有的走法一共有有7！=5040种。种。1736年，在经过一年的研究之后，年，在经过一年的研究之后，29岁的欧拉提交岁的欧拉提交了了哥尼斯堡七桥哥尼斯堡七桥的论文，圆满解决了这一问题，的论文，圆满解决了这一问题，同时开创了数学同时开创了数学新分支新分支-图论图论。图图 论论n在在许多应用领域中许多应用领域中：地图导航、：地图导航、网络技术网络技术研究及程序流程分析都会研究及程序流程分析都会遇到由遇到由“结点结点”和和“边边”组成的组成的图图n在在计算机许多学科中如：数据结构、操作计算机许多学科中如：数据结构、操作系统、网络理论、信息的组织

2、与检索均离系统、网络理论、信息的组织与检索均离不开由这种不开由这种“结点结点”和和“边边”组成的图组成的图以以及图的特殊形式及图的特殊形式-树树。n图图与树是建立和处理离散对象及其与树是建立和处理离散对象及其关系重关系重要要工具。工具。如地图导航、如地图导航、周游问题周游问题、图像分、图像分割等等割等等。一、图的一、图的概念概念1 1、无序积无序积定义：设定义：设A A，B B为任意的两个集合，为任意的两个集合， 称称 a a，b b aAbB aAbB 为为A A与与B B的无序积，记作的无序积，记作A & BA & B其元素其元素a a，b b 可简记为可简记为（a a，b

3、 b） 2 2、图的定义、图的定义 1 1）定义）定义1 1 一个一个无向图无向图是一个有序的二元组是一个有序的二元组 VE ，记作，记作G G，其中，其中 (1) (1) V V 称为顶点集，其元素称为称为顶点集，其元素称为顶点顶点或或结点结点 (2) (2) E E称为边集称为边集，它是，它是无序积无序积V VV V的的多重子集多重子集，其元素称为，其元素称为无向边无向边， 简称为简称为边边 例：例：无向图无向图G = G = VE 其中其中 顶点集合顶点集合 V Vv1,v2,v3,v4 v1,v2,v3,v4 边集合边集合 E E(v1,v2),(v1,v2),(v2,v3),(v3,

4、v2),(v2,v3),(v3,v2),(v3,v1),(v3,v1),(v2,v2),(v2,v2),(v2,v2),(v2,v2),(v1,v2),(v1,v2), 园括号表示无向边园括号表示无向边 有平行边有平行边2 2） 定义定义2 2 一个一个有向图有向图是一个有序的二元组是一个有序的二元组VE，记作，记作D D，其中，其中 (1) V (1) V 称为顶点集，其元素称为顶点或结点称为顶点集，其元素称为顶点或结点 (2)E(2)E为边集，为边集，它是笛卡儿积它是笛卡儿积 V VV V的有穷多重子集的有穷多重子集，其元素称，其元素称为为有向边有向边，简称，简称边边( (弧弧) )有向图

5、有向图D= D= 其中其中 V Vv1,v2,v3 v1,v2,v3 边集合边集合E E, v2,v1, , （与前面的关系的图表示相当）（与前面的关系的图表示相当）1 1）用）用G G表示无向图，表示无向图，D D表示有向图。表示有向图。 有时有时用用V(G)V(G)，E(G)E(G)分别表示分别表示G G的顶点集和边集。的顶点集和边集。2 2）用）用|V(G)|V(G)|，|E(G)|E(G)|分别表示分别表示G G的顶点数和边的顶点数和边数数 若若V(G)V(G)n n，则称，则称G G为为n n阶图阶图。对。对有向图有相同定义。有向图有相同定义。3 3）在图）在图G G中，若中，若边集

6、边集E(G)E(G)，则称，则称G G为为零图零图 若若G G为为n n阶图，则称阶图，则称G G为为n n阶零图阶零图，记作，记作N Nn n，特别是称，特别是称N N1 1为为平凡图平凡图4 4）在用图形表示一个图时，若给每个结点和每一条边均指定一个）在用图形表示一个图时，若给每个结点和每一条边均指定一个符号（字母或数字），则称这样的图为符号（字母或数字），则称这样的图为标定标定图。图。5) 5) 常用常用e ek k表示边表示边(v(vi i，v vj j)( )( 或或 ) ) 设设G GV E 为无向图，为无向图，e ek k = (v = (vi i，v vj j)E)E， 则则称

7、称v vi i，v vj j为为e ek k的端点的端点， e ek k与与v vi i、v vj j是彼此是彼此相关联的相关联的 起、终点起、终点相同的边称为相同的边称为环环 不不与任何边关联的结点称为与任何边关联的结点称为孤立点孤立点（包括有向图（包括有向图) )6 6）邻接：）邻接： 边的相邻边的相邻：e ek k，e el lEE若若e ek k与与e el l至少有一个公共端点，至少有一个公共端点， 则称则称e ek k与与e el l是相邻的是相邻的 顶点的相邻顶点的相邻：若：若e et tEE，使得，使得e et t = v = ， 则称则称v vi i为为e et t的始点，的

8、始点，v vj j为为e et t的终点，的终点， 并称并称v vi i邻接到邻接到v vj j，v vj j邻接于邻接于v vi i 两个结点为一条边的端点，则称两个结点两个结点为一条边的端点，则称两个结点互为邻接点互为邻接点， 也称也称边关联于这两个结点边关联于这两个结点，或称两个结点邻接于此边，或称两个结点邻接于此边。7）平行边：）平行边： 在无向图中，关联一对顶点的无向边如果多于在无向图中，关联一对顶点的无向边如果多于1 1条，则称这些条，则称这些边为边为平行边平行边，平行边的条数称为，平行边的条数称为重数重数 在在有向图中，关联一对顶点的有向边如果多于有向图中，关联一对顶点的有向边如

9、果多于1 1条，条，并且它们并且它们的的方向方向相同相同，则称这些边为则称这些边为平行边平行边8 8）多重图和简单图：）多重图和简单图：含平行边的图称为多重图含平行边的图称为多重图既既不含平行边也不含环的图称为不含平行边也不含环的图称为（主要讨论简单图（主要讨论简单图） 4 4、结点的度、结点的度 1 1) ) 定义定义4 4 设设G GVE为无向图，为无向图， v Vv V，称，称v v作为边的端点作为边的端点的次数之和的次数之和为为v v的的度数度数，简称为，简称为度度，记作，记作d dG G(v)(v)，简记为简记为d(v)d(v)，即为：结点即为：结点v v 所关联的边的总条数所关联的

10、边的总条数 关于有向图关于有向图D DV E 有：有： vVvV，称，称v v作为边的作为边的始点的次数之和始点的次数之和为为v v的的出度出度，记作，记作d d+ +(v)(v)，称称v v作为边的作为边的终点终点的次数之和为的次数之和为v v的的入度入度，记作，记作d d- -(v)(v) 称称d d+ +(v)+ d(v)+ d- -(v)(v)为为 v v的度数，记作的度数，记作d dD D(v).(v). 2) 2) 称度数为称度数为1 1的顶点为的顶点为悬挂顶点悬挂顶点，与它关联的边称为，与它关联的边称为悬挂边悬挂边 根据结点的度数可将结点分为：根据结点的度数可将结点分为： 度为偶

11、数度为偶数( (奇数奇数) )的顶点称为的顶点称为偶度偶度顶点顶点( (奇度顶点奇度顶点).). 一个环提供的度为一个环提供的度为2 2（有向图的环提供入度（有向图的环提供入度1 1和出度和出度1 1） 3 3）定义：）定义： (G) = maxd(v)|vV(G) (G) = maxd(v)|vV(G) 为图为图G G中结点最大的度中结点最大的度 (G) = mind(v)|vV(G) (G) = mind(v)|vV(G) 为图为图G G中结点最小的度中结点最小的度 简记为简记为 、定义：定义： (D) = maxd(D) = maxd(v)|vV(D) (v)|vV(D) 为图为图D D

12、中结点最大中结点最大的的入入度度 (D) = maxd(D) = maxd(v)|vV(D) (v)|vV(D) 为图为图D D中结点最大的中结点最大的出出度度 - -(D) = mind(D) = mind(v)|vV(D) (v)|vV(D) 为图为图D D中结点最小中结点最小的的入入度度 (D) = mind(D) = mind(v)|vV(D) (v)|vV(D) 为图为图D D中结点最小的中结点最小的出出度度5 5、握手定理（欧拉）、握手定理（欧拉）1)1)定理定理1 1 设设G G为任意无向图为任意无向图,V,Vvv1 1，v v2 2，v vn n,E E = m= m， 则则

13、d(vd(vi i) ) 2m2m ( (所有结点的度数值和为边数的所有结点的度数值和为边数的2 2倍倍) ) 证证: G: G中每条边中每条边( (包括环包括环) )均有两个端点，所以在计算均有两个端点，所以在计算G G中各顶点度数之和中各顶点度数之和时，每条边均提供时，每条边均提供2 2度，当然，度，当然，m m条边共提供条边共提供2m2m度度2) 2) 定理定理2 2 设设D D为任意有向图为任意有向图,V,Vvv1 1，v v2 2，v vn n,|E| = m ,|E| = m ， 则则 d d+ +(v(vi i) =) = d d- -(v(vi i) = m) = m 且且d(

14、vd(vi i) )2m2m3) 3) 推论推论 任何图任何图( (无向的或有向的无向的或有向的) )中，中，奇度顶点奇度顶点的的个数个数是是偶数个偶数个4) 4) 结点的度数序列结点的度数序列 (1) (1) 设设G GVE为一个为一个n n阶无向图，阶无向图，V Vvv1 1，v v2 2，v vn n 称称d(vd(v1 1) )，d(vd(v2 2) )， ，d(vd(vn n) ) 为为G G的的度数列度数列 注：由推论可知，不是任何一个非负整数序列均可作为一个图的度数列。注：由推论可知，不是任何一个非负整数序列均可作为一个图的度数列。 条件：条件：奇度数奇度数的结点个数应该是的结点

15、个数应该是偶数个偶数个 （2 2）序列的可图化）序列的可图化：对一个整数：对一个整数序列序列d=(dd=(d1 1,d,d2 2, ,d dn n),),若存在以若存在以n n个顶点的个顶点的n n阶阶无向图无向图G G，有，有d(vd(vi i)=d)=di i ，称该序列是，称该序列是可图化的。可图化的。 特别的，如果得到的是简单图，称该序列是特别的，如果得到的是简单图，称该序列是可简单图化的。可简单图化的。 （3 3）定理）定理 设非负整数列设非负整数列d d(d1(d1，d2d2，dn)dn)，则，则d d是可图化的是可图化的当且仅当当且仅当 d di i 是偶数是偶数( (序列之和必

16、须是偶数序列之和必须是偶数) ) （4 4）由于简单图中没有平行边及环）由于简单图中没有平行边及环 定理：设定理：设G G为任意为任意n n阶无向阶无向简单图简单图，则，则 (G(G)= n-1)dd2 2ddn n=1 =1 且且d di i= = 偶数偶数 d4=d4=（3,3,3,13,3,3,1） 分析分析 d5= d5=（4,4,3,3,2,24,4,3,3,2,2）二、图的同构二、图的同构定义：设定义：设G1G1VlE1，G2=V2G2=E2为两个无向图为两个无向图( (有向图有向图) )， 若存在双射函数若存在双射函数 f f：V1 V2 V1 V2 对于对于 vivi，vjvj

17、 V1V1，(vi(vi，vj) vj) E1 E1 当且仅当当且仅当(f(vi)(f(vi), ,f(vj)f(vj) E2 E2 并且并且(vi(vi，vj) vj) 与与(f(vi),f(vj(f(vi),f(vj)的重数的重数相同，则称相同，则称G1G1与与G2G2是是同构同构的，记作的，记作Gl Gl G2 G2。 对有向图有相同的定义。对有向图有相同的定义。 定义说明了定义说明了: :两个图的各结点之间，如果存在着一一对应关系两个图的各结点之间，如果存在着一一对应关系 f 这种对应关系又保持了这种对应关系又保持了结点间的邻接关系结点间的邻接关系，那么这两个图就是同构的那么这两个图就

18、是同构的 在有向图的情况下，在有向图的情况下， f 不但应该保持结点间的邻接关系，还应不但应该保持结点间的邻接关系，还应该该保持边的方向。保持边的方向。结点数相同边数相同结点数相同边数相同结点的度相同结点的度相同但是两个图但是两个图不同构不同构注注：1 1) ) 两个图同构的必要条件两个图同构的必要条件阶数相同阶数相同（顶点）（顶点）边数相同边数相同度数相同的顶点数相同度数相同的顶点数相同同构同构的的必要条件，并不是充分条件必要条件，并不是充分条件2 2) )图之间的图之间的同构关系同构关系可看成全体图集合上的二元可看成全体图集合上的二元关系。关系。 具有具有自反性，对称性和传递性，自反性，对

19、称性和传递性，是是等价关系。等价关系。 同构同构的图为一个等价类，在的图为一个等价类，在同构的意义之下都可以看同构的意义之下都可以看成是一个图。成是一个图。例例 (1)(1)画出画出4 4阶阶3 3条边的所有非同构的条边的所有非同构的无向简单图无向简单图 结点个数结点个数与与边数相同边数相同，只需找出，只需找出顶点度数序列不同顶点度数序列不同的图（的图（2 2 3 36 6）如何将度数如何将度数6 6分配给分配给4 4个结点：个结点： 1 1 1 3 1 1 1 3 相应的图相应的图 2 2 1 1 2 2 1 1 2 2 2 0 2 2 2 0例例 (2)(2)画出画出3 3阶阶2 2条边的

20、所有非同构的条边的所有非同构的有向简单图有向简单图 结点个数与边数相同，只需找出结点个数与边数相同，只需找出顶点度（出度及入度）数序列不同顶点度（出度及入度）数序列不同的图的图 结点总度数：结点总度数： 2 22 24 4 度数分配度数分配 1 2 1 1 2 1 按出度与入度分配：按出度与入度分配：入度列入度列 1 1 01 1 0出度列出度列 0 1 0 1 1 1入度列入度列 0 2 00 2 0出度列出度列 1 0 1 0 1 1入度列入度列 1 0 11 0 1出度列出度列 0 2 00 2 0度数分配度数分配 2 2 0 2 2 0 按出度与入度分配：按出度与入度分配：入度列入度列

21、 1 1 01 1 0出度列出度列 1 1 01 1 0这只是对较为简单的情这只是对较为简单的情况给出的非同构图，对况给出的非同构图，对于一般的情况（于一般的情况（n,m)n,m)图图到目前为止还没有解决到目前为止还没有解决 1 1) )完全图完全图 定义定义 设设G G为为n n阶无向阶无向简单图简单图，若，若G G中每个顶点均与其余的中每个顶点均与其余的n n1 1个顶点相邻，个顶点相邻，则称则称G G为为n n阶无向完全图，简称阶无向完全图，简称n n阶完全图阶完全图，记作，记作KnKn(n1)(n1) 设设D D为为n n阶有向简单图，若阶有向简单图，若D D中每个顶点都中每个顶点都邻接到邻接到其余的其余的n n1 1个顶点，个顶点，又又邻接于邻接于其余的其余的 n n1 1个顶点，则称个顶点，则称D D是是 n n 阶阶有向完全图有向完全图 可画图表示（无向图可画图表示（无向图5 5阶、有向图阶、有向图3 3阶和阶和4 4阶）阶） 2)2)完全图的性质：完全图的性质： n n阶无向完全图阶无向完全图G G的边数与结点的关系的边数与结点的关系 m = m = n (n-1)/2n (n-1)/2