第1讲图论模型精选文档.ppt

《第1讲图论模型精选文档.ppt》由会员分享，可在线阅读，更多相关《第1讲图论模型精选文档.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第第第1 1讲图论模型讲图论模型讲图论模型讲图论模型本讲稿第一页，共四十页 一一 图图 论论 简简 介介 图论的起源图论的起源：图论是组合数学的一个分支,它起源于1736年欧拉的第一篇关于图论的论文，这篇论文解决了著名的“哥尼斯堡七桥问题”，从而使欧拉成为图论的创始人。本讲稿第二页，共四十页1 1.哥尼斯堡哥尼斯堡“七桥七桥”问题问题：格尼斯堡人在寻找一条路线本讲稿第四页，共四十页 欧欧 拉拉 图图定义定义 一个图,如果能够从一点出发,经过每条边一次且仅一次再回到起点,则称为欧拉图 欧拉在论文中给出并证明了判断欧拉图的充分必要条件定理,并证明了七桥图不是欧拉图。本讲稿第五页，共四十页 从这个

2、问题可以看出：从这个问题可以看出：图：图：图用点代表各个事物,用边代表各个事物间的二元关系。所以，图是研究集合上的二元关系的工具，是建立数学模型的一个重要手段。本讲稿第六页，共四十页 2 2、一百多年以后、一百多年以后 “七桥”问题以后，图论的研究停滞了一百多年，直到1847年，基尔霍夫用“树”图解决了电路理论中的求解联立方程的问题，十年后凯莱用“树”图计算有机化学中的问题。在这一时期流行着两个著名的图论问题：哈密尔顿回路问题和“四色猜想”问题。本讲稿第七页，共四十页 3 3、哈密尔顿回路问题、哈密尔顿回路问题 1856年,英国数学家哈密尔顿设计了一个周游世界的游戏，他在一个正十二面体的二十个

3、顶点上标上二十个著名城市的名字，要求游戏者从一个城市出发，经过每一个城市一次且仅一次，然后回到出发点。本讲稿第八页，共四十页哈密尔顿回路图：哈密尔顿回路图：示意图：此路线称为：哈密尔顿回路，而此图称为：哈密尔顿图。本讲稿第九页，共四十页4 4、“四四 色色 猜猜 想想”问问 题题 人们在长期为地图(平面图)上色时发现，最少只要四种颜色，就能使得有相邻国界的国家涂上不同的颜色 四色猜想的证明一直没有解决，直到一百多年后，在计算机出现以后，于1976年用计算机算了1200多小时，才证明了四色猜想问题。本讲稿第十页，共四十页 5 5、又过了半个世纪、又过了半个世纪 四色猜想问题出现后，图论的研究又停

4、滞了半个世纪，直到1920年科尼格写了许多关于图论方面的论文，并于1936年发表了第一本关于图论的书。此后图论从理论上到应用上都有了很大发展。特别是计算机的出现使图论得到飞跃的发展。本讲稿第十一页，共四十页 图论的重要性图论的重要性 图论是组合数学的一个分支，与其它数学分支如群论、矩阵论、集合论、概率论、拓扑学、数值分析等有着密切的联系。又由于图论给含有二元关系的系统提供了数学模型，因而在许多领域里都具有越来越重要的地位，并且在物理、化学、信息学、运筹学等各方面都取得了丰硕的成果。从二十世际50 年代以来，由于计算机的迅速发展，有力地推动了图论的发展，使得图论成为数学领域里发展最快的分支之一。

