10-图模型与算法.ppt

文档介绍：Mathematical Experiments
数学实验之十
——图的模型及算法初步
[1]学会如何建立图的模型;
[2]了解图的存储结构;
[3]掌握图的表示与矩阵表示之间的转化;
[4]初步认识算法及其复杂性, 树立算法有效性的观点。
实验目的
布置实验
实验十主要内容
图的模型
算法初步
图的矩阵表示方法
结束
实验十主要内容
一个时间安排问题
图论的起源——七桥问题
人、狼、羊、菜渡河问题
图论的起源:七桥问题
a
c
b
d
a
c
b
d
图论的起源:七桥问题
graph
一般用大写字母G,H表示无向图。
一种表示工具——图
顶点
边
d
c
a
b
三要素:顶点集V;边集E;关联函数
G=(V,E,)
如(e1)={a,b},
e2
e3
e1
e4
e5
 e与顶点u, v相关联
 u与v相邻
两边相邻
重边
c
a
b
d
一种表示工具——图
有向图:
V1
V2
V3
V5
V4

想
你能给出一个可用有向图描述的实际例子吗?
一种表示工具——图
加权图
这些数字可以代表距离,费用,可靠性或其他的相关参数。
1
2
3
4
5
8
6
9
1
5
7
10
3
一种表示工具——图
返回