最短路径讲稿20110812.ppt

2011全国大学生数学建模竞赛将于2011年9月9日上午8点（星期五）到9月12日上午8点进行（星期一）竞赛共进行3天，比惯例少了近12小时 §1 图论的基本概念 前言 在现实生活以及科学研究中，人们经常遇到各种事物之间的关系，要将各种关系形象而直观地描述出来，人们常用点表示事物、用点之间是否有线表示事物之间是否有某种联系。于是点与点之间的若干条连线就构成了图。 图论最早起源于一些数学游戏的难题研究。如著名的哥尼斯堡(Konigsberg)七桥问题。 18世纪的哥尼斯堡城 隶属东普鲁士，它位 于普雷格尔(Pregel) 河畔，河中有两个岛， 通过七桥彼此相连。 如右图。 由于我们的要求只是不在桥上重复走，因此可以在陆地上随便走。从而可以把陆地缩成一点(这一点非常重要，是关键！)。因此可以将七桥问题简化如下图。 §0、前言 现实生活中，许多问题都可以归结为由点和线组成的图形问题。比如： 由点代表车站、线代表铁路线的铁路网络图； 由点代表车站、线代表公路线的公路网络图； 由点代表路口、线代表街道的的城市交通图； 由点代表管道接头、线代表管道的自来水供水系统； 由点代表网络节点、线代表节点间的电器元件的电网络图等等 。 图论正是研究这些由点和线组成的“图形”的问题。 §1 、图的概念 一、图的定义 1、有序三元组G=(V,E,?)称为一个图。其中 V={v1,v2,?,vn}是有限非空集，称为顶点集，其中的元素叫图G的顶点。 E称为边集，其中的元素叫图G的边。 ?是从边集E到顶点集V中的有序或无序的元素偶对的集合的映射，称为关联函数。 例1、设G=(V,E,?)，其中V={v1,v2,v3,v4}，E={e1,e2,e3,e4,e5}，?(e1)=v1v2，?(e2)=v1v3，?(e3)=v1v4，?(e4)=v1v4，?(e5)=v3v3。 G的图解如图。 2、赋权图 若将图G的每一条边e都对应一个实数w(e)，称w(e)为边的权，并称图G为赋权图。 规定用记号v和?分别表示图的顶点数和边数。 3、其它的一些图 在图G中，与V中的有序偶(vi,vj)对应的边e，称为图的有向边(或弧)，而与V中顶点的无序偶vi,vj相对应的边e，称为图的无向边。 每一条边都是无向边的图，叫无向图； 每一条边都是有向边的图，称为有向图； 既有无向边又有有向边的图称为混合图。 常用术语： 1)、端点相同的边称为环。 2)、一对顶点之间有两2条以上 的边联结，这些边称为重边。 3)、有边联结的两个顶点称为相邻的顶点，有一个公共端点的边称为相邻的边。 4)、边和它的端点称为互相关联的， 5)、既没有环也没有平行边的图，称为简单图， 6)、任意两顶点都相邻的简单图，称为完备图，记为Kn，其中n为顶点的数目。 二、图的矩阵表示 图除了用“几何图形”表示外，还可以用矩阵表示。用矩阵表示有利于计算机处理。常用的矩阵有关联矩阵、邻接矩阵。 1、关联矩阵 它表示的是图中节点与边之间的关联关系。 (1)、无向图 定义 任意无向图G=(V，E)，对节点编号V={v1，v2，…，vn}，对边编号E={e1，e2，…，em}。 M(G)=(mij)n?m 其中mij是vi与ej的关联次数，?i，j。 三、子图与生成子图 设有图G=V,E和图G1=V1,E1。若G和G1满足： 1)、若V1?V，E1?E，则称G1是G的子图，记为G1?G； 2)、若G1?G，且G1?G(即V1?V或E1?E)，则称G1是G的真子图，记为G1?G； 3)、若V1=V，E1?E，则称G1是G的生成子图，记为G1?G； 例2： 四、点的度 1、无向图 假设G是一个无向图。v为图G的节点，G中与v关联的边的条数（环计算两次），称为点v的度数(degree)，记为deg(v)。 §2 、路、连通性 1、设G=V,E是一个图(有向或无向均可)，考虑图G中边的序列:v0,v1