5、本讲稿第十二页，共四十页2.图论的基本概念图论的基本概念1)图的概念图的概念2)赋权图与子图赋权图与子图3)图的矩阵表示图的矩阵表示4)图的顶点度图的顶点度5)路和连通路和连通本讲稿第十三页，共四十页1)图的概念图的概念 定义定义 一个一个图图G是指一个二元组是指一个二元组(V(G),E(G)，其中，其中:其中每个元素称为图其中每个元素称为图G的的顶点顶点.组成的集合，即称为组成的集合，即称为边集边集,其中元素称为其中元素称为边边.定义定义 图图G的的阶阶是指图的顶点数是指图的顶点数|V(G)|,用用来表示；来表示；图的边的数目图的边的数目|E(G)|用用 来表示来表示.也用也用来表示边来表示

6、边是非空有限集，称为是非空有限集，称为顶顶点集点集，1)2)E(G)是顶点集是顶点集V(G)中的无序或有序的元素偶对中的无序或有序的元素偶对表示图，表示图，简记简记 用用本讲稿第十四页，共四十页 定义 若一个图的顶点集和边集都是有限集，则称若一个图的顶点集和边集都是有限集，则称 其为其为有限图有限图.只有一个顶点的图称为只有一个顶点的图称为平凡图平凡图，其他的，其他的 所有图都称为所有图都称为非平凡图非平凡图.本讲稿第十五页，共四十页 定义若若图图G中的边均为有序偶对中的边均为有序偶对,称称G为为有向有向边边 为为无向边无向边，称，称e连接连接 和和 ，顶点，顶点 和和 称称图图.称边称边为为

7、有向边有向边或或弧弧,称称是从是从连接连接，称，称 为为e的的尾尾，称，称 为为e的的头头.若图若图G中的边均为无序偶对中的边均为无序偶对 ，称，称G为为无向图无向图.称称为为e的的端点端点.既有无向边又有有向边的图称为既有无向边又有有向边的图称为混合图混合图.本讲稿第十六页，共四十页 常用术语常用术语1)边和它的两端点称为互相边和它的两端点称为互相关联关联.2)与同一条边关联的两个端点称与同一条边关联的两个端点称为为相邻相邻的顶点，与同一个顶点的顶点，与同一个顶点 点关联的两条边称为点关联的两条边称为相邻相邻的边的边.3)端点重合为一点的边称为端点重合为一点的边称为环环，端点不相同的边称为端

8、点不相同的边称为连杆连杆.4)若一对顶点之间有两条以上的边联结，则这些边若一对顶点之间有两条以上的边联结，则这些边 称为称为重边重边5)既没有环也没有重边的图，称为既没有环也没有重边的图，称为简单图简单图 本讲稿第十七页，共四十页 常用术语常用术语6)任意两顶点都相邻的简单图任意两顶点都相邻的简单图,称为完全图称为完全图.记为记为Kv.7)若若 ，且且X 中任意两顶点不中任意两顶点不，相邻，相邻，Y 中任意两顶点不相邻，则称为中任意两顶点不相邻，则称为二部图二部图或或 偶图偶图；若；若X中每一顶点皆与中每一顶点皆与Y 中一切顶点相邻中一切顶点相邻,称为称为完全二部图完全二部图或或完全偶图完全偶

9、图,记为记为 (m=|X|,n=|Y|)8)图图 叫做叫做星星.二部图二部图本讲稿第十八页，共四十页2)2)赋权图与子图赋权图与子图 定义定义 若图若图 的每一条边的每一条边e 都赋以都赋以一个实数一个实数w(e)，称，称w(e)为边为边e的的权权，G 连同边上的权连同边上的权称为称为赋权图赋权图.定义定义 设设 和和 是两个图是两个图.1)若若 ,称称 是是 的一个的一个子图子图,记记 2)若若 ，则称，则称 是是 的的生成子图生成子图.3)若若 ，且，且 ，以，以 为顶点集，以两端点为顶点集，以两端点 均在均在 中的边的全体为边集的图中的边的全体为边集的图 的子图，称的子图，称 为为 的的

10、由由 导出的子图导出的子图，记为，记为 .4)若若 ，且，且 ，以，以 为边集，以为边集，以 的端点的端点 集为顶点集的图集为顶点集的图 的子图，称为的子图，称为 的的由由 导出的导出的 边导出的子图边导出的子图，记为，记为 .本讲稿第十九页，共四十页 3)若若 ，且，且 ，以，以 为顶点集，以两端点为顶点集，以两端点 均在均在 中的边的全体为边集的图中的边的全体为边集的图 的子图，称的子图，称 4)若若 ，且，且 ，以，以 为边集，以为边集，以 的端点的端点 集为顶点集的图集为顶点集的图 的子图，称为的子图，称为 的的由由 导出的导出的 边导出的子图边导出的子图，记为，记为 .为为 的的由由

