运筹学_图与网络分析

《运筹学_图与网络分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章图与网络分析图的基本概念最小树问题中国邮路问题网络最短路问题网络最大流问题几个图论问题哥尼斯堡七空桥中国邮路问题球队间比赛问题BDAC哥尼斯堡七空桥哥尼斯堡七座桥问题是200年前数学家欧拉所研究的问题之一。哥尼斯堡现名加里宁格勒，城中有小岛，周围有七座桥架立在波列格尔河上。欧拉想：在城中散步时，能否每座桥只走一次，走遍所有的七座桥。ABCD一笔画问题图1中国邮路问题我国数学家管梅谷教授1962年首次提出，并给出了它的解法(奇偶点图上作业法)。邮递员在送报刊信件时，从邮局出发，一般地每次都要走遍所负责的全部街道，

2、任务完成后返回邮局。那么邮递员应该选择哪一条路线才能以尽可能少的路程走完所有的街道呢？有A、B、C、D、E五支球队，他们之间的比赛情况可以用图表示出来。已知A队和其他各队都比赛过一次，B队和A、C队比赛过，D队和E、C队比赛过，E队和A、D队比赛过。v1v2v3v4v5v1v2v3v4v5图2图3如果在比赛中：A胜E，B胜C，A胜D，C胜A，E胜D，A胜B，v1v2v3v4v5注：本章所研究的图与平面几何中的图不同，这里我们只关心图有几个点，点与点之间有无连线，两条线有无公共顶点，点与线是否有关联，至于连线的方式是直线还

3、是曲线，点与点的相对位置如何都是无关紧要的。12434123图4图的基本概念若点与点之间的连线没有方向，称为边，由此构成的图为无向图。记为:G=（V，E）其中V是G的点的集合，E为G的边的集合，连接Vi，Vj的边记为[Vi，Vj]或[Vj，Vi]v1v2v3v4v5v6e2e4e5e6e7e8e1e3e9e10图是由点和点与点之间的连线组成。若点与点之间的连线有方向，称为弧，由此构成的图为有向图。记为:D=（V，A），其中V是G的点的集合，A为G的弧的集合，一条方向为从Vi指向Vj的弧记为(Vi，Vj)v1v3v4v5v

4、6e2e4e5e6e7e8e1e3v2相邻点：两点之间的边属于E相邻边：如果两条边有一个公共端点环：边的两个端点相同多重边(平行边)：两个点之间有多于一条边(弧)多重图:无环但允许有多重边的图简单图：无环且无多重边的图注:在有向图中，如果两点之间有不同方向的两条弧，不是多重边端点的次d(v)：点v作为端点的边的个数；奇点：d(v)=奇数；偶点：d(v)=偶数；悬挂点：d(v)=1；悬挂边：与悬挂点连接的边，孤立点：d(v)=0；空图：E=，无边图。在有向图中，以Vi为始点的边数称为Vi的出次，以Vi为终点的边数称为Vi

5、的入次，入次和出次的和称为该点的次。有向图中所有顶点的入次之和等于所有顶点的的出次之和。图的连通性：链：由两两相邻的点及其相关联的边构成的点边序列。如：v0,e1,v1,e2,v2,e3,v3,…,vn-1,en,vnv0,vn分别为链的起点和终点简单链：链中所含的边均不相同。初等链：链中所含的点均不相同，也称通路。圈：起点和终点相同的链。e8v2v1v4v5v6e6e7e9是一条链，且是开链，也是简单链，但不是初等链，因为v1出现两次。是一个圈。v3e1e2e3通路：由两两相邻的点及其相关联的弧构成的点弧交错序列；如：

6、v0,e1,v1,e2,v2,e3,v3,…,vn-1,en,vnv0,vn分别为链的起点和终点回路：通路的起点和终点相同连通图：图中任意两点之间均至少有一条链相连，否则称作不连通图。任何一个不连通的图都可以分为若干个连同子图，每一个都称为原图的一个分图例如图中，v1和v6之间没有通路，因此它不是连通图，而如果去掉v6，则构成一个连通图。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9连通是一个很重要的概念，如果一个问题所对应的图是一个不连通图，则该问题一定可以分解成互不相关的子问题来加以研究，即可以把不连通

7、图分解成连通的子图来研究。子图设G1=[V1,E1],G2=[V2,E2]子图定义：如果V2V1,E2E1称G2是G1的子图；真子图：如果V2V1,E2E1称G2是G1的真子图；部分图：如果V2=V1,E2E1称G2是G1的部分图；v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10v1v2v3v5v6v2v1v3v4v5v6v7e4e5e6e7e8e9e10部分图子图必须指出，并不是从图G1中任选一些顶点和边在一起就组成G1的子图G1，而只有在G1中的一条边以及连接该边的两个端点均选入G2时

8、，G2才是G1的子图。e1e2e4e5v2v3v1真子图e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9v1e1e2e3e4v2v3v4v5v6e6e7e9部分图若T是图G＝(V，E)的部分图，且T是树，则称T为G的部分树。若T是图G的部分树，则从G中去掉T中所有的边，所得到的子图称为G中的T的余树，也称