金融投资.ppt

第一章最短路问题
图的概念
:哥尼斯堡七桥问题
早期图论与“数学游戏”,河中有两个小岛,:
1736年,(1707-1783)
上面的例子还可以这样来看:令
V={小岛A,小岛B,C岸,D岸}
E={连接V中两元素间的桥}
从而以V中的元素为顶点,以E中的元素为线,.
注:图的自然语言定义
定义: ,集合E中的元素称为图的边.
:
(1)定义1:有序二元组G=(V,E)称为一个图,其中:例,坐标。V研究对象,E研究对象的关系
①V={v1,v2, …,vn}是有限非空集合,称为顶点集,其中的元素叫做图G的顶点;
②E是V中元素组成的二元偶对的多重集合,称为边集,其中的元素称为边.(注意:元素允许重复)
注::一个图是由表示具体事物的集合和表示事物之间的关系的集合组成的偶对.
,用直线段或者曲线段表示图的边,那么一个图可以用几何图形来表示,这也是称为图的原因,但它与几何图形有本质的区别.
、曲直、粗细、位置等都不影响图的本质,边只是表示两个研究对象之间是否存在某种关系而已.
(2) 在图G中,与V中的有序偶<vi,vj>对应的边e称为图G的有向边(或弧),vi称为e的起点,vj称为e的终点.
而与V中顶点的无序偶(vi,vj)相对应的边e,称为图G的无向边.
每条边都是有向边的图称为有向图,每条边都是无向边的图称为无向图,既有有向边又有无向边的图称为混合图.
(3)若将图G的每条边e(或每个顶点v)都对应一个实数w(e)(或w(v)),则称w(e)(w(v))为该边(顶点)的权,并称图G为赋权图.
注:一般:用(也用n或p表示) 和(也用m或q表示)分别表示图G的顶点数和边数.
例1:无向图G:V(G)={v1,v2,v3,v4}
E(G)={e1,e2,e3,e4,e5}
G
其中:e1=(v1,v2),e2=(v1,v3),e3=(v1,v4),
e4=(v1,v4),e5=(v4,v4)无向边v1,v2可交换
e3
e4
v1
v2
v3
v4
e1
e2
e5
例2:有向图: D:V(D)={v1,v2,v3,v4}
A(D)={e1,e2,e3,e4,e5}
D
e1=<v1,v2>,e2=<v1,v3>,e3=<v1,v4>,
e4=<v4,v2>,e5=<v4,v3>
注:一般用G表示无向图,D表示有向图,且记为:G(V,E);D(V,A).有向边v,E位置不可换。
v3
e3
v1
v2
v4
e1
e2
e4
e5
常用术语:
(1)端点相同的边称为环(自环),如G中的边e5;
(2)若一对顶点之间有两条以上(有向边时方向相同)的边联结,则这些边称为重边(平行边);
(3)一条边的两个端点称为相邻,有一个公共端点的边称为相邻的边;