实用工程数学教学课件作者盛光进电子教案7图论1课件

《实用工程数学教学课件作者盛光进电子教案7图论1课件》由会员分享，可在线阅读，更多相关《实用工程数学教学课件作者盛光进电子教案7图论1课件（81页珍藏版）》请在金锄头文库上搜索。

1、,目 录,第七章 图论,7.1 图的基本概念,第一节 图的基本概念,7.1 图的基本概念,图论起源于1736年欧拉(Enler)的第一篇图论论文, 解决了“哥尼斯堡的七桥问题”.,陆地 岛屿 岛屿 陆地,哥尼斯堡七桥问题 如何不重复地走完七桥后回到起点？,7.1 图的基本概念,图论起源,7.1 图的基本概念,当时人们热衷于这样的游戏：设想从任一个地方出发通过每座桥一次且仅一次后回到原地, 这是否可能?但多次实践都发现不行。,1727 年欧拉的朋友向欧拉提出了这个问题是否有解？ 1736 年欧拉用图论的方法解决了这个问题，写了第一篇图论的论文，成为图论的创始人。 后来称此问题为哥尼斯堡七桥问题。

2、,图论起源,7.1 图的基本概念,图论在理论上和应用上都得到很大的发展, 特别是在近30多年来由于计算机的广泛应用而又得到飞跃的发展。 在计算机科学、运筹学、化学、物理和社会科学等方面都取得了不少成果，对计算机学科中的操作系统研究、编译技术、人工智能和计算机网络等方面都有广泛的应用。 图论是一个应用十分广泛而又极其有趣的数学分支。物理、化学、生物、科学管理、计算机等各个领域都可找到图论的足迹。 本章主要介绍图论的一些基本知识、图论中常用的初等方法。图论在抽象理论和具体编程之间为同学们架设一座桥梁。 为了让大家知道图论主要讲些什么，我们先举几个例子。,图论概述,7.1 图的基本概念,【引例1】

3、考虑一张航线地图，图中用点表示城市，当两个城市间有直达航班时，就用一条线将相应的点连接起来。这种航线地图的一部分如下图所示,7.1 图的基本概念,图论引例,【引例】 我们把图71看成是一个公路网，网V1,V2,V10是一些城镇,每条线旁边的数字代表这一段公路的长度。现在问要从V1把货物运到V10走哪条路最近？,这个问题通常叫做最短路径问题。这是一个有很大现实意义的问题,它不仅出现在各种运输问题中,而且在电路设计等问题中也有用。,因为这种问题研究的是从V1到V10的所有路径中,哪一条路最短?因此它是一个极大极小问题,即极值问题,而它又和一个“图”密切联系着,因此这种问题就叫做图论中的极值问题。,

4、图7-1,7.1 图的基本概念,这类问题称为图的连通性问题。,图7-1,【引例】 还是把图71看成公路网,V1, V2,V10看成公路网的站点,若这个公路网目前被敌方占领。请分析一下,能否仅破坏其公路网的一个站点或者至少破坏敌人哪几个站点，就可摧毁敌方整个运输线。,如果公路网,任意两个站点之间互相可达,这样的图称作连通图。一旦删去一些(或一个)点以及和它们关联的边时,这张图就不再成为一张完整的连通图了。军事指挥中这类问题就很多。,7.1 图的基本概念,图论引例,【例3】 飞行大队有若干个来自各地的驾驶员,专门驾驶一种型号的飞机，这种飞机每架有两个驾驶员。由于种种原因,例如相互配合的问题，有些驾

5、驶员，不能在同一架飞机上飞行，问如何搭配驾驶员才能使出航的飞机最多？,图7-2,为简单起见,假设有10个驾驶员,图7-2中的V1,，V10就代表这10个驾驶员。如果两个人可以同机飞行,就在代表他们两个之间连一条线;两个人不能同机飞行,就不连。,7.1 图的基本概念,图论引例,上面问题就成为:如何找一个包含最多线的匹配? 这个问题叫做图的最大匹配问题。请大家试试看，能不能从图72中找出一个包含4条线的匹配，再试试能不能找到包含5条线的匹配。 像上述例子那样,将实际生活中的事物分析转化为图论问题的实例还很多, 这里就不多介绍了。,画了这个图后,就可以研究搭配飞行员的问题了。图72中画的3条粗线就代

