《西南财经大学天府学院《离散数学》课件-第7章 图的基本概念》由会员分享，可在线阅读，更多相关《西南财经大学天府学院《离散数学》课件-第7章 图的基本概念（108页珍藏版）》请在金锄头文库上搜索。
1、第七章 图的基本概念l图图论论起起源源于于1736年年欧欧拉拉(Enler)的的第第一一篇篇图图论论 论论文文, 解解决决了了“哥哥尼尼斯斯堡堡的的七七桥桥问问题题”。在在哥哥尼尼斯斯堡的匹格河上有七座桥堡的匹格河上有七座桥。西南财经大学天府学院离散数学 陆地陆地 岛屿岛屿 岛屿岛屿 陆地陆地哥尼斯堡七桥问题哥尼斯堡七桥问题 如何不重复地走完七桥后回到起点如何不重复地走完七桥后回到起点？ 。 。 。 。A AB BCD Dl当当时时人人们们热热衷衷于于这这样样的的游游戏戏：设设想想从从任任一一个个地地方方出出发发通通过过每每座座桥桥一一次次且且仅仅一一次次后后回回到到原原地地, 这是否可能这是
2、否可能?但多次实践都发现不行但多次实践都发现不行l1727 年年欧欧拉拉的的朋朋友友向向欧欧拉拉提提出出了了这这个个问问题题是否有解？是否有解？l1736 年年欧欧拉拉用用图图论论的的方方法法解解决决了了这这个个问问题题,写了第一篇图论的论文写了第一篇图论的论文,成为图论的创始人。成为图论的创始人。l后来称此问题为哥尼斯堡七桥问题。后来称此问题为哥尼斯堡七桥问题。l在在图图a中中,用用边边表表示示桥桥,顶顶点点表表示示岛岛屿屿和和河河的的两岸两岸,便得到一个图便得到一个图,如图如图b所示。所示。很很显显然然,通通过过哥哥尼尼斯斯堡堡七七座座桥桥中中每每一一座座一一次次且且仅仅一一次次的的问问题
3、题等等价价于于在在右右图图(b)中中找找一一条条闭链闭链,使使得得它它的的每每一一边边出出现现一一次次且且仅仅一一次次, 也也就就是是如何一笔画的问题。如何一笔画的问题。第七章 图的基本概念l但在此之后但在此之后100年间，没有大的进展。年间，没有大的进展。l直到直到Kirchhoff(克希霍夫克希霍夫)用树的理论解决了电用树的理论解决了电 网络问题，网络问题，l这些结果引起了人们的重视这些结果引起了人们的重视,图论的研究进入图论的研究进入 了一个发展时期了一个发展时期,l在在此此期期间间,出出现现了了两两个个著著名名的的问问题题:四四色色问问题题和和Hamilton回路问题回路问题,成为不少
4、数学家的研究目标。成为不少数学家的研究目标。l但在但在19世纪后期和二十世纪初，图论的研究再世纪后期和二十世纪初，图论的研究再 次处于停顿状态。次处于停顿状态。l直直到到1920年年, 科科尼尼格格(Konig)撰撰写写了了许许多多图图论论方方面面的的论论文文。在在1936年年科科尼尼格格(Konig)发发表表了了第第一一本本图图论论书书籍籍有有限限图图与与无无限限图图理理论论, 总总结结了了200年来图论研究的主要成果。年来图论研究的主要成果。l此后的此后的50年年, 图论经历了一场爆炸性的发展图论经历了一场爆炸性的发展, 成为数学科学中一门独立的学科。成为数学科学中一门独立的学科。l主要分
5、支有图论、超图理论、极值图论、算主要分支有图论、超图理论、极值图论、算 法图论、网络图论和随机图论等。法图论、网络图论和随机图论等。l几十年来图论在理论上和应用上都得到很大几十年来图论在理论上和应用上都得到很大 的发展的发展, 特别是在近特别是在近30多年来由于计算机的广多年来由于计算机的广 泛应用而又得到飞跃的发展。泛应用而又得到飞跃的发展。l在计算机科学、运筹学、化学、物理和社会在计算机科学、运筹学、化学、物理和社会 科学等方面都取得了不少成果，对计算机学科学等方面都取得了不少成果，对计算机学 科中的操作系统研究、编译技术、人工智能科中的操作系统研究、编译技术、人工智能 和计算机网络等方面
6、都有广泛的应用。和计算机网络等方面都有广泛的应用。l这里主要讨论图的基本概念和算法这里主要讨论图的基本概念和算法, 为今后的为今后的 学习和研究打下基础。学习和研究打下基础。 概概 述述 图图论论是是一一个个应应用用十十分分广广泛泛而而又又极极其其有有趣趣的的数学分支。物理、化学、生物、科学管理、计数学分支。物理、化学、生物、科学管理、计算算机机等等各各个个领领域域都都可可找找到到图图论论的的足足迹迹。本本章章主主要要介介绍绍图图论论的的一一些些基基本本知知识识、图图论论中中常常用用的的初初等等方方法法。试试图图在在抽抽象象理理论论和和具具体体编编程程之之间间为为同同学们架设一座桥梁。学们架设
7、一座桥梁。 为为了了让让大大家家知知道道图图论论主主要要讲讲些些什什么么，我我们们先举几个例子。先举几个例子。例例7.17.1 图图7 71 1画画的的是是一一个个“图图”, ,当当然然究究竞竞什什么么叫叫做做“图图”, ,以以后后还还要要仔仔细细讲讲。这这里里只只要要先先记记住住, ,我们研究的图我们研究的图, ,指的是由顶点和线组成的图形。指的是由顶点和线组成的图形。V V1010走走哪哪条条路路最最近近？这这个个问问题题通通常常叫叫做做最最短短路路径径问问题题。这这是是一一个个有有很很大大现现实实意意义义的的问问题题, ,它它不不仅仅出出现现在在各各种种运运输输问问题题中中, ,而而且且
8、在在电电路路设设计计等等问问题题中中也也有有用用。因因为为这这种种问问题题研研究究的的是是从从V V1 1到到V V1010的的所所有有路路径径中中, ,哪哪一一条条路路最最短短? ?因因此此它它是是一一个个极极大大极极小小问问题题, ,即即极极值值问问题题, ,而而它它又又和和一一个个“图图”密密切切联联系系着着, ,因因此此这这种种问问题题就就叫叫做做图图论论中中的的极极值值问问题。题。 我们先把图我们先把图7 71 1看看成是一个公路成是一个公路, ,V V1 1, , V V1 1, ,V,V1010是一些城是一些城镇镇, ,每条线旁边的每条线旁边的数字代表这一段公数字代表这一段公路的
9、长度。现在问路的长度。现在问要从要从V V1 1把货物运到把货物运到图图7-1其其公公路路网网的的一一个个站站点点或或者者至至少少破破坏坏敌敌人人哪哪几几个个站站点点, ,就就可可摧摧毁毁敌敌方方整整个个运运输输线线。这这类类问问题题称称为为图图的的连连通通性性问问题题。原原来来的的公公路路网网, ,任任意意两两个个站站点点之之间间互互相相可可达达, ,这这样样的的图图称称作作连连通通图图。一一旦旦删删去去一一些些( (或或一一个个) )点点以以及及和和它它们们关关联联的的边边时时, ,这这张张图图就就不不再再成成为为一一张张完完整整的的连连通通图图了了。军军事事指指挥挥中中这类问题就很多。这
10、类问题就很多。图图7-1例例7.27.2 还还是是把把图图7 71 1看看 成成 公公 路路 网网, ,V V1 1, , V V1 1, ,V,V1010看看成成公公路路网网的的一一个个站站点点, ,若若这这个个公公路路网网目目前前被被敌敌方方占占领领。请请分分析析一一下下, ,能能否否仅仅破破坏坏例例7.37.3 飞飞行行大大队队有有若若干干个个来来自自各各地地的的驾驾驶驶员员, ,专专门门驾驾驶驶一一种种型型号号的的飞飞机机, ,这这种种飞飞机机每每架架有有两两个个驾驾驶驶员员。由由于于种种种种原原因因, ,例如相互配合的例如相互配合的图图7-2问问题题, ,有有些些驾驾驶驶员员, ,不
11、不能能在在同同一一架架飞飞机机上上飞飞行行, ,问问如何搭配驾驶员才能使出航的飞机最多如何搭配驾驶员才能使出航的飞机最多。 为为简简单单起起见见, ,假假设设有有10个个驾驾驶驶员员, ,图图7-27-2中中的的V1, ,V10就就代代表表这这1010个个驾驾驶驶员员。如如果果两两个个人人可可以以同同机机飞飞行行, ,就就在在代代表表他他们们两两个个之之间间连连一一条条线线; ;两两个个人人不不能能同同机机飞飞行行, ,就就不不连连。例例如如V1和和V2可可以以同同机机飞行飞行, ,而而V1和和V3就不行。就不行。图图7-2图中没有公共端点的一组线叫做一个图中没有公共端点的一组线叫做一个“匹配
12、匹配”。上面问。上面问题就成为题就成为: :如何找一个包含最多线的匹配如何找一个包含最多线的匹配? ? 这个问题叫做这个问题叫做图图的最大匹配问题。请大家试试看，能不能从图的最大匹配问题。请大家试试看，能不能从图7 72 2中找中找出一个包含出一个包含4 4条线的匹配条线的匹配, ,再试试能不能找到包含再试试能不能找到包含5 5条线的条线的匹配。匹配。 像上述例子那样像上述例子那样, ,将实际生活中的事物分析转化为图将实际生活中的事物分析转化为图论问题的实例还很多论问题的实例还很多, , 后面还要讲后面还要讲, , 这里就不多介绍了。这里就不多介绍了。画了这个图后画了这个图后, ,就可以就可以
13、研究搭配飞行员的问题研究搭配飞行员的问题了。图了。图7 72 2中画的中画的3 3条条租线就代表了一种搭配租线就代表了一种搭配方案。由于一个飞行员方案。由于一个飞行员不能同时派往两架飞机。不能同时派往两架飞机。因此任何两条粗线不能因此任何两条粗线不能有公共的端点有公共的端点, ,把一个把一个 v4v2v3e1 e3e2e4e5e6e7图论研究的对象是图图论研究的对象是图, ,什么是图呢什么是图呢? ? 什么是图？从前面我们可以看出：一个图什么是图？从前面我们可以看出：一个图一般用图形表示。它可以由两部分组成：一部一般用图形表示。它可以由两部分组成：一部分是一些点，我们称其为分是一些点，我们称其
14、为结点结点，如下图中的，如下图中的v1, v2, v3, v4诸点；另一部分是连接这些点的线，我诸点；另一部分是连接这些点的线，我们称其为们称其为边边，如下图中的，如下图中的e1, e2, e3, e4, e5, e6, e7,。 图图G是由非空结点集合是由非空结点集合V=v1, v2, vn以及以及边集合边集合E= e1, e2, en所组成，其中每条边可用所组成，其中每条边可用一个结点对表示之，这样的一个图一个结点对表示之，这样的一个图G可用示为可用示为 G=V，E v1边边。例例如如V V1 1与与V V2 2之之间间有有两两条条边边。若若连连接接两两个个顶顶点点的的边边有有多多条条,
15、,则则这这些些边边称称之之为为平平行行边边。V V2 2与与V V3 3之之间间有有一一条条边边, , V V2 2与与V V4 4之之间间没没有有边边等等等等。V V1 1与与V V1 1本本身身也也有有边边相相连连, ,这这样样的的边边叫叫做做环环。当当然然, ,也也可可能能出出现现某某顶顶点点与与图图中中除除它它外外的的每每一一顶顶点点均均不不相相连连的的情况情况, ,这种顶点称为这种顶点称为孤立点孤立点, ,例如例如与与V V1111 。也也就就是是说说图图有有若若干干个个不不同同的的点点V V1 1, , , V V1111, ,称称之之为为顶顶点点。这这些些顶顶点点中中有有一一些些
16、是是用用直直线线段段或或曲曲线线段段连连接接的的, ,这这些些直直线段和曲线段称作线段和曲线段称作例例7.4 有四座城市：有四座城市： v1, v2, v3, v4，其中其中v1与与v2间间 v1与与v4间；间； v2与与v3间有直达长话线相联，间有直达长话线相联，将此事实用图的方法表示之。将此事实用图的方法表示之。解：图中的结点集为解：图中的结点集为 V=v1, v2, v3, v4 图中的边集为图中的边集为 E=e1, e2, e3 其中，其中， e1=( v1, v2 ) e2=( v1, v4 ) e3=( v2, v3 ) 这个图可用这个图可用 G = 表示表示v1v2v3v4e1e3e2无向图：无向图：图中所有的边图中所有的边均为无向边均为无向边例例7.5 有四个程序：有四个程序： v1, v2, v3, v4，它们间有一些它们间有一些调用关系：调用关系： v1能调用能调用v2； v2能调用能调用v3；v3能调用能调用v4，将此事实用图的方法表示之。，将此事实用图的方法表示之。解：图中的结点集为解：图中的结点集为 V=v1, v2, v3, v4 图中的边集为图中的边集为
