第1讲图论模型PPT讲稿.ppt
《第1讲图论模型PPT讲稿.ppt》由会员分享,可在线阅读,更多相关《第1讲图论模型PPT讲稿.ppt(40页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第第第第1 1讲图论模型讲图论模型讲图论模型讲图论模型第1页,共40页,编辑于2022年,星期一 一一 图图 论论 简简 介介 图论的起源图论的起源:图论是组合数学的一个分支,它起源于1736年欧拉的第一篇关于图论的论文,这篇论文解决了著名的“哥尼斯堡七桥问题”,从而使欧拉成为图论的创始人。第2页,共40页,编辑于2022年,星期一1 1.哥尼斯堡哥尼斯堡“七桥七桥”问题问题:格尼斯堡人在寻找一条路线第4页,共40页,编辑于2022年,星期一 欧欧 拉拉 图图定义定义 一个图,如果能够从一点出发,经过每条边一次且仅一次再回到起点,则称为欧拉图 欧拉在论文中给出并证明了判断欧拉图的充分必要条件定
2、理,并证明了七桥图不是欧拉图。第5页,共40页,编辑于2022年,星期一 从这个问题可以看出:从这个问题可以看出:图:图:图用点代表各个事物,用边代表各个事物间的二元关系。所以,图是研究集合上的二元关系的工具,是建立数学模型的一个重要手段。第6页,共40页,编辑于2022年,星期一 2 2、一百多年以后、一百多年以后 “七桥”问题以后,图论的研究停滞了一百多年,直到1847年,基尔霍夫用“树”图解决了电路理论中的求解联立方程的问题,十年后凯莱用“树”图计算有机化学中的问题。在这一时期流行着两个著名的图论问题:哈密尔顿回路问题和“四色猜想”问题。第7页,共40页,编辑于2022年,星期一 3 3
3、、哈密尔顿回路问题、哈密尔顿回路问题 1856年,英国数学家哈密尔顿设计了一个周游世界的游戏,他在一个正十二面体的二十个顶点上标上二十个著名城市的名字,要求游戏者从一个城市出发,经过每一个城市一次且仅一次,然后回到出发点。第8页,共40页,编辑于2022年,星期一哈密尔顿回路图:哈密尔顿回路图:示意图:此路线称为:哈密尔顿回路,而此图称为:哈密尔顿图。第9页,共40页,编辑于2022年,星期一4 4、“四四 色色 猜猜 想想”问问 题题 人们在长期为地图(平面图)上色时发现,最少只要四种颜色,就能使得有相邻国界的国家涂上不同的颜色 四色猜想的证明一直没有解决,直到一百多年后,在计算机出现以后,
4、于1976年用计算机算了1200多小时,才证明了四色猜想问题。第10页,共40页,编辑于2022年,星期一 5 5、又过了半个世纪、又过了半个世纪 四色猜想问题出现后,图论的研究又停滞了半个世纪,直到1920年科尼格写了许多关于图论方面的论文,并于1936年发表了第一本关于图论的书。此后图论从理论上到应用上都有了很大发展。特别是计算机的出现使图论得到飞跃的发展。第11页,共40页,编辑于2022年,星期一 图论的重要性图论的重要性 图论是组合数学的一个分支,与其它数学分支如群论、矩阵论、集合论、概率论、拓扑学、数值分析等有着密切的联系。又由于图论给含有二元关系的系统提供了数学模型,因而在许多领
5、域里都具有越来越重要的地位,并且在物理、化学、信息学、运筹学等各方面都取得了丰硕的成果。从二十世际50 年代以来,由于计算机的迅速发展,有力地推动了图论的发展,使得图论成为数学领域里发展最快的分支之一。第12页,共40页,编辑于2022年,星期一2.图论的基本概念图论的基本概念1)图的概念图的概念2)赋权图与子图赋权图与子图3)图的矩阵表示图的矩阵表示4)图的顶点度图的顶点度5)路和连通路和连通第13页,共40页,编辑于2022年,星期一1)图的概念图的概念 定义定义 一个一个图图G是指一个二元组是指一个二元组(V(G),E(G),其中,其中:其中每个元素称为图其中每个元素称为图G的的顶点顶点
6、.组成的集合,即称为组成的集合,即称为边集边集,其中元素称为其中元素称为边边.定义定义 图图G的的阶阶是指图的顶点数是指图的顶点数|V(G)|,用用来表示;来表示;图的边的数目图的边的数目|E(G)|用用 来表示来表示.也用也用来表示边来表示边是非空有限集,称为是非空有限集,称为顶顶点集点集,1)2)E(G)是顶点集是顶点集V(G)中的无序或有序的元素偶对中的无序或有序的元素偶对表示图,表示图,简记简记 用用第14页,共40页,编辑于2022年,星期一 定义 若一个图的顶点集和边集都是有限集,则称若一个图的顶点集和边集都是有限集,则称 其为其为有限图有限图.只有一个顶点的图称为只有一个顶点的图
7、称为平凡图平凡图,其他的,其他的 所有图都称为所有图都称为非平凡图非平凡图.第15页,共40页,编辑于2022年,星期一 定义若若图图G中的边均为有序偶对中的边均为有序偶对,称称G为为有向有向边边 为为无向边无向边,称,称e连接连接 和和 ,顶点,顶点 和和 称称图图.称边称边为为有向边有向边或或弧弧,称称是从是从连接连接,称,称 为为e的的尾尾,称,称 为为e的的头头.若图若图G中的边均为无序偶对中的边均为无序偶对 ,称,称G为为无向图无向图.称称为为e的的端点端点.既有无向边又有有向边的图称为既有无向边又有有向边的图称为混合图混合图.第16页,共40页,编辑于2022年,星期一 常用术语常
8、用术语1)边和它的两端点称为互相边和它的两端点称为互相关联关联.2)与同一条边关联的两个端点称与同一条边关联的两个端点称为为相邻相邻的顶点,与同一个顶点的顶点,与同一个顶点 点关联的两条边称为点关联的两条边称为相邻相邻的边的边.3)端点重合为一点的边称为端点重合为一点的边称为环环,端点不相同的边称为端点不相同的边称为连杆连杆.4)若一对顶点之间有两条以上的边联结,则这些边若一对顶点之间有两条以上的边联结,则这些边 称为称为重边重边5)既没有环也没有重边的图,称为既没有环也没有重边的图,称为简单图简单图 第17页,共40页,编辑于2022年,星期一 常用术语常用术语6)任意两顶点都相邻的简单图任
9、意两顶点都相邻的简单图,称为完全图称为完全图.记为记为Kv.7)若若 ,且且X 中任意两顶点不中任意两顶点不,相邻,相邻,Y 中任意两顶点不相邻,则称为中任意两顶点不相邻,则称为二部图二部图或或 偶图偶图;若;若X中每一顶点皆与中每一顶点皆与Y 中一切顶点相邻中一切顶点相邻,称为称为完全二部图完全二部图或或完全偶图完全偶图,记为记为 (m=|X|,n=|Y|)8)图图 叫做叫做星星.二部图二部图第18页,共40页,编辑于2022年,星期一2)2)赋权图与子图赋权图与子图 定义定义 若图若图 的每一条边的每一条边e 都赋以都赋以一个实数一个实数w(e),称,称w(e)为边为边e的的权权,G 连同
10、边上的权连同边上的权称为称为赋权图赋权图.定义定义 设设 和和 是两个图是两个图.1)若若 ,称称 是是 的一个的一个子图子图,记记 2)若若 ,则称,则称 是是 的的生成子图生成子图.3)若若 ,且,且 ,以,以 为顶点集,以两端点为顶点集,以两端点 均在均在 中的边的全体为边集的图中的边的全体为边集的图 的子图,称的子图,称 为为 的的由由 导出的子图导出的子图,记为,记为 .4)若若 ,且,且 ,以,以 为边集,以为边集,以 的端点的端点 集为顶点集的图集为顶点集的图 的子图,称为的子图,称为 的的由由 导出的导出的 边导出的子图边导出的子图,记为,记为 .第19页,共40页,编辑于20
11、22年,星期一 3)若若 ,且,且 ,以,以 为顶点集,以两端点为顶点集,以两端点 均在均在 中的边的全体为边集的图中的边的全体为边集的图 的子图,称的子图,称 4)若若 ,且,且 ,以,以 为边集,以为边集,以 的端点的端点 集为顶点集的图集为顶点集的图 的子图,称为的子图,称为 的的由由 导出的导出的 边导出的子图边导出的子图,记为,记为 .为为 的的由由 导出的子图导出的子图,记为,记为 .第20页,共40页,编辑于2022年,星期一3)3)图的矩阵表示图的矩阵表示 邻接矩阵邻接矩阵:1)对无向图对无向图 ,其邻接矩阵,其邻接矩阵 ,其中:,其中:(以下均假设图为简单图以下均假设图为简单
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 讲图论 模型 PPT 讲稿
限制150内