11、 导出的子图导出的子图，记为，记为 .本讲稿第二十页，共四十页3)3)图的矩阵表示图的矩阵表示 邻接矩阵邻接矩阵:1)对无向图对无向图 ，其邻接矩阵，其邻接矩阵 ，其中：，其中：(以下均假设图为简单图以下均假设图为简单图).本讲稿第二十一页，共四十页2)对有向图对有向图 ,其邻接矩阵其邻接矩阵 ,其中：其中：本讲稿第二十二页，共四十页其中：其中：3)对有向赋权图对有向赋权图 ,其邻接矩阵其邻接矩阵 ,对于无向赋权图的邻接矩阵可类似定义对于无向赋权图的邻接矩阵可类似定义.本讲稿第二十三页，共四十页关联矩阵关联矩阵 1)对无向图对无向图 ，其关联矩阵，其关联矩阵 ,其中：其中：本讲稿第二十四页，共

12、四十页2)对有向图对有向图 ，其关联矩阵，其关联矩阵 ,其中：其中：本讲稿第二十五页，共四十页4)图的顶点度图的顶点度定义定义 1)在无向图在无向图G中，与顶点中，与顶点v关联的边的数目关联的边的数目(环环算两次算两次),称为顶点称为顶点v的的度度或或次数次数，记为，记为d(v)或或 dG(v).称度为奇数的顶点为称度为奇数的顶点为奇点奇点，度为偶数的顶点为，度为偶数的顶点为偶点偶点.2)在有向图中，从顶点在有向图中，从顶点v引出的边的数目称为顶点引出的边的数目称为顶点 v的的出度出度，记为，记为d+(v)，从顶点，从顶点v引入的边的数目称为引入的边的数目称为 v的的入度入度，记为，记为d-(

13、v).称称d(v)=d+(v)+d-(v)为顶点为顶点v的的 度度或或次数次数定理定理的个数为偶数的个数为偶数推论推论 任何图中奇点任何图中奇点本讲稿第二十六页，共四十页5)路和连通路和连通 定义定义1)无向图无向图G的一条的一条途径途径（或（或通道通道或或链链）是指）是指一个有限非空序列一个有限非空序列 ，它的项交替，它的项交替 地为顶点和边，使得对地为顶点和边，使得对 ，的端点是的端点是 和和 ,称称W是从是从 到到 的一条的一条途径途径，或一条，或一条 途径途径.整整数数k称为称为W的的长长.顶点顶点 和和 分别称为的分别称为的起点起点和和终点终点,而而 称为称为W的的内部顶点内部顶点.

14、2)若途径若途径W的边互不相同但顶点可重复，则称的边互不相同但顶点可重复，则称W为为迹迹或或简单链简单链.3)若途径若途径W的顶点和边均互不相同，则称的顶点和边均互不相同，则称W为为路路或或路径路径.一条起点为一条起点为 ,终点为终点为 的路称为的路称为 路路记为记为本讲稿第二十七页，共四十页 定义定义 1)途径途径 中由相继项构成子序列中由相继项构成子序列 称为途径称为途径W的的节节.2)起点与终点重合的途径称为起点与终点重合的途径称为闭途径闭途径.3)起点与终点重合的的路称为起点与终点重合的的路称为圈圈(或或回路回路)，长，长为为k的圈称为的圈称为k阶圈阶圈，记为，记为Ck.4)若在图若在

15、图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为为有向途径有向途径.例例

16、在右图中：在右图中：途径或链：途径或链：迹或简单链：迹或简单链：路或路径：路或路径：圈或回路：圈或回路：本讲稿第二十九页，共四十页3.可达矩阵算法及可达矩阵算法及MATLAB实现实现【算法思想算法思想】一般的，设一般的，设n阶有向图的邻接矩阵为阶有向图的邻接矩阵为A,由由A可可得图得图D的可达矩阵，不妨设为的可达矩阵，不妨设为P,其步骤如下：其步骤如下：首先：求出首先：求出Bn=A+A2+.+An然后：把矩阵然后：把矩阵Bn中不为中不为0的元素改为的元素改为1，而为，而为0的的 元素不变，这样所得到的矩阵为可达矩阵。元素不变，这样所得到的矩阵为可达矩阵。本讲稿第三十页，共四十页【算法的算法的M

