第6章 图与网络优化(2012使用版)

第6章 图与网络优化

数学建模(公修)

主要内容6.1 6.2 6.3 6.4 6.5

图与网络的基本知识 树及最小树问题 最短路问题 最大流问题 最小费用最大流问题

2/71

A

C

D

A B

哥尼斯堡七桥

C

D

B

一笔画问题3/71

6.1 图与网络的基本知识 一、图与网络的基本概念E

1、一个图是由点 A 和连线组成。(连线 可带箭头，也可不带， 前者叫弧，后者叫边)B C

D

点代表研究的对象，点与点的连线表示这两个对象 之间有特定的关系。4/71

一个图是由点集 V {v j } 和 V 中元素的无序对的 一个集合 E {ek } 构成的二元组，记为G =(V,E),其 中 V 中的元素 v j 叫做顶点，V 表示图 G 的点集合；E 中的元素 e k 叫做边，E 表示图 G 的边集合。 例V v1 ,v2 , v3 , v4 , v5 , v6 E {e1 ,2 , e3 , e4 , e5 , e6 , e7 , e8 , e9 , e10 } ee1 v1

e2 e5e8 v5 e6

v2

e10v6 e9

e3 e v4 4e7 v3

e1 {v1 , v2 }e 3 {v 2 , v 3 } e5 {v1 , v 3 } e 7 {v 3 , v 5 } e 9 {v 6 , v 6 }

e2 {v1 , v2 }e 4 {v 3 , v 4 } e 6 {v 3 , v 5 } e 8 {v 5 , v 6 } e10 {v1 , v6 }

图1

5/71

2、如果一个图是由点和边所构成的，则称其为无向图， 记作G = (V,E),连接点的边记作[vi , vj],或者[vj , vi]。

3、如果一个图是由点和弧所构成的，那么称它为有向图， 记作D=(V, A),其中V 表示有向图D 的点集合，A 表示有向 图D 的弧集合。一条方向从vi指向vj 的弧，记作(vi , vj)。例 V = {v1 , v2 , v3 , v4 , v5 , v6 }, A = {(v1 , v3 ) , (v2 , v1) , (v2 , v3 ) , (v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) }v1v3 v5 v2 v4 v6

图26/71

4、一条边的两个端点是相同的,那么称为这条边 是环。 5、如果两个端点之间有两条以上的边，那么称 为它们为多重边。 6、一个无环，无多重边的图称为简单图，一个 无环，有多重边的图称为多重图。

7、每一对顶点间都有边相连的无向简单图称为 完全图。有向完全图则是指任意两个顶点之间有且仅 有一条有向边的简单图。7/71

8、以点v为端点的边的个数称为点v 的次(度),记 作 d (v ) 。图1中 d(v1)= ?,d(v6)= ?, d(v4)= ?e1 e2 e5 e8 v5 e6 e7 v3 v2 e3 e v4 4

次为零的点称为弧立 v1 点，次为1的点称为悬挂点。 悬挂点的关联边称为悬挂 e10 边。次为奇数的点称为奇 v6 点，次为偶数的点称为偶 e9 点。

8/71

定理1

所有顶点次数之和等于所有边数的2倍。

定理2

在任一图中，奇点的个数必为偶数。

9/71

9、设 G1=( V1 , E1 ),G2 =( V2 ,E2 ),如果V2 V1 , E2 E1 称 G2 是G1 的子图；如果 V2 = V1 , E2 E1 称 G2 是 G1 的部分图或支撑子图。v2 e1 v1 e6 v6 e8

e2e9 e10 v7 e 11 e5 (a) v5

v3 e3 v4 v1

v2 e1 e6 e7

v2

e8 v1v7

v3e9 e10 v7 e 11 v5 (c)支撑子图10/71

e

1 e6 e7

e7

v4

e4

v6 e5子图

v5(b)

v6

10、由两两相邻的点及其相关联的边构成的点 边交错序列称为链。 若链中所含的边均不相同，则称此链为简单链； 所含的点均不相同的链称为初等链。圈、简单圈、初等圈

11、图中任意两点之间均至少有一条链，则称 此图为连通图，否则称为不连通图。有向图 基础图(有向图对应的无向图); 弧的起点终点； 路、初等路、回路、初等回路。11/71

v2

e4 e5

v4 e9 e8 e10 v5 v6

(v1 , v2 , v4 , v6 ) (v1 , v3 , v4 , v2 , v3 , v5 , v6 )

e1

v1e2

e3v3

e7

e6

(v1 , v3 , v5 , v6 ) (v1 , v3 , v2 , v5 , v6 )v1

v2

v4 v6

v3

v5

12/71

在实际应用中，给定一个图G=(V,E)或有向 图D=(V,A),在V中指定两个点，一个称为始点 (或发点),记作vs ,一个称为终点(或收点),记 作vt ,其余的点称为中间点。对每一条弧 (v i , v j ) A, 对应一个数 wi ,称为弧上的“权”。通常把这种赋权 j 的图称为网络。

13/71

二、图的矩阵表示 对于网络(赋权图)G=(V,E),其中边 (v i , v j ) 有权 wi j ,构造矩阵 A (ai j )n n ,其中： wi j ai j 0 (v i , v j ) E (v i , v j ) E

称矩阵A为网络G的权矩阵。设图G=(V,E)中顶点的个数为n,构造一个 矩阵A (ai j )n n

,其中：

1 ai j 0

(v i , v j ) E (v i , v j ) E

称矩阵A为网络G的邻接矩阵。14/71

例v6

v1

4

v27 3 2 v3 5

3

6

3

4 2 v5 v4

邻接矩阵什么 特点？ 有向图如何定 义邻接矩阵？

权矩阵为：v1 0 v 2 4 v 3 0 A v4 6 v5 4 v6 3 v1 4 0 6 4 3 0 2 7 0 0 2 0 5 0 3 7 5 0 2 0 0 0 2 0 3 0 3 0 3 0 v 2 v 3 v4 v5 v6

邻接矩阵为：v1 0 v 2 1 v 3 0 B v 4 1 v 5 1 v 6 1 v1 End 1 0 1 1 1 0 1 1 0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 0 v 2 v 3 v4 v5 v615/71

6.2 树及最小树问题已知有六个城市，它们之间 要架设电话线， 要求任意两个城市均可以互相通话，并且电话线 的总长次最短。v1v2

一、树 v6 1、定义 一个无圈的连通图称为树。

v3 v4

v5

16/71

2、树的性质 (1)必连通，但无圈。 (2)n 个顶点的树必有n-1 条边。 图 (3)树的充要条件是任意两个顶点恰有一条链 (初等链)。 (4)树连通，但去掉任一条边，必变为不连通。 (5)树无圈，但不相邻的两个点之间加一条边， 恰得到一个圈。 (6)顶点不少于两个的树至少有两个悬挂点。v1v6 v2

v3 v4

v5

17/71

二、生成树 设图 K (V , E1 ) 是图G=(V , E )的一支撑子图， 如果图 K (V , E1 ) 是一个树,那么称K 是G 的一个 生成树(支撑树),或简称为图G 的树。v1 v5

v1 v2 v5

v2

v4

v3

v4

v3

一个图G 有生成树的充要条件是G 是连通图。

18/71

用破圈法求出下图的一个生成树。v2 e1 v1 e2 v2 e1 v1 e2 v3 e3 e5 e6 e4 e7 v4 v3 v2 e4 e3

e4

e7v4 e 8 v5

e5 e6

e8v5

v1 e2 v3

v4 e6

e8

v5

19/71