《离散数学耿素云第5版.ppt》由会员分享，可在线阅读，更多相关《离散数学耿素云第5版.ppt（27页珍藏版）》请在三一办公上搜索。
1、1,图论,2,图论部分,第5章 图的基本概念第6章 特殊的图第7章 树,3,第5章 图的基本概念,5.1 无向图及有向图5.2 通路,回路和图的连通性5.3 图的矩阵表示5.4 最短路径,关键路径和着色,4,5.1 无向图及有向图,无向图与有向图顶点的度数握手定理简单图完全图子图补图,5,无向图,多重集合:元素可以重复出现的集合无序积:AB=(x,y)|xAyB 定义 无向图G=,其中(1)顶点集V是非空有穷集合,其元素称为顶点(2)边集E为VV的多重子集，其元素称为无向边，简称边.例如,G=,其中V=v1,v2,v5,E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2
2、,v5),(v1,v5),(v4,v5),6,有向图,定义 有向图D=,其中(1)顶点集V是非空有穷集合,其元素称为顶点(2)边集E为VV的多重子集，其 元素称为有向边，简称边.D的基图:用无向边代替有向边如D=,其中 V=a,b,c,dE=,图的数学定义与图形表示,在同构意义下一一对应,7,无向图与有向图(续),通常用G表示无向图,D表示有向图,也常用G泛指无向图和有向图.V(G),E(G),V(D),E(D):G和D的顶点集,边集.n 阶图:n个顶点的图零图:E=平凡图:1 阶零图空图:V=,8,顶点和边的关联与相邻,定义 设e=(u,v)是无向图G=的一条边,称u,v为e的端点,e与u(
3、v)关联.若u v,则称e与u(v)的关联次数为1;若u=v,则称e为环,此时称e与u 的关联次数为2;若w不是e端点,则称e与w 的关联次数为0.无边关联的顶点称作孤立点.定义 设无向图G=,u,vV,e,eE,若(u,v)E,则称u,v相邻;若e,e至少有一个公共端点,则称e,e相邻.对有向图有类似定义.设e=u,v是有向图的一条边,又称u是e的始点,v是e的终点,u邻接到v,v邻接于u.,9,顶点的度数,设G=为无向图,vV,v的度数(度)d(v):v作为边的端点次数之和 悬挂顶点:度数为1的顶点 悬挂边:与悬挂顶点关联的边 G的最大度(G)=maxd(v)|vV G的最小度(G)=mi
4、nd(v)|vV例如 d(v5)=3,d(v2)=4,d(v1)=4,(G)=4,(G)=1,v4是悬挂顶点,e7是悬挂边,e1是环,10,顶点的度数(续),设D=为有向图,vV,v的出度d+(v):v作为边的始点次数之和 v的入度d(v):v作为边的终点次数之和 v的度数(度)d(v):v作为边的端点次数之和 d(v)=d+(v)+d-(v)D的最大出度+(D)=maxd+(v)|vV 最小出度+(D)=mind+(v)|vV 最大入度(D)=maxd(v)|vV 最小入度(D)=mind(v)|vV 最大度(D)=maxd(v)|vV 最小度(D)=mind(v)|vV,11,例,例 d+
5、(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.,12,图论基本定理握手定理,定理 任意无向图和有向图的所有顶点度数之和都等于边数的2倍,并且有向图的所有顶点入度之和等于出度之和等于边数.证 G中每条边（包括环）均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，m条边共提供2m度.有向图的每条边提供一个入度和一个出度,故所有顶点入度之和等于出度之和等于边数.推论 任意无向图和有向图的奇度顶点个数必为偶数.,13,图的度数列,设无向图G的顶点集V=v1,v2,vnG的
6、度数列:d(v1),d(v2),d(vn)如右图度数列:4,4,2,1,3设有向图D的顶点集V=v1,v2,vnD的度数列:d(v1),d(v2),d(vn)D的出度列:d+(v1),d+(v2),d+(vn)D的入度列:d(v1),d(v2),d(vn)如右图度数列:5,3,3,3 出度列:4,0,2,1 入度列:1,3,1,2,14,握手定理的应用,例1(3,3,3,4),(2,3,4,6,8)能成为图的度数列吗?,解 不可能.它们都有奇数个奇数.,例2 已知图G有10条边,4个3度顶点,其余顶点的度数均小于等于2,问G至少有多少个顶点?,解 设G有n个顶点.由握手定理,43+2(n-4)
7、210解得 n8,15,握手定理的应用(续),例3 证明不存在具有奇数个面且每个面都具有奇数条棱的多面体.,证 用反证法.假设存在这样的多面体,作无向图G=,其中V=v|v为多面体的面,E=(u,v)|u,vV u与v有公共的棱 uv.根据假设,|V|为奇数且vV,d(v)为奇数.这与握 手定理的推论矛盾.,16,多重图与简单图,定义(1)在无向图中,如果有2条或2条以上的边关联同一对顶点,则称这些边为平行边,平行边的条数称为重数.(2)在有向图中,如果有2条或2条以上的边具有相同的始点和终点,则称这些边为有向平行边,简称平行边,平行边的条数称为重数.(3)含平行边的图称为多重图.(4)既无平
8、行边也无环的图称为简单图.注意:简单图是极其重要的概念,17,实例,e5和e6 是平行边重数为2不是简单图,e2和e3 是平行边,重数为2e6和e7 不是平行边不是简单图,18,图的同构,定义 设G1=,G2=为两个无向图(有向图),若存在双射函数 f:V1V2,使得对于任意的vi,vjV1,(vi,vj)E1（E1）当且仅当(f(vi),f(vj)E2（E2），并且,(vi,vj)（）与(f(vi),f(vj)（）的重数相同，则称G1与G2是同构的，记作G1G2.,同构实例,19,彼得森图,例1 证明下述2对图是同构的,20,同构实例(续),例2 试画出4阶3条边的所有非同构的无向简单图例3
9、 判断下述每一对图是否同构:(1),度数列不同不同构,21,同构实例(续),(2)(3),不同构入(出)度列不同,不同构(左边没有三角形,右边有三角形)注意:度数列相同,(1)(2),22,图的同构(续),几点说明：图之间的同构关系具有自反性、对称性和传递性.能找到多条同构的必要条件,但它们都不是充分条件:边数相同，顶点数相同 度数列相同(不计度数的顺序)对应顶点的关联集及邻域的元素个数相同，等等若破坏必要条件，则两图不同构至今没有找到判断两个图同构的多项式时间算法,23,完全图,n阶无向完全图Kn:每个顶点都与其余顶点相邻的n阶无向简单图.简单性质:边数m=n(n-1)/2,=n-1n阶有向
10、完全图:每对顶点之间均有两条方向相反的有向边的n阶有向简单图.简单性质:边数m=n(n-1),=2(n-1),+=+=-=-=n-1,K5,3阶有向完全图,24,子图,定义 设G=,G=是两个图(1)若V V且E E,则称G 为G的子图,G为G 的 母图,记作G G(2)若G G 且V=V，则称G 为G的生成子图(3)若V V 或E E，称G 为G的真子图(4)设V V 且V,以V 为顶点集,以两端点都在 V 中的所有边为边集的G的子图称作V 的导 出子图，记作 GV(5)设E E且E,以E 为边集,以E 中边关联的 所有顶点为顶点集的G的子图称作E 的导出子 图,记作 GE,25,生成子图实例,K4的所有非同构的生成子图,导出子图实例,26,G,D,Gv1,v2,Ge1,e3,e4,De1,e3,Dv1,v2,27,补图,定义 设G=为n阶无向简单图，以V为顶点集,所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记作.若G,则称G是自补图.例 对K4的所有非同构子图,指出互为补图的每一对子图,并指出哪些是自补图.,
