图论模型 数学建模 图论分析 矩阵课件.ppt

《图论模型 数学建模 图论分析 矩阵课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论模型§1哥尼斯堡七桥问题ADCB哥尼斯堡是18世纪东普鲁士的一个城市，流经市区有条河名叫普雷格尔河，河中有两岛，把市区分成四快陆地A、B、C、D，陆地间有七座桥相通。问：一个散步者能否从某地出发，走遍七座桥，且每座桥只走一次，最后回到出发地？一个人能否经过每座桥恰一次而走遍七座桥？ABCD抽象：陆地点；桥线欧拉判别准则：要能从图的某个顶点出发，经图的每条线正好一次，最后回到原来顶点，当且仅当这个图连成一片，且每个顶点都有偶数条线和它连接。七桥问题无解。§2图论的基本概念一、图的概念一个图G指的是仅由一些点和一些点

2、的连线组成的图形。顶点（结点）：边：e7V5V4V3V2V1e6e5e4e3e2e1(a)V5V4V3V2V1a6a5a3a4a2a1(b)图中的小圆点顶点之间的连线无向图：图中的边没有方向的图有向图：图中的边有方向的图1.图的定义：图的集合表示：设V表示所有顶点组成的集合，E表示所有边组成的集合，G表示图，那么G=。e7V5V4V3V2V1e6e5e4e3e2e1(a)V5V4V3V2V1a6a5a3a4a2a1(b)对于无向图G，连接顶点Vi,Vj的边记为（Vi,Vj)如：在图(a)中，边e2=(V2,

3、V3)V={v1,v2,v3,v4,v5},E={e1,e2,e3,e4,e5,e6,e7}对于有向图G，一条连接从Vi指向Vj的边记为,如在图(b)中，边a4=V={v1,v2,v3,v4,v5},E={a1,a2,a3,a4,a5,a6}2.关联设G=为无向图，e=(u,v)E,则称u,v是e的端点，也称u,v是相邻的，称e是点u（及点v）的关联边。3.环若图G中某边e的两个端点相同,则称e为环4.多重边在图G中，若两个顶点之间有多于一条边，称这些边为多重边5.简单图7.度

4、（次）无环，无多重边的图6.多重图无环，但允许有多重边的图设G=为一无向图，vV,则称以v为端点的边的个数为v的度（次）数，简称度（次），记为d(v)推论定理1设图G=为无向图或有向图，则G中所有点的度数之和是边数之和的2倍。任何图中，度数为奇数的顶点个数为偶数。二、子图、完全图、补图1.子图设G=,G’=是两个图，若V’V,E’E,则称G’是G的子图，G是G’的母图,记为G’G。若G’G,且G’G,（即V’V或E’E），则称G’是G的真子图。若G’G,且

5、V’=V,则称G’是G的生成子图。2.导出图设G=,若V’V,且V’，E’={(u,v)

6、u,vV’,(u,v)E}，则称G’=是G的由V’导出的导出子图。设G=,若E’E,且E’，V’={vV

7、v是E’中某边的端点}，则称G’=是G的由E’导出的导出子图。(1)v1v4v3v2e1e2e3e4e5(2)v1v2e4e5(3)v1v4v3v2e1e3e43.完全图设G=是n阶无向简单图（

8、V

9、=n，顶点数为n），若G中任何顶点都与其余的n-1

10、个顶点相邻，则称G为n阶无向完全图，记为Kn(2)和(3)是(1)的子图(3)是(1)的生成子图(2)是v1,v2导出子图(3)是e1,e3,e4导出子图设D=是n阶有向简单图，若对任意的顶点u,vV，既有有向边，又有有向边，则称D为n阶有向完全图。4.补图设G=是n阶无向简单图，以V为顶点集，以所有能使G成为完全图Kn的添加边组成的集合为边集的图，称为G相对于完全图Kn的补图，简称G的补图。(1)(2)(3)(4)(1)与(2)互补(3)与(4)互补三、通路、回路、图的连通

11、性1.通路、回路：给定一个图G=，设G中顶点和边的交错序列T={v0,e1,v1,e2,v2,…,ek,vk}，如果满足ei=(vi－1,vi),(i=1,2,…,k),则称T为G的一条联结v0和vk的通路，记为T={v0,v1,v2,…,vk}；v0和vk称为此通路的起点和终点；T中边数k称为T的长度；若v0=vk,此时称通路为回路。定理2：在一个n阶图中，若从顶点vi到vj存在通路，则从vi到vj存在长度小于等于n－1的通路。定理3：在一个n阶图中，若存在顶点vi到自身的回路，则从vi到自身存在长度小于

12、等于n的回路。2.连通：在一个无向图G中，若从顶点vi到vj存在通路（当然从vj到vi也存在通路），则称vi与vj是连通的。规定vi到自身总是连通。3.连通图：若无向图G是平凡图，或G中任意两点都连通，则称G是连通的，否则，称G是不连通的。四、两个特殊的图1.二部图（二分图）若能将无向图G=的顶点集V划分成两个子集V1和V2（V1V