第6章-图论1解析课件

图论

哥尼斯堡七桥问题哥尼斯堡（现名加里宁格勒）是欧洲一个城市，Pregei河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次最后回到原地呢？ABCDACBD6.1图的基本概念

图论是专门研究图的理论的一门数学分支，主要研究点和线之间的几何关系。定义：（图）设G=（V，E）其中：V=（v1，v2，…...vm）

是m个顶点集合；

E=（e1，e2，…...en）

是n条边集合。

如果给图中的点和边赋以具体含义和权数，把这样的图称为网络图v2v5v3v4e1e3e5e6e4e7e2v1e8e1=[v1,v1]e3=[v1,v3]若e=[vi，vj]，vi，vj是e的端点e为vi或vj的关联边若vi、vj与同一条边关联，则称vi和vj相邻若ei和ej有相同的端点，则称边ei和ej相邻若边e的两个端点相重，称该边为环如果两个点之间的边多余一条，称为具有多重边对无环、无多重边的图称作简单图与某一个点vi相关联的边的数目称为点vi的次（度或限度）次为奇数的点称作奇点次为偶数的点称作偶点次为0的点称作孤立点链、路

点和边的交替序列

若其中各边e1,e2,…,ek互不相同,且任意vi,t-1和vit(2≤t≤k)均相邻，称为链

如果链中的所有顶点v0,v1,…,vk也不相同称作路

对起点与终点相重合的链称作圈对起点与终点相重合的路称作回路在一个图中，如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称该图是不连通的完全图一个简单图中若任意两点之间均有边相连，称这样的图为完全图含有n个顶点的完全图，其边数为偶图

如果图的顶点能分成两个互不相交的非空集合v1和v2，使在同一集合中任意两个顶点均不相邻，称这样的图为偶图。V1和v2之间的每一对不同顶点都有一条边相连，称为完全偶图V1含m个顶点，v2含n个顶点，其边数为m*n条子图设G=（V，E）和G1=（V1，E1）。如果V1V，E1E则称G1为G的子图；

v1v5v4v2v3e1e8e7e6e5e4e3e2v1v5v4v2e1e5e3（a）的子图部分图设G=（V，E）和G1=（V1，E1）。如果V1=V，E1E则称G1为G的部分图；

v1v5v4v2v3e1e8e7e6e5e4e3e2v1v5v4v2e1e5e3（a）的部分图v3例1：有甲、乙、丙、丁、戊、已六名运动员报名参加A、B、C、D、E、F六个项目的比赛。各个运动员报名参加的比赛项目如下表，问六个项目的比赛顺序应如何安排，能做到每名运动员都不连续地参加两项比赛。ABCDEF甲√√√乙√√√丙√√丁√√戊√√√已√√√ABCDEFA、C、B、F、E、D例二：某单位储存八种化学药品，其中某些药品不能存放在某一库房内，V1、…、V8分别代表这八种药品，若药品Vi与Vj不能存放在一个库房内，则在Vi与Vj之间连一条边，问至少需要几个库房存储这八种药品。V1V8V7V6V5V4V3V26.2树图和图的最小部分树树图T（V，E）无圈的连通图。性质1：任何树中必存在次为1的点性质2：具有n个顶点的树的边数恰好为（n-1）条性质3：任何具有n个点、（n-1）条边的连通图是树图以下说法哪些是正确的：1在树中任意两点之间必有一条而且只有一条通路。2在树中划去一条边，则树不连通。3在树中不相邻的两个顶点之间加一条边，可得一个且仅得一个圈。4树中边数有ne=p-1（p为顶点数）6.2.1图的最小部分树图的最小部分树

如果G1是G2的部分图，又是树图，则称G1是G2的部分树。

一般G2含有多个部分树，其中树枝总长最小的部分树称为最小部分树定理1：图中任一个点i，若j是与i相邻点中距离最近的，则边[i，j]一定必含在该图的最小部分树内。推论：把图的所有点分成v和两个集合，则两集合之间连线的最短边一定包含在最小部分树内。6.2.3避圈法和破圈法避圈法：

1、从图中任选一点vi，让vi∈v，图中其余点均包含在；

2、从v与的连线中找出最小边，这条边一定包含在最小部分树内，将这条边设为[vi，vj]并加粗，作为标记

3、令V∪ViV，

\vi

4、重复2、3步，一直到图中所有点均包含在v中为止ABCDETS225417435157避圈法例2：ABCDETS225417435157vABCDETS225417435157vABCDETS225417435157vABCDETS225417435157vABCDETS225417435157vABCDETS225417435157vv1v7v4v3v2v5v620159162532817412336例3：用避圈法求如下图的最小部分树：v1v7v4v3v2v5v620159162532817412336破圈法

从网络图N中任取一回路，去掉这个回路中权数最大的一条边，得一子网络图N1，在N1再取一回路，再去掉这个回路中权数最大的一条边，得一子网络图N2；一直继续下去不含回路止。ABCDETS225417435157破圈法例3’：用避圈法求改图的最小部分树ABCDETS22417435157破圈法ABCDETS2217435157破圈法ABCDETS221435157破圈法ABCDETS22135157破圈法