6、表了一种搭配方案。由于一个飞行员不能同时派往两架飞机。因此任何两条粗线不能有公共的端点,把一个图中没有公共端点的一组线叫做一个“匹配”.,假设有一群人和一组工作，这群人中的某些人能够做这组工作中的某些工作。例如，有3个人A、B和C，3件工作D、E和F. 假设A只能做工作D，B能做工作E和F，C能做工作D和E。则这种情形可用下图表示，其中，在人和这个人能够做的工作之间画有线段。,7.1 图的基本概念,图是一个包含有限的点（称之为结点）和连接一对顶点的线段（称之为边）。,用图形表示一组对象，其中有些对象是有联系的，有些也是没有联系的同一个图形也可以表示不同的含义。例如，引例中的图，即可以表示从V1

7、把货物运到V10走哪条路最近的问题，又可以表示公路网的运输线摧毁的最少站点问题 对于这种图形，我们感兴趣的只是有多少个点和哪些结点之间有线连接，至于连线的长短曲直和结点的位置却无关紧要，只要求每一条线都起始于一个点，而终止于另一个点。,7.1 图的基本概念,7.1 图的基本概念,图论研究的对象是图。 什么是图？ 一个图一般用图形表示。它可以由两部分组成：一部分是一些点，我们称其为结点，如下图中的v1,v2, v3,v4诸点；另一部分是连接这些点的线，我们称其为边，如下图中的e1,e2,e3,e4,e5,e6,e7。,图G是由非空结点集合V=v1, v2, vn以及边集合E= e1, e2, e

8、n所组成，其中每条边可用一个结点对表示之，这样的一个图G可表示为 G=V，E,观察下图,7.1 图的基本概念,【定义1 】 一个无向图 G是一个二元组，即 G=，其中 (1)V是有限的非空集合，称为顶点集, 其元素称为结点 或顶点 (2) E 是以结点的无序对为元素的集合，称为边集, 其 元素称为无向边，简称为边每条边可用一个无序结点对表 示。即表示为,一、图的基本概念,图的表示：用图形表示无向图时，常用小圆圈或实心点表示结点，用顶点之间的连线表示无向边.,7.1 图的基本概念,【例1】 设 ，其中 ， , 则 G可用图表示为：,7.1 图的基本概念,【定义2】 一个有向图是一个有序的二元组,

9、 记作 D， 其中 (1) V ，称为顶点集，其元素称为结点或顶点。 (2) E 称为边集，（它是笛卡儿积VV的子集）, 其元素称为有向边，简称为边。,用图形表示无(有)向图时，常用小圆圈或实心点表示结点，用顶点之间的连线表示无向边，用有方向的边表示有向边。,每条边可用一个有序结点对表示。即表示为,7.1 图的基本概念,【例如】 有四个程序： v1, v2, v3, v4，它们间有一些调用关系： v1能调用v2，v2能调用v3，v2能调用v4，将此事实用图的方法表示之。,有向图： 图中所有的边均为有向边,【解】图中的结点集为,这个图可用 D = 表示.,图中的边集为,7.1 图的基本概念,注意

10、到无向图与有向图集合表示的异同了吗？,【例2】 画出下列图形。 (1) G =,其中V=v1,v2,v3,v4,v5, E =(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v1,v5), (v2,v5), (v4,v5)。 (2) D =,其中V=a,b,c,d, E=, ,。,7.1 图的基本概念,【例3】 画出下列图形。 （1） G=,其中V=v1,v2,v3,v4,v5, E=(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v1,v5), (v2,v5), (v4,v5).,【解】（1）：作图如下,7.1 图的基本概念,【例3】 画出

