离散数学7-1图概念7-2路与回路.ppt

《离散数学7-1图概念7-2路与回路.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学DiscreteMathematics山东科技大学信息科学与工程学院1第七章图论图论是近年来发展迅速而又应用广泛的一门学科。本章主要讲授图论的基本概念和定理。图论：数据结构、操作系统、编译原理、计算机网络原理的基础要求：熟练掌握图的基本概念和定理并能够进行简单应用。27-1图的基本概念本节要熟悉下列概念（26个）：图、无向边、有向边、起始结点、终止结点、无向图、有向图、混合图、邻接点、邻接边、孤立结点、零图、平凡图、结点的度数、图的最大度、最小度、结点的入度、结点的出度、平行边、简单图、

2、完全图、补图、子图、生成子图、子图的相对于图的补图、图的同构多重图、3图的定义点的度数特殊的图图同构7-1图的基本概念4一、图的定义定义7-1.1图（graph）G由一个三元组表示，其中：非空集合V(G)={v1,v2,…,vr}称为图G的结点集，其成员vi(i=1,2,…,r)称为结点或顶点（nodesorvertices）；集合E(G)={e1,e2,…,es}称为图G的边集，其成员ej(j=1,2,…s)称为边(edges)。函数G：E(G)→(V(G),V(

3、G))，称为边与顶点的关联映射（associatvemapping）5例1：G=其中V(G)={a，b，c，d}，E(G)={e1，e2，e3，e4，e5，e6}，G(e1)=(a，b)，G(e2)=(a，c)，G(e3)=(b，d)，G(e4)=(b，c)，G(e5)=(d，c)，G(e6)=(a，d)abcde1e2e3e4e5e6若把图中的边ej看作总是和两个结点关联，那么一个图亦简记为G=，其中非空集合V称为图G的结点集，集合E称为图G的

4、边集。若边ej与结点无序偶(vj,vk)关联，那么称该边为无向边。若边ej与结点序偶关联，那么称该边为有向边。起始结点终止结点6例2：G=其中V(G)={a，b，c，d}，E(G)={e1，e2，e3，e4，e5，e6}，G(e1)=(a，b)，G(e2)=(a，c)，G(e3)=(b，d)，G(e4)=(b，c)，G(e5)=(d，c)，G(e6)=(a，d)一个图与结点、连接结点的边、边与结点的关联有关。72、有向边&无向边无向边：如果E

5、中边ei对应V中的结点对是无序的(u，v)称ei是无向边，记ei=(u，v)，称u，v是ei的两个端点。有向边：如果ei与结点有序对相对应，称ei是有向边，记ei=，称u为ei的始点，v为ei的终点。83、图的分类：①无向图：每条边均为无向边的图称为无向图。②有向图：每条边均为有向边的图称为有向图。③混合图：有些边是无向边，有些边是有向边的图称为混合图。V1’v1v4v5v1v2v3v4V2’V3’V4’(a)无向图(b)有向图(c)混合图(孤立点)v2v3环91、G1=

6、1，E1>是无向图，其中V1={V1，V2，V3，V4，V5，V6}，E1={e1，e2，e3，e4，e5，e6}，e1=(V1，V3)，e2=(V1，V4)，e2=(V2，V4)，e3=(V3，V4)，e4=(V3，V6)，e5=(V4，V5)，e6=(V5，V6)3、G3=是混合图，V3={V1，V2，V3，V4}，E3={，(V1，V3)，，，(V4，V2)}2、G2=是有向图，其中V2={V1，V2，V3，V4}，E=

7、{，，，，，，}练习：画出下面的图。104、点和边的关联：如ei=(u，v)或ei=称u，v与ei关联。5、点与点的相邻：关联于同一条边的结点称为邻接点。6、边与边的邻接：关联于同一结点的边称为邻接边。7、孤立结点：不与任何结点相邻接的结点称为孤立结点。8、零图：仅有孤立结点的图。9、平凡图：仅有一个孤立结点的图。1110、自回路(环)：关联于同一结点的边称为自回路，或称为环。11、平行边

8、：在有向图中，始点和终点均相同的边称为平行边，无向图中若两点间有多条边，称这些边为平行边，两点间平行边的条数称为边的重数。12图的定义点的度数特殊的图图同构7-1图的基本概念13二、点的度数1、点的度数的定义定义7-1.2：在图G=，vV，与结点v关联的边数称为该点的度数，记为deg(v)。孤立结点的度数为0。2、出度与入度定义7-1.3：在有向图中，vV，以v为始点的边数称为该结点的出度，记作deg+(v);以v为终点的边数称为该结点的入度，记作deg-(v)。显然有deg(v)