第十章图论模型.pptVIP

第十章图论模型第1页，共35页，星期日，2025年，2月5日§1哥尼斯堡七桥问题ADCB哥尼斯堡是18世纪东普鲁士的一个城市，流经市区有条河名叫普雷格尔河，河中有两岛，把市区分成四快陆地A、B、C、D，陆地间有七座桥相通。问：一个散步者能否从某地出发，走遍七座桥，且每座桥只走一次，最后回到出发地？一个人能否经过每座桥恰一次而走遍七座桥？ABCD抽象：陆地点；桥线欧拉判别准则：要能从图的某个顶点出发，经图的每条线正好一次，最后回到原来顶点，当且仅当这个图连成一片，且每个顶点都有偶数条线和它连接。七桥问题无解。第2页，共35页，星期日，2025年，2月5日§2图论的基本概念一、图的概念一个图G指的是仅由一些点和一些点的连线组成的图形。顶点（结点）：边：e7V5V4V3V2V1e6e5e4e3e2e1(a)V5V4V3V2V1a6a5a3a4a2a1(b)图中的小圆点顶点之间的连线无向图：图中的边没有方向的图有向图：图中的边有方向的图1.图的定义：图的集合表示：设V表示所有顶点组成的集合，E表示所有边组成的集合，G表示图，那么G=V,E。第3页，共35页，星期日，2025年，2月5日e7V5V4V3V2V1e6e5e4e3e2e1(a)V5V4V3V2V1a6a5a3a4a2a1(b)对于无向图G，连接顶点Vi,Vj的边记为（Vi,Vj)如：在图(a)中，边e2=(V2,V3)V={v1,v2,v3,v4,v5},E={e1,e2,e3,e4,e5,e6,e7}对于有向图G，一条连接从Vi指向Vj的边记为Vi,Vj,如在图(b)中，边a4=v5,v2V={v1,v2,v3,v4,v5},E={a1,a2,a3,a4,a5,a6}2.关联设G=V,E为无向图，e=(u,v)?E,则称u,v是e的端点，也称u,v是相邻的，称e是点u（及点v）的关联边。3.环若图G中某边e的两个端点相同,则称e为环4.多重边在图G中，若两个顶点之间有多于一条边，称这些边为多重边第4页，共35页，星期日，2025年，2月5日5.简单图7.度（次）无环，无多重边的图6.多重图无环，但允许有多重边的图设G=V,E为一无向图，v?V,则称以v为端点的边的个数为v的度（次）数，简称度（次），记为d(v)推论定理1设图G=V,E为无向图或有向图，则G中所有点的度数之和是边数之和的2倍。任何图中，度数为奇数的顶点个数为偶数。二、子图、完全图、补图1.子图设G=V,E,G’=V’,E’是两个图，若V’?V,E’?E,则称G’是G的子图，G是G’的母图,记为G’?G。若G’?G,且G’?G,（即V’?V或E’?E），则称G’是G的真子图。若G’?G,且V’=V,则称G’是G的生成子图。第5页，共35页，星期日，2025年，2月5日2.导出图设G=V,E,若V’?V,且V’??，E’={(u,v)|u,v?V’,(u,v)?E}，则称G’=V’,E’是G的由V’导出的导出子图。设G=V,E,若E’?E,且E’??，V’={v?V|v是E’中某边的端点}，则称G’=V’,E’是G的由E’导出的导出子图。(1)v1v4v3v2e1e2e3e4e5(2)v1v2e4e5(3)v1v4v3v2e1e3e43.完全图设G=V,E是n阶无向简单图（|V|=n，顶点数为n），若G中任何顶点都与其余的n-1个顶点相邻，则称G为n阶无向完全图，记为Kn(2)和(3)是(1)的子图(3)是(1)的生成子图(2)是v1,v2导出子图(3)是e1,e3,e4导出子图第6页，共35页，星期日，2025年，2月5日设D=V,E是n阶有向简单图，若对任意的顶点u,v?V，既有有向边u,v，又有有向边v,u，则称D为n阶有向完全图。4.补图设G=V,E是n阶无向简单图，以V为顶点集，以所有能使G成为完全图Kn的添加边组成的集合为边集的图，称为G相对于完全图Kn的补图，简称G的补图。(1)(2)(3)(4)(1)与(2)互补(3)与(4)互补第7页，共35页，星期日，2025年，2月5日三、通路、回路、图的连通性1.通路、回路：给定一