离散数学与第22讲 .pptVIP

信息学院计算机应用技术系 授课教师：胡静 办公地点：信息楼805 联系方式电子邮箱：ise_huj@ujn.cn 图论的起源和发展 图论是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 图论最早起源于一些数学游戏的难题研究，如1736年Euler所解决的K?nigsberg七桥问题，以及民间广为流传的一些游戏难题，如迷宫问题，匿门博弈问题，棋盘上马的行走路线问题等。这些古老的数学难题，当时吸引了很多学者的注意，在这些问题的研究的基础上又继续提出了著名的四色猜想，汉密尔顿（环游世界）数学难题。 图论的起源和发展 1847年，克希霍夫（Kirchhoff）用图论分析电网络，这是图论最早应用于工程科学。以后随着科学的发展，图论在解决运筹学、网络理论、信息论、控制论、博弈论以及计算机科学等各个领域的问题时，显示出越来越大的效果。 图论在各种物理学科，化学学科，工程领域，社会科学和经济问题的广泛应用，使它受到数学界和工程界的广泛支持。 离散数学第22讲 本讲基本知识点： 1、图论中的基本概念 2、通路与回路的定义 3、图的连通性 4、图的矩阵表示 第十四章 图的基本概念 第十四章 图的基本概念 第十四章 图的基本概念 第十四章 图的基本概念 第十四章 图的基本概念 第十四章 图的基本概念 第十四章 图的基本概念 第十四章 图的基本概念 第十四章 图的基本概念 第十四章 图的基本概念 定义14.5完全图 设G＝V,E为一个具有n个结点的无向简单图，如果G中任一个结点都与其余n-1个结点相邻接，则称G为无向完全图，简称G为完全图，记为Kn。 设G＝V,E为一个具有n个结点的有向简单图，若对于任意u,v?V(u?v)，既有有向边u,v，又有有向边v,u，则称G为有向完全图，在不发生误解的情况下，也记为Kn。 第十四章 图的基本概念 第十四章 图的基本概念 若通路中的所有边e1，e2，…，ek互不相同，则称此通路为简单通路或一条迹；若回路中的所有边e1，e2，…，ek互不相同，则称此回路为简单回路或一条闭迹； 若通路中的所有结点v0，v1，…，vk互不相同，则称此通路为基本通路或者初级通路、路径；若回路中除v0＝vk外的所有结点v0，v1，…，vk-1互不相同（从而所有边互不相同），则称此回路为基本回路或者初级回路、圈。 基本通路(或基本回路)一定是简单通路(或简单回路)，但反之则不一定。 第十四章 图的基本概念 第十四章 图的基本概念 第十四章 图的基本概念 第十四章 图的基本概念 第十四章 图的基本概念 第十四章 图的基本概念 第十四章 图的基本概念 第十四章 图的基本概念 第十四章 图的基本概念 离散数学 第22讲 本讲小结： 图论中的基本概念 握手定理及推论 完全图及其特征 通路及回路 * * 第 四 部 分 14.1 图 定义14.1 一个无向图是一个有序的二元组V,E，记作G， 其中 (1) V≠φ称为顶点集，其元素称为顶点或结点。 (2) E称为边集，它是无序积VV的多重子集，其元素称为无向边，简称为边。 设A，B为任意的两个集合，称 {{a,b}|a∈A∧b∈B} 为A与B的无序积，记作AB. 元素可以重复出现的集合称为多重集合，某个元素重复出现的次数称为该元素的重复度。例如在集合{a,b,b,a,a}中，a,b的重复度分别为3,2. 定义14.2 一个有向图是一个有序的二元组V,E，记作D， 其中 (1) V≠ ?,称为顶点集，其元素称为顶点或结点。 (2) E称为边集，它是笛卡儿积V×V的多重子集，其元素称为有向边，简称为边。 用图形表示无(有)向图时，常用小圆圈或实心点表示顶点，用顶点之间的连线表示无向边，用有方向的边表示有向边。 v1。 。v2 v3 。 (1) v4 。 。v5 a 。 。b (2) d 。 。c 例14.1 画出下列图形。 (1) G=V,E,其中V={v1,v2,v3,v4,v5},E={(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v1,v5), (v2,v5), (v4,v5)}。 (2) D=V,E,其中V={a,b,c,d},E={a,a,a,b,a,b,a,d,c,d,d,c,c,b}。