第1讲图论模型.ppt

第一讲 图论模型 一 图 论 简 介 图论的起源： 图论是组合数学的一个分支,它起源于1736年欧拉的第一篇关于图论的论文，这篇论文解决了著名的 “哥尼斯堡七桥问题” ，从而使欧拉成为图论的创始人。 1 哥尼斯堡七桥问题 哥尼斯堡位于前苏联的加里宁格勒，历史上曾经是德国东普鲁士省的省会，普雷格尔河横穿城堡，河中有两个小岛，共有七座桥连接两岸和小岛。 1. 哥尼斯堡“七桥”问题： 格尼斯堡人在寻找一条路线 欧 拉 图 定义 一个图,如果能够从一点出发,经过每条边一次且仅一次再回到起点,则称为欧拉图 欧拉在论文中给出并证明了判断欧拉图的充分必要条件定理,并证明了七桥图不是欧拉图。 从这个问题可以看出： 图： 图用点代表各个事物,用边代表各个事物间的二元关系。 所以，图是研究集合上的二元关系的工具，是建立数学模型的一个重要手段。 2、一百多年以后 “七桥”问题以后，图论的研究停滞了一百多年，直到1847年，基尔霍夫用“树”图解决了电路理论中的求解联立方程的问题，十年后凯莱用 “树” 图计算有机化学中的问题。在这一时期流行着两个著名的图论问题：哈密尔顿回路问题和 “四色猜想” 问题。 3、哈密尔顿回路问题 1856年,英国数学家哈密尔顿设计了一个周游世界的游戏，他在一个正十二面体的二十个顶点上标上二十个著名城市的名字，要求游戏者从一个城市出发，经过每一个城市一次且仅一次，然后回到出发点。 哈密尔顿回路图： 示意图： 此路线称为：哈密尔顿回路， 而此图称为：哈密尔顿图。 4、“四 色 猜 想” 问 题 人们在长期为地图(平面图)上色时发现，最少只要四种颜色，就能使得有相邻国界的国家涂上不同的颜色 四色猜想的证明一直没有解决，直到一百多年后，在计算机出现以后，于1976年用计算机算了1200多小时，才证明了四色猜想问题。 5、又过了半个世纪 四色猜想问题出现后，图论的研究又停滞了半个世纪，直到1920年科尼格写了许多关于图论方面的论文，并于1936年发表了第一本关于图论的书。此后图论从理论上到应用上都有了很大发展。特别是计算机的出现使图论得到飞跃的发展。 图论的重要性 图论是组合数学的一个分支，与其它数学分支如群论、矩阵论、集合论、概率论、拓扑学、数值分析等有着密切的联系 。 又由于图论给含有二元关系的系统提供了数学模型，因而在许多领域里都具有越来越重要的地位，并且在物理、化学、信息学、运筹学等各方面都取得了丰硕的成果。从二十世际50 年代以来，由于计算机的迅速发展，有力地推动了图论的发展，使得图论成为数学领域里发展最快的分支之一。 2. 图论的基本概念 1) 图的概念 定义 若一个图的顶点集和边集都是有限集，则称 定义若图G中的边均为有序偶对 常用术语 2) 赋权图与子图 定义 若图 的每一条边e 都赋以 3) 图的矩阵表示 关联矩阵 4) 图的顶点度 5) 路和连通 3. 可达矩阵算法及MATLAB实现 4.关联矩阵和邻接矩阵算法及MATLAB实现 定义 1) 途径 中由相继项构成子序列 称为途径W的节. 2) 起点与终点重合的途径称为闭途径. 3) 起点与终点重合的的路称为圈(或回路)，长 为k的圈称为k阶圈，记为Ck. 4) 若在图G中存在(u,v)路，则称顶点u和v在图G 中连通. 5) 若在图G中顶点u和v是连通的，则顶点u和v之 之间的距离d(u,v)是指图G中最短(u,v)路的长；若没 没有路连接u和v，则定义为无穷大. 6) 图G中任意两点皆连通的图称为连通图． 7) 对于有向图G，若 ，且 有 类似地，可定义有向迹，有向路和有向圈. 头 和尾 ，则称W为有向途径. 例 在右图中： 途径或链： 迹或简单链： 路或路径： 圈或回路： 【算法思想】 一般的，设n阶有向图的邻接矩阵为A,由A可 得图D的可达矩阵，不妨设为P,其步骤如下： 首先：求出Bn=A+A^2+….+A^n 然后：把矩阵Bn中不为0的元素改为1，而为0的 元素不变，这样所