当前位置:文档之家› 第五章 图论简介(运筹学,中央财经大学)

第五章 图论简介(运筹学,中央财经大学)


类似的问题:一笔画问题
图的一笔画: 可一笔画 不可一笔画
字的一笔画:如“中、日、口、串”等可一笔画 而:“田、目”等不能一笔画
图论的应用范围:
1、中国邮路问题: 邮递员如何选择适当的投递路线,使每条街道至 少走过一次且所走的总路程最短?
2、最短路问题:
一个乡有9个自然村,其间道路如下图所示, 要以村为中心v 0建有线广播网,如要求沿道路 架设广播线,应如何架设使所用电线最短
简单回路 C3: {v1 , e7 , v5 , e4 , v 4 , e8 , v1 }
v6
e6 e5
v1 e1
e8 e10

v2
e2

e7
e9
v5
e4
G
4 v
v3 e
3
e6
v1 e1
e8 e10

v2

e7
v1
e8
v 6
e7 e5
v5
e4
把C3从C 2的v1点处插入 C 2,得一简单回路 C,
创始人
创立时间 问题的提 出
E.Euler(瑞士数学家) 18世纪
歌尼斯堡七桥难题
※歌尼斯堡七桥难题
普莱格尔河
七桥问题的数学模型:
用A、B表示两座小岛,C、D表示两岸, 连线AB表示A、B之间有一座桥。 C

A
B D
问题简化为: 在该图中,从任一点出发,能否通过每条线段 一次且仅仅一次后又回到原来的出发点 结论:不存在这样一种走法。
1

4 5
4 2
1

v0
1 3

4 4
5
2
3


5
1
1

2
1 2

v0
1



2
1
2
3

3、选址问题 已知一个地区的交通网络如下图所示,其中点代表 居民小区,边表示公路,问区中心医院应建在哪个 小区,可使离医院最远的小区居民就诊时所走的路 程最近? v5 即求图的中心
v3
有向图 ——边e=(vi, vj)有方向 vi为始点,vj为终点 图 此时(vi, vj)≠ (vj,vi) 无向图 ——边e=(vi, vj)无方向
此时(vi, vj)= (vj, vi)
e1
e2
有 向 图
e1
e2
v1
e3
e6
v1
e3
无 向 图
e6
v2

e4
e5
v 4
对vi V
vi 每出现一次,必关联两 条边 若vi 是C的中间点, 如C: {v1 , e1 , v2 , e2 , v3 , vi 1 , ei 1 , vi , ei , vi 1 ,, v1 } ,即 vi 为偶点 d (vi )为偶数
vi必关联两条边 若vi 是C的起点, vi 也是 C的终点,
{v5 , e4 , v4 , e9 , v2 , e2 , v3 , e3 , v4 , e8 , v1},
链 开链 : 链中的起点与终点不同
闭链 : 链中的起点与终点重合
圈或回路 道路
简单圈 在圈中,所含的边均不相同 初等圈 在圈 中,除起点和终点重合 外,
没有相同的顶点和相同 的边
e4
4 v
v 3
如w(e2)=50: 城市v2 到城市v3 的距离是50公里
5.2 欧拉图与中国回路问题
欧拉道路: 一笔画问题 设G是一个无向连通图,若 存在一条道路,经过 G中的 每一条边一次且仅一次 ,则称这条道路为欧拉 道路
开 链
v1 e1
v5
e6
e5
4 v
v2
e2
v1
记G G C2 (V ,E ),E E E1,V 是E 中边的端点
在G 中,以 G 与C 2的公共顶点 v1为起点取一个简单回路 C3
简单回路 C3: {v1 , e7 , v5 , e4 , v 4 , e8 , v1 }
v6
e6 e5
v1 e1
v 3
d (v ) 12 ,G的边数m=6 即 d (v ) 2m
i
i
三、次的性质
定理1 在图G=(V,E)中,所有点的次之和是边数m 的两倍。
证明: 由于每条边均与两个顶点关联, 因此在计算顶点的次时每条边都计算了两遍 所以顶点次数的总和等于边 数的二倍。
定理5.2 在任何图G=(V,E)中,奇点的个数为偶数
d (vi )为偶数 ,即 vi 为偶点
充分性: 若无向连通图G=(V,E)中无奇点,则G为欧拉图
d (vi )为偶数 例: G连通,
v1 e1
e7 e5 e8
v6
e6

