文档介绍：2017/11/11
管理运筹学课程组 ftp://
1
第七章图与网络分析
本
章
内
容
2017/11/11
管理运筹学课程组 ftp://
2
例:七桥问题
A
B
C
D
问题:一个散步者能否走过七座桥,且每座桥只走
过一次,最后回到出发点。
问题:能否从某一点开始一笔画出这个图形,最后回到原点,而不重复。
2017/11/11
管理运筹学课程组 ftp://
3
例:中国邮路问题
一个邮递员送信,要走完他所负责的全部街道分送
信件,最后返回邮局。邮递员都会本能地以尽可能少的
行程完成送信任务。
问题:他如何走?
点:路口;
边:两路口之间道路,第i条道路长ei。
问题:求一个圈,过每边至少一次,并使圈的长度最
短。
2017/11/11
管理运筹学课程组 ftp://
4
例:四色猜想
能否用四种颜色给地图染色,使相邻的国家有不同的颜色。
点:国家;
边:两个国家有公共边界。
问题:能否用四种颜色给平面图的点染色,使有公共
边的点有不同的颜色。
2017/11/11
管理运筹学课程组 ftp://
5
有二十个顶点标以二十个城市的名字,要求游戏者找一条从某一城市出发的路线,它经过每一个城市恰好一次,并且最后回到出发点。
点:城市
边:城市之间的道路
问题:游戏者怎么走才能恰好每个城市走一次,而且不重复?如图:
例: Hamilton
2017/11/11
管理运筹学课程组 ftp://
6
第一节图的基本概念
点:研究对象(陆地、路口、国家、球队);
点间连线:对象之间的特定关系(陆地间有桥、路口
之间道路、两国边界、两球队比赛及结果)。
对称关系:桥、道路、边界;
用不带箭头的连线表示,称为边。
非对称关系:甲队胜乙队,用带箭头的连线表示,
称为弧。
图:点及边(或弧)组成。
2017/11/11
管理运筹学课程组 ftp://
7
例:有甲、乙、丙、丁、戊五个球队,各队之间比赛
情况如表:
2017/11/11
管理运筹学课程组 ftp://
8
点:球队;
连线:两个球队之间比赛过,如甲胜乙,用
v1 v2表示。
v1
v2
v3
v4
v5
2017/11/11
管理运筹学课程组 ftp://
9
一、图的定义
定义1:一个图,是由非空集合V(G)={vi} 和V(G)中
元素的有序对(或无序对)的集合E(G)={ek}
所组成的二元组( V(G), E(G) )所构成。记为
G= ( V(G), E(G) )
简记 G=(V,E)
其中 V= {vi} 称为点集,vi为点。
E={ek}称为边集, ek为边(或弧)。
当V,E为有限集时,称G为有限图。否则称为无限图。
2017/11/11
管理运筹学课程组 ftp://
10
无向图:由点及边构成,边[vi,vj]
有向图:由点及弧构成,弧( vi,vj)
图G中点集V的顶点个数,记为p (G) ,边数记为
q(G),简记p,q。