主讲人:孙云龙数学建模课件
图论模型
数 学 建 模
主讲人:孙云龙数学建模课件
引例 七桥问题
哥尼斯堡七桥问题
D
A
B
C
问题:
从某点出发通过每座桥且每桥只通过一次回到起点.
主讲人:孙云龙数学建模课件
模型构造
点: 陆地 岛屿
边: 桥
A
B
C
D
图论方法已经成为数学模型中的重要方法。许多难题由于
归结为图论问题被巧妙地解决。
图论中有许多著名算法。
D
A
B
C
主讲人:孙云龙数学建模课件
一、图的一般理论
一个图G由一个顶点集V和一个边的集E组成。
E中每个元素e是连接顶点集 V中两个顶点u和v的边。
例:
图G=<V,E>:
点集 V = {v
1
,v
2
, ...,v
n
}
边集 E = {e
1
,e
2
, ...,e
m
} 其中 e
k
=v
i
v
j
图G=<V,E>:
其中 V = {v
1
,v
2
,v
3
,v
4,
v
5
}
E = {e
1
,e
2
,e
3
,e
4
}
e
1
=v
1
v
2
,e
2
=v
2
v
4
,e
3
=v
1
v
4
,e
4
=v
5
v
2
e
1
v
1
v
2
v
3
v
4
v
5
e
2
e
3
e
4
1、定义
主讲人:孙云龙数学建模课件
图的图形表示
例
联接
点的位置, 边的长度
×
v
1
v
2
v
3
v
4
v
5
e
1
e
2
e
3
e
4
比较: 同构
G1
G2
G3
1 2
3
4
3
4
2
1
3 4
1
2
v
1
v
2
v
3
v
4
v
5
e
2
e
3
e
4
评论1