《图的基本概念lly》PPT课件

《《图的基本概念lly》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8讲图的基本概念重点重要概念：简单图，度与握手定理、完全图、同构图通路、回路、图的连通性图的矩阵表示与应用欧拉图与哈密尔顿图难点同构图，割集，初级通路与简单通路区别18世纪：哥尼斯堡(Konigsiberg)七桥问题图论是近年来发展迅速而又应用广泛的一门新兴学科。它最早起源于数学游戏的难题研究。acdbadcb1859年：哈密尔顿提出环游世界19~20世纪：迷宫、棋盘上马的行走线路1852年：格色里(Guthrie)提出四色猜想在工程科学中的应用：现实世界中，许多状态都可用图来描述，例如交通运输、城市规划、电路网络、工作调配等都可以

2、用点和边连结的图来模拟。在计算机学科中，计算机网络、操作系统数据库，数据结构等等都与图论有重要的联系。计算机科学广泛应用于运筹学，信息论，控制论，网络理论，化学生物学，物理学。原因在于这些学科的许多实际问题和理论问题可以概括为图论。第七、八、九章介绍与计算机科学关系密切的图论内容及其在实际中的应用。一、基本图类及相关概念8.1无向图及有向图如右图，这是不同于几何图形的另一数学结构。adcb我们不关心边的长短与形状。但边可以是有方向的，有方向的边称为有向边，没有方向的边称为无向边。称{{a,b}

3、aAbB}为A与B的无序积，记作：

4、A&B。习惯上，无序对{a,b}改记成(a,b)有序对(a,b)均用无序积：设A，B为二集合，=(b,a)≠1.无向图无向图：无向图G是一个二元组，其中(1)V是一个非空集–––顶点集V(G)，每个元素为顶点或结点；(2)E是无序积V&V的可重子集(?元素可重复出现)，E–––边集E(G)，E中元素称为无向边。通常记：V={v1,v2,…,vn}E={e1,e2,…,em}其中：ek=(vi,vj)实际中，图的画法：用小圆圈表示V中的每一个元素，如果(vi,vj)E，则在顶点vi与vj之间连线段。如(1

5、)：G=，V={v1,v2,v3,v4}，E={(v1,v2),(v1,v2),(v2,v3),(v2,v3),(v3,v4),(v2,v4),(v1,v4)}v1v4v3v2e1e7e2e3e4e5e6(1)v4e1e2e3e4e5e6v1v2v3v5(2)如(2)：G=，V={v1,v2,v3,v4,v5}，E={(v2,v2),(v1,v2),(v2,v3),(v1,v3),(v1,v3),(v1,v4)}有向图：有向图D是一个二元组，其中(1)V是非空集–––顶点集V(D)(2)E是笛卡尔积VV

6、的可重子集，其元素为有向边实际中，画法同无向图，只是要根据E中元素的次序，由第一元素用方向线段指向第二元素。2.有向图v1v4v3v2e1e2e3e4e5e6(a)v1v4v3v2e1e2e3e4e5e6(b)如(a)：D=，V={v1,v2,v3,v4}，E={,,,,,}如(b)：D=，V={v1,v2,v3,v4}，E={,,,,,}思考：与以

7、前讲到的什么相似？有限图：V，E均为有穷集合零图：E平凡图：E且

8、V

9、=1(n,m)图：

10、V

11、=n且

12、E

13、=m顶点与边关联：如果ek=(vi,vj)E，称ek与vi关联，或ek与vj关联。3.相关概念v1v2v3v4v5v1e1e2e3e4e5e6v1v2v3v5(5,6)图v4顶与顶相邻：如果ek=(vi,vj)E，称vi与vj相邻；边与边相邻：如果ek和ei至少有一个公共顶点关联，则称ek与ei相邻。若ek为有向边，则称vi邻接到vj,vj邻接于vi。ek=e1e2e3e4e5e6v1v2v3v5v4v1

14、v4v3v2e1e2e3e4e5e6孤立点：无边关联的顶点。平行边：无向图中，关联一对结点的无向边多于一条，平行边的条数为重数；多重图：?包含平行边的图。有向图中，关联一对顶点的有向边多于一条，且始、终点相同。简单图：?既不包含平行边又不包含环的图。环：ek=中，若vi=vj，则ek称为环。例：判断多重图与简单图？v1v4v3v2e1e2e3e4e5e8e6e7v5e1e2e3e4e5v1v2v3v5v4e1e3e2e4v1v2v3v5v4度：(1)在无向图G=中，与顶点v(vV)关联的边的数目(每个环计算两

15、次)，记作：d(v)。二、度e1e2e3e4e5e6v1v2v3v5v4思考：无向图中度与边的关系?(2)在有向图D=中，以顶点v(vV)作为始点的边的数目，称为该顶点的出度，记作：d+(v)；出度与入度之和