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

第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}

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)}

6.简单图对于无向图,假设关联一对顶点的边多于1条,那么称这些边为平行边.对于有向图,关联一对顶点的方向相同的边,如果多于1条,那么称这些边为平行边.既不含平行边,也不含环的图,称为简单图.

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的导出子图.注)每个图都是本身的子图.

9.补图:设G=V,E为n阶简单图,称以V为顶点集,以使G成为n阶完全图所添加的边为边集的图为G的补图,记作

二.握手定理(图论根本定理)任何图G中各顶点的度数之和等于边数的2倍.假设G为有向图,那么各顶点的入度之和等于各顶点的出度之和.都等于边数.推论:任何图G中,奇度顶点的个数为偶数.说明:图G的度数序列为{d(v1),d(v2),…,d(vn)}

yongshengsuoye吺唍咦

例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.

例7.2(1)画出4个顶点3条边的所有可能非同构的无向简单图(2)画出3个顶点2条边的所有可能非同构的有向简单图

7.2通路、回路、图的连通性一.术语1.通路与回路设Γ=v0e1v1e2…ekvk为图G中的顶点与边的交