17、ATLAB程序程序】%计算图的可达矩阵计算图的可达矩阵function P=dgraf(A)n=size(A,1);P=A;%计算矩阵计算矩阵Bnfor i=2:n P=P+Ai;endP(P=0)=1;将不为0的元素变为1P;本讲稿第三十一页，共四十页例例1：求图的可达矩阵：求图的可达矩阵A=0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0本讲稿第三十二页，共四十页4.关联矩阵和邻接矩阵算法及关联矩阵和邻接矩阵算法及MATLAB实现实现【程序参数说明程序参数说明】F表示所给出图的相应矩阵。表示所给出图的相应矩阵。W表示程序运行结束后的结果。即所转换的结果。表示程序运行结束后的结

18、果。即所转换的结果。当当f=0时，完成邻接矩阵转换为关联矩阵；时，完成邻接矩阵转换为关联矩阵；当当f=1时，完成关联矩阵转换为邻接矩阵。时，完成关联矩阵转换为邻接矩阵。本讲稿第三十三页，共四十页【算法的算法的MATLAB实现实现】%无向图的关联矩阵和邻接矩阵的相互转换无向图的关联矩阵和邻接矩阵的相互转换function W=incandadf(F,f)if f=0%邻接转关联邻接转关联 m=sum(sum(F)/2;%计算图的边数计算图的边数 n=size(F,1);W=zeros(n,m);k=1;for i=1:n for j=i:n if F(i,j)=0 W(i,k)=1;%给边的始点

19、赋值为1 W(j,k)=1;%给边的终点赋值为1 k=k+1;end end end本讲稿第三十四页，共四十页elseif f=1 m=size(F,2);n=size(F,1);W=zeros(n,n);for i=1:m a=find(F(:,i)=0);W(a(1),a(2)=1;W(a(2),a(1)=1;endelse fprint(Please imput the right value of f);endW;本讲稿第三十五页，共四十页例例2：已知图：已知图G的邻接矩阵的邻接矩阵F=0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0求图求图G的关联矩阵的关联矩阵例例3：

20、已知图：已知图G的关联矩阵的关联矩阵F=1 1 1 0 0 0 1 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1求图求图G的邻接矩阵的邻接矩阵本讲稿第三十六页，共四十页【有向图矩阵转换的有向图矩阵转换的MATLAB实现实现】%有向图的关联矩阵和邻接矩阵的转换function W=mattransf(F,f)if f=0%邻接转关联 m=sum(sum(F);%计算图的边数 n=size(F,1);W=zeros(n,m);k=1;for i=1:n for j=i:n if F(i,j)=0 W(i,k)=1;%关联矩阵的始发点为1 W(j,k)=-1;%关联矩阵的终点为

21、-1 k=k+1;end end end本讲稿第三十七页，共四十页elseif f=1%关联矩阵转换为邻接矩阵 m=size(F,2);n=size(F,1);W=zeros(n,n);for i=1:m a=find(F(:,i)=0);%有向边的两个顶点 if F(a(1),i)=1 W(a(1),a(2)=1;%有向边由a(1)指向(2)else W(a(2),a(1)=1;%有向边由a(2)指向(1)end end else fprint(Please imput the right value of f);endW;本讲稿第三十八页，共四十页例例4：已知图：已知图G的邻接矩阵的邻接矩阵F=0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0】求图求图G的关联矩阵的关联矩阵本讲稿第三十九页，共四十页第一节课习题：第一节课习题：1.求给定图求给定图6的邻接矩阵和可达矩阵的邻接矩阵和可达矩阵2.求出图求出图7的关联矩阵和邻接矩阵并用程序转换的关联矩阵和邻接矩阵并用程序转换3.试将某图的关联矩阵试将某图的关联矩阵 F=1 1 1 0 0 0 -1 0 0 1 1 0 0-1 0-1 0 1 -1 0-1 0-1-1 转换为邻接矩阵。转换为邻接矩阵。图图6图图7本讲稿第四十页，共四十页