11、下列图形。 (2) D=,其中V=a,c,b,d , E=, ,。,【解】（2）作图如下：,7.1 图的基本概念,与图有关的概念和规定,设 G=为一有向图或无向图。 (1)V、E分别表示G的顶点集、边集， |V|、|E|分别表示G的顶点数、边数。 若|V|=n，则称G为n阶图。,(2) 若|V| 、|E|均为有限数，则称G为有限图。,(3) 在图G中，若E= ，则称G为零图（即只有点没有边的图称为零图）只有一个点的图称为平凡图。,7.1 图的基本概念,【定义3】 设G=为无（有）向图，e=(u,v)(或e=)是图的一条边，则称点u,v为边e的端点，边e关联于点u和v，也称点u或v关联于边e。,

12、无边关联的顶点称为孤立点。 若一条边所关联的两个顶点重合，则称此边为环。,若边 e=(u,v) 且 u=v，则称边e与点u的关联次数为2；,若边 e=(u,v) 且 u v，则称边e与点u的关联次数为1；,若边点u，v不是边e的端点，则称边e与点u的关联次数为0；,与同一条边e关联和两个结点u和v称为是相邻的,若e=为有向边，则称点u邻接到v，v邻接于u,7.1 图的基本概念,【解】 边e2与点v1，v2的关联次数均为1， 边e1与点v2的关联次数为2。 边 e1与V4的关联次数为.,【例4】 指出下图中，各边与点关联的次数。,v5是孤立点， e1是环.,7.1 图的基本概念,【解】下图中，e

13、2=，点v1是边e2的始点，点v2是e2的终点，点v1邻接到v2，点v2邻接于点v，边e1与边e2相邻.,【例5】观察下图：指出边与边的邻接，边与点的邻接，点与点的邻接。,7.1 图的基本概念,【定义】 设G=为一无（有）向图， 点V ,所有与点 关联的边的条数，称为点的度数，简称为度，记作 d(). 设D=为一有向图， V , 以点为起点的边的条数, 称为点的出度,记作d+(); 以点为终点的边的条数, 称为的入度，记作d-(); 称d+()+ d-()为点的度数，记作d(). 称度数为1的顶点为悬挂点,它所对应的边为悬挂边.,二、 图中结点的度数,【注意】 图中每一条边对应的度数为. 约定

14、：每个环在其对应结点上的度数增加,7.1 图的基本概念,【例6】 在下图(1)中，指出各点的度数: d(v1)=4, d(v2)=4, d(v3)=3, d(v4)=1,d(v5)=0。 在图(2)中，指出各点的度、出度和入度. d+(v1)=2， d-(v1)=1， d(v1)=3, d+(v2)=1，d-(v2)=3， d(v2)=4，,(1),7.1 图的基本概念,【定义5】 在图G中,令(G)=maxd(v)|vV， (G) = mind(v)| vV , (G)和 (G)分别称为G的最大度和最小度。,分别简记作,7.1 图的基本概念,在图（）中， 最大度= 4, 最小度=2， 最大出

15、度+ = 3, 最大入度- = 3， 最小出度 + = 1, 最小入度- = 0.,(2),【解】在图(1)中, 最大度=4, 最小度=0,【例7】在图(1)中, 最大度和最小度是多少？ 在图(2)中,最大度、最小度与最大出度、最大入度及最小出度？,7.1 图的基本概念,【解】(1) d(b)6, 6 , 2.,【实训】求下列图中指定结点的度。 (1) d(b), , .,(2) d+(v3)=3, d-(v3)=2, =5, =3, +=3, +=1 , -=2, -=2。,(2) d+(v3),d-(v3), , +, + , -, - .,7.1 图的基本概念,【定理1】（握手定理） 设

16、G=为无向图或有向图， V=v1,v2,vn,|E|= m ( m为边数), 则,【证明】图G中每条边（包括环）均提供2个端点，故在计算各顶点度数的和时，每条边均提供2度，m条边共提供2m度。因此在一个图中，节点度数的总和等于边数的2倍。,= 2m,（即每个顶点度数之和等于边数的2倍）,【推论 】 任何图(无向或有向)中，度为奇数的顶点个数为偶数。,【例如】设图G为下列情况： (1) 16条边，每个顶点都是2度； (2) 21条边，3个4度顶点，其余均为度顶点； 试求每个图有几个节点？,【解答】利用握手定理， 设图有x个顶点，则 （1）x=16*2 , x=16. （2）21*2=12+3*x