【教学课件】第七章图的基本概念.ppt
第七章 图的基本概念,7.1 无向图及有向图7.2 通路、回路、图的连通性7.3 图的矩阵表示,作 业,7.1 无向图及有向图,设A,B为两集合,称 a,baAbB为A与B的无序积,记作AB将无序对a,b记作(a,b).,无向图,一个无向图G是一个二元组,即G,其中,(1)V是一个非空的集合,称为G的顶点集,V中元素称为顶点或结点；(2)E是无序积VV的一个多重子集,称E为G的边集,E中元素称为无向边或简称边.,有向图,一个有向图D是一个二元组,即D,其中,(1)V同无向图中的顶点集；(2)E是卡氏积的多重子图,其元素称为有向边,也简称边.,给每条边赋与权的图G=称为加权图，记为G=,其中W表示各边权的集合。,2,3.5,7.8,设ek(vi,vj)为无向图G中的一条边,称vi,vj为ek的端点,ek与vi(或vj)是彼此关联的.无边关联的顶点称为孤立点.若一条边所关联的两个顶点重合,则称此边为环.,ek与vi(或vj)的关联次数,1,vivj,2,vi vj,0,vi(vj)不是ek的端点,b,a,v,V,设G为一无向图或有向图(1)若V,E都是有穷集合,则称G是有限图.(2)若Vn,则称G为n阶图(3)若E,则称G为零图特别是,若此时又有V1,则称G为平凡图.,相邻,设无向图GV,E,vi,vjV,ek,elE.(1)若存在一条边e以vi,vj为端点,即e(vi,vj),则称vi,vj是彼此相邻的,简称相邻的(2)若ek,el至少有一个公共端点,则称ek,el是彼此相邻的,简称相邻的,始点 终点,以上两定义对有向图也是类似的若ek vi,vj,除称vi,vj是ek的端点外,还称vi是ek的始点,vj是ek的终点,vi邻接到vj,vj邻接于vi.,度,设G为一无向图,vjV,称vj作为边的端点的次数之和为vi的度数,简称度,记作d(vj).称度数为1的顶点为悬挂顶点,它所对应的边为悬挂边.,设D为一有向图,vjV,称vj作为边的始点的次数之和,为vj的出度,记作d+(vj)；称vj作为边的终点的次数之和,为vj的入度,记作d-(vj)；称vj作为边的端点的次数之和,为vj的度数,简称度,记作d(vj).显然d(vj)d+(vj)d-(vj).,deg(v1)3，deg+(v1)2，deg-(v1)1；deg(v2)3，deg+(v2)2，deg-(v2)1；deg(v3)5，deg+(v3)2，deg-(v3)3；deg(v4)deg+(v4)deg-(v4)0；deg(v5)1，deg+(v5)0，deg-(v5)1；其中，v5是悬挂结点，为悬挂边。,最大度和最小度,对于图G,记(G)maxd(v)vV,(G)mind(v)vV,分别称为G的最大度和最小度.,若DV,E是有向图,除了(D),(D)外,还有最大出度、最大入度、最小出度、最小入度,分别定义为,基本定理(握手定理),设图G为无向图或有向图,Vv1,v2,.,vn,|E|=m(m为边数),则,推论,任何图(无向的或有向的)中,度为奇数的顶点个数为偶数.,定理,设有向图D,Vv1,v2,.,vn,Em,则,度数序列,设Vv1,v2,.,vn为图G的顶点集,称(d(v1),d(v2),.,d(vn)为G的度数序列.,例7.1,(1)(3,3,2,3),(5,2,3,1,4)能成为图的度数序列吗？为什么？(2)已知图G中有10条边,4个3度顶点,其余顶点的度数均小于等于2.问G中至少有多少个顶点？为什么？,平行边、重数、多重图、简单图,在无向图中,关联一对顶点的无向边如果多于1条,称这些边为平行边.平行边的条数称为重数.在有向图中,关联一对顶点的有向边如果多于1条,且它们的始点与终点相同,则称这些边为有向平行边,简称平行边.含平行边的图称为多重图.既不含平行边,也不含环的图称为简单图.,例,无向完全图、有向完全图,设G=是n阶无向简单图,若G中任何顶点都与其余的n1个顶点相邻,则称G为n阶无向完全图,记作Kn.设D=为n阶有向简单图,若对于任意的顶点u,vV(uv),既有有向边,又有,则称D是n阶有向完全图.Kn均指无向完全图.,图7.2,在图7.2(1)中所示为K4,(2)所示为K5,(3)所示为3阶有向完全图.,子图、真子图,设G=,G=是两个图.若VV,且EE,则称G 是G的子图,G 是G的母图,记做G G.若G G且GG(即VV或E E),则G是G的真子图.,生成子图、导出子图,若G G且V=V则称V是V的生成子图.设V1V,且V1,以V1为顶点集,以两端点均在V1中的全体边为边集的G的子图,称为V1导出的导出子图.设E1 E,且E1,以E1为边集,以E1中关联的顶点的全体为顶点集的G的子图称为E1导出的导出子图.,在如下图中，给出了图G以及它的真子图G和生成子图G。G是结点集v1，v2，v4，v5，v6的导出子图。,补图,设G=是n阶无向简单图.以V为顶点集,以所有能使G成为完全图Kn的添加边组成的集合为边集的图,称为G相对于完全图Kn的补图,简称G的补图,记作.有向简单图的补图可类似定义.,图7.4,图的同构,例如下图(a)、(b)、(c)、(d)所示，图(a)、图(b)、图(c)和图(d)所表示的图形实际上都是一样的。,同构,设两个无向图 G1=,G2=,如果存在双射函数：V1V2,使得对于任意的e=(vi,vj)E1当且仅当e=(vi),(vj)E2,并且e与e的重数相同,则称G1与G2是同构的,记作G1G2.,有向图的同构,(1)(2),顶点之间的对应关系为av1,b v2,c v3,d v4,e v5.,两图同构1、顶点个数相同 2、边的条数相同 3、度数相同的结点数相同,(a)(b)(c).(a)所示图称为彼德森图.,例7.2(1)画出4个顶点3条边的所有可能非同构的无向简单图；(2)画出3个顶点2条边的所有可能非同构的有向简单图.,7.1结束，返回目录,
