文档介绍：第五章图与网络分析
教学大纲:
理解图与网络的基本概念,掌握最小树、最短路、法、floyd法、最大流的标号法和最小截集最大流定理.
例:七桥问题
A
B
C
D
问题:一个散步者能否走过七座桥,且每座桥只走
过一次,最后回到出发点。
问题:能否从某一点开始一笔画出这个图形,最后回
到原点,而不重复。
例:中国邮路问题
一个邮递员送信,要走完他所负责的全部街道分送
信件,最后返回邮局。邮递员都会本能地以尽可能少的
行程完成送信任务。
问题:他如何走?
点:路口;
边:两路口之间道路,第i条道路长ei。
问题:求一个圈,过每边至少一次,并使圈的长度最短。
例:四色猜想
能否用四种颜色给地图染色,使相邻的国家有不同的颜色。
点:国家;
边:两个国家有公共边界。
问题:能否用四种颜色给平面图的点染色,使有公
共边的点有不同的颜色。
例:有甲、乙、丙、丁、戊五个球队,各队之间比赛
情况如表:
点:球队;
连线:两个球队之间比赛过,如甲胜乙,用
v1 v2表示。
v1
v2
v3
v4
v5
第一节图的基本概念
点:研究对象(陆地、路口、国家、球队);
点间连线:对象之间的特定关系(陆地间有桥、路口
之间道路、两国边界、两球队比赛及结果)。
对称关系:桥、道路、边界;
用不带箭头的连线表示,称为边。
非对称关系:甲队胜乙队,用带箭头的连线表示,
称为弧。
图:点及边(或弧)组成。
一、图的定义
定义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为有限图。否则称为
无限图。
无向图:由点及边构成,边[vi,vj]
有向图:由点及弧构成,弧( vi,vj)
图G中点集V的顶点个数,记为P (G) ,边数记为q(G),
简记P,q。
二、图论中常用术语
1、相邻与关联
若边e=[u,v]∈E,称u,v是e的端点,也称u,v是相邻的。称e是点u(及点v)的关联边。
若两条边有一个公共的端点,则称这两条边相邻。
vi
vj
e
vi,vj相邻
e 与vi,vj关联
vi
e1
e1 与e2相邻
vj
vk
e2
点点,相邻
边边,相邻
点边
2、简单图与多重图
某条边两个端点相同,称这条边为环。
若两点之间有多于一条的边,称这些边为多重边。
无环、无多重边的图称为简单图。
多重图:无环、但允许有多重边。
v1
e1
e2
e3
v2
v3
e5
e4
v4