离散数学第七章图的基本概念

第7章图的基本概念7.1无向图及有向图7.2通路、回路、图的连通性7.3图的矩阵表示7.4最短路径及关键路径7.1无向图及有向图一.基本概念和术语1.无向图与有向图图:图G=V,E,其中V为(非空)顶点集合,E是V中顶点偶对的集合,称为边.通常用V(G)和E(G)分别表示图G的顶点集合和边集合.无向图:若图G中边集合E(G)为无向边的集合,则称该图为无向图.有向图:若图G中边集合E(G)为有向边的集合,则称该图为有向图.有时用D=V,E表示有向图.2.有限图与n阶图若G=V,E中V,E都是有穷集合,则称G为有限图.若|V|=n,则称G为n阶图.例如:图7.1中(1)为无向图G=V,E,V={v1,v2,v3,v4,v5},E={(v1,v2),(v2,v2),(v2,v3),(v1,v3),(v1,v3)(v1,v4)};(2)为有向图D=V,E,V={v1,v2,v3,v4,v5},E={v1,v1,v1,v2,v2,v4,v3,v2,v3,v2,v3,v4,v4,v5,v5,v4}V2V1V5V3V4e1e2e3e4e5e6(1)V1V2V3V4V5e1e2e3e4e5e6e7e8图7.1(2)3.零图与平凡图若G=V,E中,E=φ,则称G为零图.若|V|=1,则称G为平凡图.4.关联与相邻设图G=V,E,u,v∈V,(u,v)∈E(有向图u,v∈E)常记e=(u,v)(或有向图e=u,v),称u,v为e的端点.(对有向图中的有向边来说,称u为e的始点,v为e的终点)称e与u或v是彼此相关联的;无边关联的顶点称为孤立点.若e关联的两个顶点重合,则称e为环;若u≠v,则称e与u(或v)的关联次数为1;若u=v(即e为环),则称e与u关联的次数为2;若顶点u,v之间有边关联,则称u与v相邻;若两条边至少有一个公共端点,则称这两条边相邻.5.顶点的度数设v为无向图G中的一个顶点,称v作为边的端点的次数之和为v的度数或度,记作d(v).若v为有向图G中的一个顶点,称v作为边的始点次数之和为v的出度,记作d+(v);v作为边的终点的次数之和为v的入度,记作d-(v),称d+(v)+d-(v)为v的度数或度,记作d(v).G的最大度:Δ(G)=max{d(v)|v∈V(G)}G的最小度:δ(G)=min{d(v)|v∈V(G)}V2V1V5V3V4(1)V1V2V3V4V5图7.1(2)V1V2V3V5V4V1V2V3V5V46.简单图对于无向图,若关联一对顶点的边多于1条,则称这些边为平行边.对于有向图,关联一对顶点的方向相同的边,如果多于1条,则称这些边为平行边.既不含平行边,也不含环的图,称为简单图.124312345123(1)K4(2)K5图7.2(3)7.完全图设G为n阶(n个顶点)无向简单图,若G中任何两个顶点均相邻,则称G为n阶(无向)完全图,记作Kn.边数n(n-1)/2设D为n阶(n个顶点)有向简单图,若G中任何两个顶点之间均有两条方向相反的边,则称G为n阶有向完全图.边数n(n-1)8.子图设G=V,E,G’=V’,E’,若V’⊆V,E’⊆E,则称G’为G的子图.记作G’⊆G.若G’⊆G且G’≠G,则称G’为G的真子图.若G’⊆G且V’=V,则称G’为G的生成子图.若V1⊆V且V1≠φ,称以V1为顶点集,以两个端点均在V1中的边为边集的图为V1的导出子图.若E1⊆E且E1≠φ,称以E1为边集,以E1中边关联的顶点为顶点集的图为E1的导出子图.注)每个图都是本身的子图.e1e3V1V2V3V4e5e4e2V1V2e5e4V1V2V3V4e1e3e4(1)(2)(3)V1V2V3e1e2e3e4V1V2V3e1e3(2)图7.3V1V2e1(3)(1)演示文稿123后等印度神油官方网站补图:设G=V,E为n阶简单图,称以V为顶点集,以使G成为n阶完全图所添加的边为边集的图为G的补图,记作G123451234512345(1)(2)5阶完全图(1)与(2)互为补图123123123(1)(2)3阶有向完全图(1)与(2)互为补图图7.4二.握手定理(图论基本定理)任何图G中各顶点的度数之和等于边数的2倍.若G为有向图,则各顶点的入度之和等于各顶点的出度之和.都等于边数.mEvvvVEVGmvdvdmvdnniiniinii||},,...,,{,,)()(2)(21111其中即推论:任何图G中,奇度顶点的个数为偶数.说明:图G的度数序列为{d(v1),d(v2),…,d(vn)}例7.1(1)(3,3,2,3),(5,2,3,1,4)能成为图的度数序列吗?为什么?(2)已知图G中有10条边,4个3度顶点,其余顶点的度数均小于等于2,问G中至少有多少个顶点?为什么?三.图的同构设G1=V1,E1,G2=V2,E2为两个无向图,若存在双射函数f:V1-V2,使得对于任意的e=(v1,v2)∈E1当且仅当e’=(f(v1),f(v2))∈E2,且e与e’的重数相同,则称G1与G2同构.记作G1≌G2.abcdeV1V2V3V4V5(1)(2)例7.2(1)画出4个顶点3条边的所有可能非同构的无向简单图(2)画出3个顶点2条边的所有可能非同构的有向简单图(1)(2)1234123412341231231231237.2通路、回路、图的连通性一.术语1.通路与回路设Γ=v0e1v1e2…ekvk为图G中的顶点与边的交替序列,若Γ满足:vi-1,vi为ei的端点(若G为有向图,vi-1是ei的始点,vi是ei的终点)i=1,2,…,k,则称Γ为G中通路,v0,vk分别称为通路的始点和终点,Γ中边的数目k称为通路长度.若v0=vk,则通路称为回路.若Γ中各边互不相同,则称Γ为简单通路,若v0=vk,则称Γ为简单回路.若Γ中各顶点互不相同,则称Γ为初级通路,若Γ中除v0=vk外,各顶点各不相同,并且各边也互不相同,则称Γ为初级回路或圈.有边重复出现的通路和回路分别称为复杂通路和回路.V0V1V2V3V4V0V6V5V7V8V3V1V2V4V0V1V2V3V4V2V3V4V0V1V5(1)v0到v4长为4的初级通路(3)v0到v8长为8的简单通路(5)v0到v0=v5长为5的初级回路(7)v0到v0长为8的简单回路图7.7V0V1V2V3V4V0V6V5V7V8V3V1V2V4V0V1V2V3V4V2V3V4V0V1V5(2)v0到v4长为4的初级通路(4)v0到v8长为8的简单通路(6)v0到v0=v5长为5的初级回路(8)v0到v0长为8的简单回路图7.7定理1:在一个n阶图中,若从顶点vi到vj(vi≠vj)存在通路,则从vi到vj存在长度小于等于n-1的通路.推论:在一个n阶图中,若从顶点vi到vj(vi≠vj)存在通路,则从vi到vj存在长度小于等于n-1的初级通路.定理1:在一个n阶图中,如果存在vi到自身的回路,则从vi到自身存在长度小于等于n的回路.推论:在一个n阶图中,如果存在vi到自身存在一条简单回路,则从vi到自身存在长度小于等于n的初级回路.2.顶点之间的连通关系在无向图G中,若顶点vi到vj有通路,则称vi与vj连通.规定顶点与自身连通.顶点之间的连通关系是等价关系.在有向图G中,若顶点vi到vj有通路,则称vi可达vj.规定任何顶点与自身可达.3.短程线与距离若vi与vj连通(有向图,若vi可达vj),则称vi到vj长度最短的通路为vi到vj的短程线,短程线的长度称为vi到vj的距离,用d(vi,vj)表示.(对于有向图,用dvi,vj表示).说明:若vi与vj不连通(对于有向图,若vi不可达vj),则规定d(vi,vj)=∞(dvi,vj=∞).其他情况满足距离公式.4.无向图的连通性若无向图G中任何两顶点都连通,则称G是连通图.对于任意的无向图G.设V1,V2,…,Vk是顶点之间连通关系的等价类,则称他们的导出子图为G的连通分支.用p(G)表示G的连通分支数.abcdefghiV1V2V3V4e4e1e2e35.有向图的连通性若略去有向图D中各边的键头,所得无向图是无向连通图,则称D是弱连通图(或称D是连通图).若D中任何两顶点至少一个可达另一个,则称D是单向连通图若D中任何两顶点都是相互可达的,则称D是强连通图.注)D是强连通图⇒D是单向连通图⇒D是弱连通图.123412341234(1)强(2)单(3)弱二.点割集与边割集1.点割集与割点若无向图G=V,E中,存在V’⊂V,使得p(G-V’)p(G),而任意的V”⊂V’,均有p(G-V”)=p(G),则称V’为G的点割集.若V’={v},称v为G的割点.2.边割集及桥若无向图G=V,E中,存在E’⊆E,使得p(G-E’)p(G),而任意的E”⊂E’,均有p(G-E”)=p(G),则称E’为G的边割集或割集.若E’={e},称e为G的割边或桥.V1V2V3V4V5V6V7e1e2e5e3e4e7e8e6e9{v3,v5},{v2},{v6}为点割集.{e3,e4},{e4,e5},{e1,e2,e3},{e1,e2,e4},{e9}等边割集,e9是桥.7.3图的矩阵表示1.无向图的关联矩阵设无向图G=V,E,V={v1,v2,…,vn},E={e1,e2,…,em}令mij为顶点vi与ej的关联次数,则称(mij)n×m为G的关联矩阵.记为M(G)V1V2V3V4e4e1e2e3e5图7.1000000210010111000111)(GM.,)5(0)4(2)()3(),...,2,1)(()2(),...,2,1(2)1(11111111为平行边与则说明列相同列与第若第是孤立点kjimjijniinimjijmjniijimjijniijeekjvmmvdmmnivdmmjm性质:00000210010111000111)(GM2.有向图的关联矩阵设有向图D=V,E,V={v1,v2,…,vn},E={e1,e2,…,em}1,vi为ej的始点令mij=0,vi与ej不关联-1,vi为ej的终点则称(mij)n×m为D的关联矩阵.记为M(D).V1V2V3V4e1e2e3e4e5图7.1101110100001110100011)(DMniniimjijniinimjijimjijimjijmjniijniijmvdmmvdmnivdmvdmmmjm11111111111)()1(,)()1(:),...,2,1(),()1(),()1()2(0,,...,2,1,0)1(所以即性质:3.有向图的邻接矩阵设有向图D=V,E,V={v1,v2,…,vn},|E|=m令a(1)ij为vi邻接到vj的边的条数,则称为D的邻接矩阵,记为A(D).nnija)()1(01110100001110100011)(DMV1V2V3V4图7.120100100001000121)(DA.1,,1,)3()(),()2()(),()1(1)1(11)1(111)1(1)1(111)1(1)1(的回路总数中长度为即中环的个数为而的通路总数中长度为也可看成中边的总数为DDaDDamvdavdamvdavdaniiininjijnjjnjniijjniijniininjijinjijD中长度为l≥2的通路数和回路数为:nkkjliklijnnlijlaaaaA1)1()1()()(,)(其中为顶点v