v2
e2

v5
e10
e9
e4
4 v
v3 e
3
G
任取一点,如 v3, 找一个以 v3为起点的一个简单回路 C1
e7 e8

v2
e2
e6 e5
v1 e1
e8 e10

v2

e7
v1
e8

v5
e10
e9
G
e4
4 v
e3
v 3 v 6
e7
v5
e4
G
4 v
v5
G
e4
4 v
简单回路 C1: {v3 , e3 , v4 , e9 , v 2 , e2 , v3 } 简单回路 C 2: {v2 , e10 , v5 , e5 , v6 , e6 , v1 , e1 , v2 }
{v3 , e3 , v4 , e2 , v2 , e1 , v1 , e4 , v4 }
欧拉回路:
v1
欧拉图

设G是一个无向连通图,若 存在一个回路,经过 G中的 每一条边一次且仅一次 ,则称这个回路为欧拉 回路

e6 e5
e1

v2
e2
存在欧拉回路:
{v1 , e1 , v2 , e2 , v3 , e3 , v4 , e7 , v2 , e5 , v5 , e4 , v4 , e6 , v1}
e7
v5
e4
4 v
v2
e3
v 3
该图特点:d (vi )均为偶数
v1

e1
e5

e2
e4
该图不存在欧拉回路
存在奇点
v 3
e3
4 v
定理5.3 无向连通图G为欧拉图的 充要条件是G中无奇点
证明:必要性 已知G=(V,E)为欧拉图,即存在一条欧拉回路C, C经过G的每一条边, 由于G为连通图, 所以G中的每个点至少在C中出现一次
2、相邻点和相邻边:
一条边的两个端点称为 相邻点,简称邻点, 端点落在同一个顶点的 边称为相邻边,简称邻 边 e1 1 3、多重边与环: 具有相同端点的边称为 多重边或平行边; e2 两个端点落在同一个顶 点的边称为环。
v 1
e3
e6
4、多重图和简单图:
v2

含有多重边的图称为多 重图; 无环也无多重边的图称 为简单图。
证明: 设V1和V2 分别是图 G中奇点和偶点的集合
则V1 V2 V且V1 V2
d (v ) d (v ) d (v ) 2m (定理5.1)
iV i iV1 i iV2 i
V2 是偶点的集合 , d (vi )(i V2 )均为偶数
所以 d (vi )为偶数
G
4 v
v5
G
e4
4 v
C: {v 2 , e10 , v5 , e5 , v6 , e6 , v1, e7 , v5 , e4 , v4 , e8 , v1 , e1 , v 2 }
六、赋权图(网络)
对图G=(V,E),
e的权
若对每一条边e,都有一个实数w(e)与之对应, 则称图G=(V,E)为赋权图 ,或网络 权w(e)通常表示距离、费用、容量等 如公路交通图:
e6 e5
v1

e1
e8
v6

v2
e2
Vi表示 城市, ei表示公路 w(ei)表示公路ei的长度
e3

e7
e9
v5
iV2
d (v )为偶数
i V1 i
而V1是奇点的集合, d (vi )(i V1 )均为奇数
只有偶数个奇数相加才能得到偶数
所以 V1中的点,即奇点的个数 为偶数
四、链: 对无向图 G (V,E)
(V,E)中,一个点与边的交 错序列 1、链的定义: 在图 G {vi 0 , ei1 , vi1 , ei 2 , vik 2 , eik 1 , vik 1 , eik , vik }, 且eit (vit 1 , vit )(t 1,2, k ), 则称这个点边序列为 连接 vi 0与vik的一条链 , 简记为 {vi 0 , vi1 ,,vik 2 , vik 1 , vik }
简单链:在链中,所含的边均不相同 初等链:在链 中,所含的顶点、边均 不相同
v6
e6 e5
v1

e1
e8

v2
e2

e7
e9
v5
e4
4 v
e3
v 3
{v6 , e5 , v5 , e7 , v1 }
初等 链
不是链
{v6 , e7 , v1 , e8 , v4 }
简单链
相关主题