实验5：图论的基本概念2008[1].4.28

实验5 最短路问题§5.1

图 论 的 基 本 概 念

图论的历史起源：柯尼斯堡七桥问题是图论中的著名问题。这个问题是基于一个现实生活中的事例：位于当时东普鲁士柯尼斯堡(今日俄罗斯加里宁格勒)有一条河，河中心有两个小岛(如图1)。小岛与河的两岸有七条桥连接。在所有桥都只能走一遍的前提下，如何才能把这个地方把所有的小岛都走遍。不少数学家都尝试去解析这个事例。而这些解析，最后发展成为了数学中的图论。

图1

雷翁哈得欧拉(Leonhard Euler)在1736年把问题简单化（如图2）圆满地解决了这一问题，证明这种方法并不存在。他在圣彼得堡科学院发表了图论史上第一篇重要文献。

图2

图论的应用：

1

例1:最短路问题（SPP－shortest path problem）

一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。

例2:公路连接问题

某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？

例3:指派问题（assignment problem）

一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？

其它问题：运输问题（transportation problem）、计算机图形学、网络问题等 一、 图的概念

通俗的说，图就是由点与边构成的示意图，通常用点代表所研究的对象，用连线代表两个对象之间的特定的关系；至于图中点的相对位置如何，点与点之间连线的长短曲直，对于反映对象之间的关系，并不是重要的。

2

1．

图的定义

有序三元组G=(V,E,Ψ)称为一个图(graph).其中V={v1,v2,?,vn}是有

穷非空集，称为顶点集(vertex)， 其中的元素叫图G的顶点.

[2] E称为边集，其中的元素叫图G的边（edge）. [3] ?是从边集E到顶点集V中的有序或无序的元素 偶对的集合的映射，称为关联函数（incident）. 利用图论的语言，上面图3的图可表示为 例1 设G=(V,E,?)，其中 顶点四个： V={v1 ,v2 , v3 , v4}， 边5条： E={e1, e2 , e3, e4, e5}, 相应的关联函数：

?(e1)?{v1,v2},?(e2)?{v1,v3},?(e3)?{v1,v4}. ?(e4)?{v1,v4},?(e5)?{v3,v3}2． 有向图与无向图

路有单行道与双行道，同样图也有有向图与无向图，通俗的用箭头表示。

，，

无向图 有向图 混合图

定义：

3

图的有向边（或弧）：在图G中，与V中的有序偶(vi， vj)对应的边e 图的无向边：与V中顶点的无序偶{vi , vj}相对应的边e， 无向图：每一条边都是无向边的图； 有向图：每一条边都是有向边的图； 混合图：既有无向边又有有向边的图.

注：（1）有向与无向的区别在图中用箭头区分。 （2）有序偶用（），无序偶用{ }区分。 3．

赋权图：

实例：用点代表城市，用边代表两城市有路相连，用相应的数学代表两城市的距离（单位：100公里）

赋权图：若将图G的每一条边e都对应一个实数w(e)，称w(e)为边的权，并记为(G , w)。

规定用记号ν和ε分别表示图的顶点数和边数. 4．

常用术语：

（１） 环：端点相同的边．

（２） 重边：若一对顶点之间有两条以上的边联结．

（３） 有边联结的两个顶点称为相邻的顶点，有一个公共端点的

边，称为相邻的边．

（４） 边和它的端点称为互相关联的． （５） 简单图：既没有环也没有平行边的图。

（６） 完备图：任意两顶点都相邻的简单图，记为Kn，其中n为

顶点的数目．

不是简单图

是简单图

4

K1是个点；K2是条线；K3－三角形；K4－四边形；K6－正六边形 5、顶点的次数

（１）在无向图中，与顶点v关联的边的数目（环两次）称为顶点v的次数，记为d(v)． （２）在有向图中，从顶点v引出的边的数目称为顶点v的出度， 记为d+(v)，从顶点v引入的边的数目称为v的入度，记为d-(v)， d(v)=d+(v)+d-(v)称为顶点v的次数．

d(v4

d(v)?2,d)?4, d(v)?5?44

?(v4)?3

定理１(握手引理)

?v?V(G)d(v)?2?(G)

推论１ 任何图中奇次顶点的总数必为偶数．

例1: 在一次聚会中，认识奇数个人的人数一定是偶数。 例2：七桥堡问题

二、 子图通俗的说，子图是某图的点或边是另一图的一部分。定义

设图G=(V,E,Ψ),G1=(V1,E1, Ψ1)

(1) 若V1?V，E1?E,且当e?E1时，?1(e)= ?(e),则称G1是G的子图．

特别的，若V1=V，则G1称为G的生成子图．

(2) 设V1?V，且V1??，以V1为顶点集、两个端点都在V1中的 图G的边为边集的图G的子图，称为G的由V1导出的子图，记为G[V1].

5