第5章 图论与网络分析

图的基本概念 最小支撑树问题 网络分析 最短路径问题 网络最大流问题

图论起源： 图论起源：哥尼斯堡七桥问题

A C B D C

A D B

问题：一个散步者能否从任一块陆地出发， 问题：一个散步者能否从任一块陆地出发，走过七 座桥，且每座桥只走过一次，最后回到出发点？ 座桥，且每座桥只走过一次，最后回到出发点？ 结论： 结论：每个结点关联的边数均为偶数

§1 图的基本概念

1. 图 由点和边组成，记作 由点和边组成，记作G=(V，E)，其中 ， ， V=(v1，v2，……，vn)为结点的集合， 为结点的集合， ， 为结点的集合 E=(e1，e2，……，em) 为边的集合。 为边的集合。 ， 点表示研究对象 边表示研究对象之间的特定关系

p114

2、图的分类 、

无向图，记作 无向图，记作G=(V，E) ， 图 有向图，记作 有向图，记作D=(V，A) ， 例1：哥尼斯堡桥问题的图为一个无向图。 ：哥尼斯堡桥问题的图为一个无向图。 例2：五个球队的比赛情况，v1 ：五个球队的比赛情况， v2 表示v1胜v2。 表示 有向图的边 称为弧 称为弧。

v5 v1 v4

v2

v3

e1

例

v1 e10 v6 e9 e8

e2 e5 e6 v5

v2 e3 e v4 4 e7 v3

图1

V = {v1 ,v 2 , v 3 , v 4 , v 5 , v 6 } E = {e1 ，2 , e3 , e4 , e5 , e6 , e7 , e8 , e9 , e10 } e

e1 = [v1 , v 2 ]

e 3 = [v 2 , v 3 ] e5 = [v1 , v 3 ]

e2 = [v1 , v2 ]

e4 = [ v 3 , v 4 ] e6 = [ v 3 , v 5 ] e8 = [ v 5 , v 6 ]

e7 = [ v 3 , v 5 ] e9 = [ v 6 , v 6 ]

e10 = [v1 , v6 ]

V = {v1 , v2 , v3 , v4 , v5 , v6 }， A = {(v1 , v3 ) , (v2 , v1) , (v2 , v3 ) , (v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) }

v1

v2

v4 v6

v3

v5

图2

3、链与路、圈与回路 、链与路、 无向图： 无向图： 链 点边交错的序列

圈 起点=终点的链 起点 终点的链

有向图： 有向图： 路 点弧交错的序列 回路 起点 终点的路 起点=终点的路

v5 v1 v4 v1 v5 v4

v2

v3

v2

v3

链与路中的点均不相同，则称为初等链 路 链与路中的点均不相同，则称为初等链 (路) 类似可定义初等圈 回路） 初等圈（ 类似可定义初等圈（回路）

4、连通图 、

任何两点之间至少存在一条链的图称为连通图， 任何两点之间至少存在一条链的图称为连通图， 否则称为不连通图。 否则称为不连通图。 例： G1为不连通图， G2为连通图 为不连通图，

G1

G2

5、支撑子图 、

图G=(V，E)和G'=(V ' ，E ')，若V =V ' 且E ' E ， ， 和 ， 则称G' 则称 为G的支撑子图。 的支撑子图。 例 ： G2为G1的支撑子图 v5 v1 v1 v5

v4

v4

v2 G1

v3

v2 G2

v3

例：

G2 是G1 的子图； 的子图；

e2 v2 e1 v1 e6 v6 (c) e7 e9 e10 v7 e 11 v5 v4

v2 e1 v1 e6 v6 e7 e8

v3 e9 e10 e3 v4 e4

v3

v7 e 11 e5 (a) v5

6、赋权图（网络） 、赋权图（网络）

图的每条边都有一个表示一