电子科技大学图论

1、图论是一个应用十分广泛而又极其有趣的数学分支。图论是一个应用十分广泛而又极其有趣的数学分支。物理、化学、生物、科学管理、计算机等各个领域物理、化学、生物、科学管理、计算机等各个领域都可找到图论的足迹。本讲座主要介绍图论的一些都可找到图论的足迹。本讲座主要介绍图论的一些基本知识、图论中常用的初等方法。基本知识、图论中常用的初等方法。例：可以把右图看成是例：可以把右图看成是一个公路网，一个公路网，v1,vl0是一些城镇，每条线旁是一些城镇，每条线旁边的数字代表这一段公边的数字代表这一段公路的长度。现在问，要路的长度。现在问，要从从v1把货物运到把货物运到v10。走。走哪条路最近？这个问题哪条路最近

2、？这个问题通常叫做最短路径问题通常叫做最短路径问题.图的概念图的概念图的概念图的概念例例: 上图还可看成公路网，上图还可看成公路网，v1，v2，v10看看成公路网的一个站点，若这个公路网目前被成公路网的一个站点，若这个公路网目前被敌方占领。请分析一下，能否仅破坏其公路敌方占领。请分析一下，能否仅破坏其公路网的一个站点或者至少破坏敌人哪几个站点网的一个站点或者至少破坏敌人哪几个站点，就可摧毁敌方整个运输线。，就可摧毁敌方整个运输线。这类问题称为图的连通性问题这类问题称为图的连通性问题图的概念图的概念一个图一个图G是由一个称为点集的非空集合是由一个称为点集的非空集合V(G)和和一个称为边集的集合一

3、个称为边集的集合E(G)组成的有序对组成的有序对(其中其中V(G) E(G)= =f f),记为记为G=(V(G)，E(G).简记为简记为G=(V，E).其中其中V的元素称为点或顶点，的元素称为点或顶点，E的元素称为边，并且的元素称为边，并且E中的每一个元素均与中的每一个元素均与V中的一对无序点相对应（点对中的一对无序点相对应（点对中的点可以相同）。中的点可以相同）。点集与边集均为有限集的图称为有限图。点集与边集均为有限集的图称为有限图。若边若边e对应的无序点对为对应的无序点对为u,v，则记，则记e=uv，其中，其中u,v均称均称为边为边e的端点。的端点。若用小圆点表示点若用小圆点表示点集中的

4、点，连线表集中的点，连线表示边，可用图形将示边，可用图形将图表示出来。图表示出来。图的概念图的概念例：设例：设V=v1, v2, v3, v4，E=e1, e2, e3, e4, e5 ，满足，满足 e1= v1v2， e2= v2v3， e3= v2v3， e4= v3v4， e5= v4v4，则称则称G=（V，E）是一个图。）是一个图。图的概念图的概念例：例：设设V =v1,v2,v3,v4，E =v1v2 ,v1v2,v2v3 ，则，则H = (V,E ）是一个图。）是一个图。 v1v2v3v4图的概念图的概念若边若边e与无序结点对与无序结点对(u，v)相对应，则称边相对应，则称边e为为

5、无向无向边边,记为记为e(u，v)，这时称，这时称u，v是边是边e的两个的两个端点端点；若边若边e与有序结点对与有序结点对相对应，则称边相对应，则称边e为为有向有向边边(或弧或弧)，记为，记为e，这时称，这时称u是边是边e的的始点始点(或弧尾或弧尾).v是边是边e的的终点终点(或弧头或弧头)，统称为，统称为e的的端点端点；在一个图中，关联结点在一个图中，关联结点vi和和vj的边的边e，无论是有向的，无论是有向的还是无向的，均称边还是无向的，均称边e与结点与结点vi和和vj相关联相关联，而，而vi和和vj称为称为邻接点邻接点，否则称为，否则称为不邻接的不邻接的；关联于同一个结点的两条边称为关联于

6、同一个结点的两条边称为邻接边邻接边；图的概念图的概念图中关联同一个结点的边称为图中关联同一个结点的边称为自回路自回路（或（或环环）；）；图中不与任何结点相邻接的结点称为图中不与任何结点相邻接的结点称为孤立结点孤立结点；仅由孤立结点组成的图称为仅由孤立结点组成的图称为零图零图；仅含一个结点的零图称为仅含一个结点的零图称为平凡图平凡图；含有含有n个结点、个结点、m条边的图称为条边的图称为（n，m）图）图；每条边都是无向边的图称为每条边都是无向边的图称为无向图无向图；每条边都是有向边的图称为每条边都是有向边的图称为有向图有向图；图的概念图的概念有些边是无向边有些边是无向边,而另一些是有向边的图称为而

7、另一些是有向边的图称为混合图混合图.在有向图中，两个结点间（包括结点自身间）若有同在有向图中，两个结点间（包括结点自身间）若有同始点和同终点的几条边，则这几条边称为始点和同终点的几条边，则这几条边称为平行边平行边，在，在无向图中，两个结点间（包括结点自身间）若有几条无向图中，两个结点间（包括结点自身间）若有几条边，则这几条边称为边，则这几条边称为平行边平行边，两结点，两结点vi，vj间相互平行间相互平行的边的条数称为边的边的条数称为边(vi，vj）或）或的的重数重数；含有平行边的图称为含有平行边的图称为多重图多重图。非多重图称为。非多重图称为线图线图；无；无环的线图称为环的线图称为简单图简单图

8、。图中顶点的个数称为该图的图中顶点的个数称为该图的阶阶。任意两点均相邻的简单图称为任意两点均相邻的简单图称为完全图完全图，n阶完全图阶完全图记为记为Kn。例如。例如K2, K3, K4分别为如下图所示分别为如下图所示。K2K3K4图的概念图的概念图的概念图的概念简单图简单图多重图多重图例如：例如：平凡图平凡图图的概念图的概念赋权图赋权图G是一个三重组是一个三重组或四重组或四重组，其，其中，中，V是结点集合，是结点集合，E是边的集合，是边的集合，f是从是从V到非负实数到非负实数集合的函数，集合的函数，g是从是从E到非负实数集合的函数。到非负实数集合的函数。关联矩阵和邻接矩阵：关联矩阵和邻接矩阵：

9、设图设图G = (V,E)，V = v1,v2,vn，E = e1, e2,em 。G 的的关联矩关联矩阵阵 M(G) = mij 是一个是一个 nm 矩阵，其中矩阵，其中 mij 为点为点 vi 与边与边 ej 关联的次数；关联的次数；G的的邻接矩邻接矩阵阵 A(G) = aij 是一个是一个n阶方阵，其中阶方阵，其中aij 是连是连接接 vi 与与 vj 的边的数目。的边的数目。图的概念图的概念图的关联矩阵图的关联矩阵 M(G)=mij。其中。其中mij是点是点vi与边与边ej相关相关联的次数。联的次数。 = =21000011100011100001 )(543214321eeeeevv

10、vvGM如如右右图图图的概念图的概念图的邻接矩阵图的邻接矩阵 A(G)=aij。其中。其中aij是连接点是连接点vi与点与点vi的的边的条数。边的条数。 = =1100102002010010 )(43214321vvvvvvvvGA如如右右图图图的概念图的概念无环有向图的关联矩阵无环有向图的关联矩阵 M(G)=mij。其中。其中mij是点是点vi与与边边ej相关联的次数（起点为相关联的次数（起点为-1，终点为，终点为+1）。）。 = =11000011100011110001 )(543214321eeeeevvvvGM如如右右图图图的概念图的概念有向图的邻接矩阵有向图的邻接矩阵 A(G)=

11、aij。其中。其中aij是连接点是连接点vi与点与点vi的边的条数。的边的条数。 = =1100001001010000 )(43214321vvvvvvvvGA如如右右图图图的概念图的概念图的同构：图的同构：设有图设有图G和图和图G1,如果存在双射函数如果存在双射函数g:VV1,使得对于任意的边使得对于任意的边e(vi,vj)(或或) E，当且仅当，当且仅当e1(g(vi),g(vj) (或或) E1,并且并且(vi,vj)与与(g(vi),g(vj) (或或 与与) 有相同的重数。有相同的重数。则称则称G和和G1同构同构，记为记为G G1。图的概念图的概念图的概念图的概念例例: :如下图所

12、示，如下图所示，这四个图实际上是同一个图，因为它们是同构的。这四个图实际上是同一个图，因为它们是同构的。定义：设定义：设v为为G的顶点，的顶点，G中以中以v为端点的边的条数（为端点的边的条数（环计算两次）称为环计算两次）称为v 的度数。简称为的度数。简称为v的度，记为的度，记为dG(v)，简记为，简记为d(G).如右图：如右图：3)(, 3)(, 3)(, 1)(4321= = = = =vdvdvdvd图的概念图的概念注注：该图中各点的度数之和等于该图中各点的度数之和等于10，恰好是边数，恰好是边数5的的两两倍倍图中图中d (v1) = 5，d (v2) = 4 ，d (v3) = 3，d

13、(v4) = 0，d (v5) = 2。v1v2v3v4v5例：例：注注：该图中各点的度该图中各点的度数之和等于数之和等于14，恰好是，恰好是边数边数7的的两两倍倍图的概念图的概念类似有出度和入度的概念类似有出度和入度的概念)(deg),(degvv ；mvVv2)deg(= = 1 1）在无向图）在无向图G=V，E中，则所有结点的度数的中，则所有结点的度数的总和等于边数的两倍，即：总和等于边数的两倍，即：图的概念图的概念握手定理握手定理 (欧拉欧拉)证明证明 因图因图 G 的任一条边均有两个端点的任一条边均有两个端点 (可以相同可以相同)，在计算度时恰被计算两次在计算度时恰被计算两次 (每个

14、端点各被计算了一每个端点各被计算了一次次)，所以各点的度数之和恰好为边数的两倍，即，所以各点的度数之和恰好为边数的两倍，即 上上 式成立。式成立。，mvvvmvvVvVvVvVvVv2)(deg)(deg)deg()(deg)(deg= = = = = = 2 2）在有向图）在有向图G=V，E中，则所有结点的引出度中，则所有结点的引出度数之和等于所有结点的引入度数之和，所有结点的数之和等于所有结点的引入度数之和，所有结点的度数的总和等于边数的两倍，即：度数的总和等于边数的两倍，即：图的概念图的概念握手定理握手定理 (欧拉欧拉)推论推论：在图：在图G=V，E中，其中，其V=v1,v2 ,v3 ,

15、vn ， E=e1，e2，em，度数为奇数的，度数为奇数的结点个数为偶数。结点个数为偶数。图的概念图的概念图的概念图的概念例：例：证明在任意一次集会中和奇数个人握手的证明在任意一次集会中和奇数个人握手的人的个数为偶数个。人的个数为偶数个。证明证明: 将集会中的人作为点，若两个人握手则将集会中的人作为点，若两个人握手则对应的点联边，则得简单图对应的点联边，则得简单图G。这样。这样G中点中点v的的度对应于集会中与度对应于集会中与v握手的人的个数。于是，握手的人的个数。于是，问题转化为证明问题转化为证明“任意图中度数为奇的点的个任意图中度数为奇的点的个数为偶数数为偶数”，这正是，这正是推论推论的结论

16、。的结论。定义定义：在图：在图G中，一个由不同的边组成的序列中，一个由不同的边组成的序列e1, e2, en，如果，如果ei是连接是连接vi-1与与vi (il,2,n)的，并且的，并且ei-1与与ei (il,2,n-1)相邻。我们就称这个序列为从相邻。我们就称这个序列为从v0到到vn的的一条一条通路通路(或道路或道路)，数，数n称为路长，称为路长， v0和和vn称为这条道称为这条道路的两个端点，路的两个端点， vi(1in)叫做道路的内点。如果叫做道路的内点。如果G是简单图，这条道路也可以记作是简单图，这条道路也可以记作(v0 ， v0 ， vn)。边不重复的通路称为边不重复的通路称为简单

17、通路简单通路。除了端点可相同外，任意两点都不相同的通路称为除了端点可相同外，任意两点都不相同的通路称为基基本通路本通路。显然它一定是简单通路。显然它一定是简单通路。最短路问题最短路问题 起点和终点相同的通路称为起点和终点相同的通路称为回路回路。边不重复的回路称为边不重复的回路称为简单回路简单回路。起点和终点相同的长为正的基本通路称为起点和终点相同的长为正的基本通路称为基基本回路本回路，简称，简称圈圈。定义定义：给定图：给定图G=(V,E)，对，对u,vV,若若u与与v间间存在通路，则称存在通路，则称u与与v间的最短通路的长为从间的最短通路的长为从u到到v的距离，记为的距离，记为d(u,v),若

18、若u与与v间不存在通间不存在通路，则称从路，则称从u到到v的距离为无穷。的距离为无穷。最短路问题最短路问题 例：如右图例：如右图6v5v4v3v2v1v1e9e8e7e6e5e4e3e2ev1v2v5v1v2v3v6是通路是通路v1v2v5v1v4v5v6是简单是简单通路通路v1v5v2v6是基本通路是基本通路v1v2v5v1v2v3v6v5v1是回路是回路v1v4v5v6v2v5v1是简单回路是简单回路v1v2v3v6v5v4v1是基本回路是基本回路最短路问题最短路问题 例：考虑右图例：考虑右图（1,2,3）是基本通路）是基本通路（1,1,1,2,3）是通路）是通路（1,2,4,1,4,3）

19、是简单通路）是简单通路（1,2,4,1,4,3,1）是回路）是回路（1,2,4,1,2,3,1）是简单回路）是简单回路（1,2,4,3,1）是基本回路）是基本回路最短路问题最短路问题 例例:在下图在下图G中，取中，取1 = v1v2v3 ，2 = v1v2v3v4v2 ，3 = v1v2v3v2v3v4 ( 注：注：简单图可只用点序列表通路）简单图可只用点序列表通路）v1v4v5v3v2G则则 1, 2, 3 依次为长为依次为长为2,4,5的通路，其中的通路，其中1与与2为简单通路，为简单通路，1为基为基本通路。本通路。 由定义由定义1可看出可看出,G中中 v1v2v5v1为长为为长为3的圈，

20、的圈，v1v2v3v4v2 v5v1为长为为长为6的简单回路。的简单回路。最短路问题最短路问题 最短路问题最短路问题 注：注：在回路已被定义为通路的特殊情况中，为了讨在回路已被定义为通路的特殊情况中，为了讨论问题的方便，我们约定：论问题的方便，我们约定：凡指基本通路或路均认凡指基本通路或路均认为此路不是圈。为此路不是圈。易知，图中若点易知，图中若点u与与 v间存在通路，则间存在通路，则 u 与与 v 间必存间必存在基本通路；若过点在基本通路；若过点u存在简单回路，则过点存在简单回路，则过点u必存必存在基本回路。在基本回路。定义定义:给定图给定图G = (V, E)，对，对 u, vV，若，若u

21、与与 v间存在间存在通路，则称通路，则称u与与 v间的最短通路的长为从间的最短通路的长为从u到到 v的距离，的距离，记为记为 d(u, v)；若；若u与与 v间不存在通路，则称从间不存在通路，则称从u到到 v的的距离为无穷。距离为无穷。例如右图：例如右图： d(u, v) = 2其最短路为其最短路为uxvuvwxd(u, w) = 容易证明对容易证明对 ，距离具有性质：，距离具有性质：（1）d(u, v)0；（；（2）d(u, v) = d(v, u)；（3）d(u, v) + d(v, w) d(u, w)最短路问题最短路问题 连连通通图图 G D任意两点间均存在通路的图称为任意两点间均存在

22、通路的图称为连通图连通图，否则称为，否则称为非连非连通图通图。若若H是图是图G 的连通子图且的连通子图且H不能再扩充为不能再扩充为G的任一连的任一连通子图，则称通子图，则称H为为G的连通分支。用的连通分支。用(G) 记图记图G 的连的连通分支数。通分支数。非非连连通通图图 例如：例如：(D) =3， (G) =1 最短路问题最短路问题 定义：定义：若图若图G的每一条边的每一条边e都附有一个实数都附有一个实数w(e)，则，则称称G为为权图权图。实数。实数w(e) 称为称为e的权。子图的权。子图H的各边权的各边权之和称为子图之和称为子图H的权，记为的权，记为W(H)。例如下图例如下图G为权图，其中

23、为权图，其中w(v1v2) = 1，w(v1v3) = 5，W(G) = 20。v1v3v2v4 G 1 3 5 6 5最短路问题最短路问题 设设是权图是权图G中的一条路，称中的一条路，称的各边权之和为路的各边权之和为路的的长。易知，各边的权均为长。易知，各边的权均为1的权图中的路长与非权图的权图中的路长与非权图中的路长是一致的。中的路长是一致的。权图中点权图中点u到到v的距离仍定义为点的距离仍定义为点u到到v的最短路的长，的最短路的长，仍记为仍记为d(u,v)。例：例：下图中，下图中，d(v2, v4) = 5，相应的最短路为，相应的最短路为：v2v1 v3v4。v1v3v2v4 G 1 3

24、 1 6 3最短路问题最短路问题 例（渡河问题）例（渡河问题）:一个摆渡人要把一只狼、一只羊和一个摆渡人要把一只狼、一只羊和一捆菜运过河去。由于船很小，每次摆渡人至多只一捆菜运过河去。由于船很小，每次摆渡人至多只能带一样东西。另外，如果人不在旁时，狼就要吃能带一样东西。另外，如果人不在旁时，狼就要吃羊，羊就要吃菜。问这人怎样才能安全地将它们运羊，羊就要吃菜。问这人怎样才能安全地将它们运过河去？过河去？解：用解：用F表示摆渡人表示摆渡人,W表示狼表示狼,S表示羊表示羊,C表示菜表示菜.原岸全部可能出现的状态为以下原岸全部可能出现的状态为以下16种：种： FWSC, FWS, FWC, FSC,

25、WSC(), FW（ ）, FS, FC（ ）, WS (), WC, SC(), F （ ）, W, S, C , .最短路问题最短路问题 构造一个图构造一个图G，它的顶点就是剩下的，它的顶点就是剩下的10种情况。连种情况。连边有规则是：如果经过一次渡河，情况甲可以变成边有规则是：如果经过一次渡河，情况甲可以变成情况乙，那么就在情况甲与情况乙之间连一条边情况乙，那么就在情况甲与情况乙之间连一条边(如如上图上图)。作了图。作了图G以后，渡河的问题就归结为下述问以后，渡河的问题就归结为下述问题了：在题了：在G中找一条连接顶点中找一条连接顶点FWSC和和ff，并且包，并且包含边数最少的路。含边数最

26、少的路。最短路问题最短路问题 最短路问题定义：最短路问题定义：求有向图的最短路问题求有向图的最短路问题设设G(V,E)是一个有向图，它的每一条弧是一个有向图，它的每一条弧Ai都有一个都有一个非负的长度非负的长度L(Ai)，在，在G中指定一个顶点中指定一个顶点u，要求把从，要求把从u到到G的每一个顶点的每一个顶点v的最短有向路找出来的最短有向路找出来(或者指出或者指出不存在从不存在从u到到v的有向路，认为不可达的有向路，认为不可达v).求无向图的最短路问题求无向图的最短路问题 设设G(V,E)是一个无向图，它的每一条边是一个无向图，它的每一条边Ai都有一都有一个非负的长度个非负的长度L(Ai)，

27、在，在G中指定一个顶点中指定一个顶点u，要求把，要求把从从u到到G的每一个顶点的每一个顶点v的最短无向路找出来的最短无向路找出来(或者指或者指出不存在从出不存在从u到到v的无向路，即认不可达的无向路，即认不可达v).最短路问题最短路问题 算法算法（Dijkstra算法或标号法）算法或标号法）给定简单权图给定简单权图G=（V，E），设），设|V|=n，求，求u0到到G中中各点的距离。各点的距离。2若若i=n-1，则停；否则令，则停；否则令 ，转（，转（3）iiSVS= =3对每一个对每一个 ，令，令iSv vlvuwulvlvliSvii)(min ),()(),(min)( = =计算计算并用

28、并用ui+1记达最小值的某点。置记达最小值的某点。置Si+1=Siui+1，i=i+1，转（，转（2）。）。最短路问题最短路问题 1置置l(u0)=0；对所有；对所有vVu0，令，令l(v)=；S0=u0，i=0。说明：说明： （1 1） 算法中算法中w(ui，v) 表示边表示边 uiv 的权；的权； （2 2） 若只想确定若只想确定u0到某顶点到某顶点v0的距离，的距离， 则当某则当某uj等于等于v0 时即停；时即停；（3 3）算法稍加改进可同时得出）算法稍加改进可同时得出u0到其它点到其它点的最短路。的最短路。最短路问题最短路问题 例：求右图例：求右图u0到其到其它点的距离。它点的距离。0

29、u713851452解：解：第第1步：初始标号步：初始标号0,)(, 0)(0000= = = = = =iuSSVvvlul)0 ,(0u713851452 最短路问题最短路问题 第二步：计算第二步：计算l(v)0,(0u713851452274 第三步：求第三步：求ui+1),()(),(min)(vuwulvlvlii = =1,)(min 101= = = iuuS vliSv)0,(0u713851452)2,(1u74 最短路问题最短路问题 类似地。类似地。)0,(0u713851452)2,(1u7377)0,(0u713851452)2,(1u7)3,(2u77最短路问题最短路

30、问题 )0,(0u713851452)2,(1u6)3,(2u47)0,(0u713851452)2,(1u6)3,(2u)4,(3u7最短路问题最短路问题 )0,(0u713851452)2,(1u)6,(4u)3,(2u)4,(3u7)0,(0u713851452)2,(1u)6,(4u)3,(2u)4,(3u)7,(5u最短路问题最短路问题 另：最短路的规划算法另：最短路的规划算法假设图假设图G(V,E)有有n个顶点个顶点, 现要求从顶点现要求从顶点1到到顶点顶点n的最短路的最短路. 设决策变量为设决策变量为xij,当当xij =1时时,说明说明弧弧(i, j)位于顶点位于顶点1到顶点到

31、顶点n的最短路上的最短路上; 否则否则xij =0. 其数学规划的表达式为其数学规划的表达式为: Ejiijijxw),(minEjixniniixxthatsuchijnEjijjinEjijij = = = = = = = = =),(, 0, 10111),(1),(1求最短路的应用求最短路的应用例：在纵横交错的公路网中例：在纵横交错的公路网中,货车司机希望找到一货车司机希望找到一条从一个城市到另一个城市的最短路条从一个城市到另一个城市的最短路.假设下图表假设下图表示的是该公路网示的是该公路网,节点是表示货车可以停靠的城市节点是表示货车可以停靠的城市,弧上的权表示两个城市之间的距离弧上的

32、权表示两个城市之间的距离(百公里百公里),那么那么从城市从城市S出发到城市出发到城市T,如何选择行驶路线如何选择行驶路线,使经过使经过的路程最短的路程最短?S713851452T求最短路的应用求最短路的应用解：对顶点编号解：对顶点编号S=1,T=6找到各边的权找到各边的权 = =018050100314800050030007515002040720wS713851452T235461决策变量为决策变量为0 ijx求最短路的应用求最短路的应用! 这是一个求最短路的这是一个求最短路的LINGO示范程序示范程序;sets:! 这是六个城市的集合这是六个城市的集合; cities/1, 2, 3,

33、4, 5, 6/; ! 城市之间存在的路由为城市集合的派生集合城市之间存在的路由为城市集合的派生集合; roads(cities, cities)/ 1,2 1,5 1,3 2,4 2,6 2,5 3,5 4,6 5,6 2,1 5,1 3,1 4,2 6,2 5,2 5,3 6,4 6,5/: w, x;endsets求最短路的应用求最短路的应用data: ! 对应城市之间路的长度对应城市之间路的长度; w = 2 4 7 5 5 1 3 8 1 2 4 7 5 5 1 3 8 1;enddatan=size(cities); ! 城市的个数城市的个数;min=sum(roads: w*x)

34、;for(cities(i) | i #ne# 1 #and# i #ne# n: sum(roads(i,j): x(i,j) = sum(roads(j,i): x(j,i);sum(roads(i,j)|i #eq# 1 : x(i,j)=1;sum(roads(i,j)|j #eq# n : x(i,j)=1;for(roads:BIN(x);end求最短路的应用求最短路的应用解得：解得：Global optimal solution found. Objective value: 4.000000求最短路的应用求最短路的应用X( 1, 2) 1.000000 X( 2, 5) 1.0

35、00000X( 5, 6) 1.000000其余的其余的 X 全部取零全部取零例例:某公司在六个城市某公司在六个城市x1, x2, x3, x4, x5, x6中都设中都设有分公司从有分公司从xi,到到xj, 直接航程票价由下列矩直接航程票价由下列矩阵的第阵的第(i，j)个元素给出个元素给出(表示无直达航线表示无直达航线)请你为该公司制作一张任意两城市之间的最请你为该公司制作一张任意两城市之间的最廉价路线表廉价路线表最短路问题最短路问题 最短路问题最短路问题 例：设备更新问题例：设备更新问题 企业在使用某设备时，每年年初可购置新设备，企业在使用某设备时，每年年初可购置新设备，也可以使用一年或几

36、年后卖掉重新购置新设备。已也可以使用一年或几年后卖掉重新购置新设备。已知知4年年初购置新设备的价格分别为年年初购置新设备的价格分别为2.5、2.6、2.8和和3.1万元。设备使用了万元。设备使用了14年后设备的残值分别为年后设备的残值分别为2、1.6、1.3和和1.1万元，使用时间在万元，使用时间在14年内的维修年内的维修保养费用分别为保养费用分别为0.3、0.8、1.5和和2.0万元。试确定一万元。试确定一个设备更新策略，在下例两种情形下使个设备更新策略，在下例两种情形下使4年的设备年的设备购置和维护总费用最小。购置和维护总费用最小。（1）第）第4年年末设备一定处理掉；年年末设备一定处理掉；

37、（2）第）第4年年末设备不处理。年年末设备不处理。上面的数据可整理如下表：上面的数据可整理如下表： 最短路问题最短路问题 年数年数第一年第一年第二年第二年第三年第三年第四年第四年购置价格购置价格2.52.52.62.62.82.83.13.1维修保养费维修保养费0.30.30.80.81.51.52.02.0使用残值使用残值2 21.61.61.31.31.11.1 用点用点(1,2,3,4,5)表示第表示第1年年初购置设备使用到第年年初购置设备使用到第i年年初更新，经过若干次更新使用到第年年初更新，经过若干次更新使用到第5年年初，年年初，第第1年年初和第年年初和第5年年初分别用及表示。使用过

38、年年初分别用及表示。使用过程用弧连接起来，弧上的权表示总费用程用弧连接起来，弧上的权表示总费用(购置费维购置费维护费残值护费残值)，如图所示，如图所示 最短路问题最短路问题 154322.5+0.3-22.5+0.3+0.8-1.62.5+0.3+0.8+1.5-1.32.5+0.3+0.8+1.5+2.0-1.12.6+0.3-22.8+0.3-23.1+0.3-22.6+0.3+0.8-1.62.8+0.3+0.8-1.62.6+0.3+0.8+1.5-1.3最短路问题最短路问题 154320.823.860.92.93.22.12.33.9例：求图的中心例：求图的中心如学校的选址问题。如

39、学校的选址问题。最短路问题最短路问题 图的概念图的概念子图的定义：子图的定义：设有图设有图G和图和图G1,若若G和和G1满足：满足：1)若若V1 V，E1 E, 则称则称G1是是G的的子图子图, 记为记为G1 G;2)若若G1 G, 且且G1 G（即（即V1 V或或E1 E）, 则称则称G1是是G的的真子图真子图, 记为记为G1 G;即即V1=V, 则称则称G1是是G的的生成子图生成子图3)若若V2 V, V2 ,以以V2为结点集为结点集,以两个端点均在以两个端点均在V2中中的边的全体为边集的的边的全体为边集的G的子图称为的子图称为V2导出的子图导出的子图, 简简称称G的的(点点)导出子图导出

40、子图.图的概念图的概念4)若若E2 E，E2 ，以，以E2为边集，以为边集，以E2相关联的顶点相关联的顶点的全体为顶点集的的全体为顶点集的G的子图称为的子图称为E2导出的子图导出的子图，简，简称称G的的(边边)导出子图导出子图。5)设设G为具有为具有n个结点的简单图个结点的简单图, 从完全图从完全图Kn中删去中删去G中的所有的边而得到的图称为中的所有的边而得到的图称为G的的补图补图（或或G的的补补），），记为记为G。6)设设G为具有为具有n个结点的简单图，图个结点的简单图，图 G1 是是G的一个子图，从图的一个子图，从图G中删去中删去G1中的所中的所有的边而得到的图称为有的边而得到的图称为G1

41、相对于相对于G的的补图补图（或或G1在在G中的中的补补）。在下图中，给出了图在下图中，给出了图G以及它的真子图以及它的真子图G和生成子和生成子图图G”. G1是结点集是结点集v1，v2，v3，v4，v5的导出子图的导出子图图的概念图的概念在下图中，给出了图在下图中，给出了图G以及它的真子图以及它的真子图G和子图和子图G”. 其中其中G”是是G在在G中的补图中的补图图的概念图的概念树树树的定义：树的定义：无圈的连通图称为树。树中度为无圈的连通图称为树。树中度为1 1的点称为树叶，其余点称为分枝点。的点称为树叶，其余点称为分枝点。树树树树不是树不是树不是树不是树例例平凡树平凡树定理：定理：设设G是

42、具有是具有n个点个点m条边的图，则以下条边的图，则以下关于树的命题等价。关于树的命题等价。（1）G是树。是树。（2）G 中任意两个不同点之间存在唯一的路。中任意两个不同点之间存在唯一的路。（3）G 连通，删去任一边便不连通。连通，删去任一边便不连通。（4）G 连通，且连通，且n = m+1。（5）G 无圈，且无圈，且n= m+1。（6）G 无圈，添加任一条边可得唯一的圈。无圈，添加任一条边可得唯一的圈。树树（2）G中任意两个不同点之间存在唯一的路中任意两个不同点之间存在唯一的路（1）G 是是树树 因因G是树，树是连通的，故是树，树是连通的，故G中任意两个不同点之中任意两个不同点之间存在路。下证

43、唯一性。间存在路。下证唯一性。 若不然，设点若不然，设点u与与v之间存在两条不同的路之间存在两条不同的路1与与2。从从u出发沿出发沿1搜索，设搜索，设x是具有第一个如下性质的点：是具有第一个如下性质的点：它在它在2上，但它的下一个点上，但它的下一个点w不在不在2上；继续搜索，上；继续搜索，设设y是是w之后的第一个既在之后的第一个既在1上又在上又在2上的点。这样上的点。这样1上从上从x到到y段与段与2上从上从y到到x段便构成一个圈，这与段便构成一个圈，这与G是树无圈矛盾，所以任意两点间的路唯一。是树无圈矛盾，所以任意两点间的路唯一。树树（4）G 连通，且连通，且n= m+1“G 连通，删去任一边

44、便不连通连通，删去任一边便不连通只需证只需证 n= m+1即可。对即可。对n用归纳法。用归纳法。当当n = 1时，时，G无边，满足无边，满足n = m+1。设对少于设对少于n个点的图（个点的图（4）的结论成立。）的结论成立。对于有对于有n个点的图个点的图G，由（，由（3）的假设知删去）的假设知删去G中某边可得中某边可得两个具有同样性质的子图两个具有同样性质的子图G1与与G2。设。设Gi 的点数与边数分别的点数与边数分别为为ni 与与mi（i =1,2）。显然）。显然n1 n，n2 (G) 的点的点v为为割点割点。易知，若。易知，若v是是G的割点，则的割点，则v是是G的的1-顶点割顶点割。例如对

45、上例中的例如对上例中的G， V= v3, v6是是2-顶点割，顶点割，v5是割点。是割点。树树v1v2v3v6v5v4e1e2e3e4e5e6定义：定义：给定给定 n 阶图阶图 G，若，若 G 中存在两个不相邻的中存在两个不相邻的顶点，则令顶点，则令(G) = minkG中存在中存在k顶点割顶点割，否，否则，令则，令(G) = n 1。称称 (G) 为图为图 G 的的连通度连通度，简记，简记 (G) 为为 。若。若 (G)k，则称，则称 G 为为 k 连通的连通的。由定义由定义2，若，若G不连通或不连通或G是平凡图，则是平凡图，则=0。树树树树G1G3G4G2u(G1) =(G2) =1(G3

46、) =2(G4) = 4满足满足 (G - e) (G) 的边的边 e 称为称为 G 的割边。的割边。定义定义3 给定图给定图G，设，设S为为V(G) 的非空子集，令的非空子集，令 S, 表示表示G中两端点分属于中两端点分属于 S 与与 的边组成的集的边组成的集合，则称合，则称 S, 为为G的边割，其中的边割，其中 = (G)S。SSSS例如非平凡树中每条边均为割边。边割是割边的推例如非平凡树中每条边均为割边。边割是割边的推广。当广。当G连通时，边割是指删去一组边使连通时，边割是指删去一组边使G不连通的不连通的这组边构成的集合。这组边构成的集合。树树定义：定义：若若G 为非平凡图，令为非平凡图

47、，令 (G) = minkG 中存在中存在 k 边割边割 否则令否则令 (G)=0则称则称 (G)（简记为（简记为 ）为）为G 的边连通度。的边连通度。若若 (G) k，则称，则称G为为k 边连通的。边连通的。树树树树G1G3G4G2u(G1) =1 ，(G2) =2(G3) =2(G4) = 4例定理：定理：任意的图均满足：任意的图均满足： 。是显然的，是显然的， 的证明从略。的证明从略。也存在满足也存在满足 = level(i) + x(i,j) - (n-2)*(1-x(i,j) + (n-3)*x(j,i); );! The level of city is at least 1 bu

48、t no more n-1, and is 1 if it links to base (city 1); bnd(1,level(i),999); level(i) 1 =|V |可验证彼得森图（下图（可验证彼得森图（下图（b b）所示）不是哈密尔顿图，）所示）不是哈密尔顿图，但满足定理的条件。这表明定理所给出的条件只是但满足定理的条件。这表明定理所给出的条件只是哈密尔顿图的必要条件而不是充分条件。哈密尔顿图的必要条件而不是充分条件。 (b)欧拉图和哈密尔顿图欧拉图和哈密尔顿图 （a）v设设G是具有是具有n 个点的简单图，则对个点的简单图，则对G的任意两个的任意两个不相邻顶点不相邻顶点 u

49、和和 v ，（1）若）若d(u) + d(v)n-1, 则则 G 有有哈密尔顿路哈密尔顿路；（2）若）若d(u) + d(v)n, 则则 G 是是哈密尔顿图哈密尔顿图。由定理可知当由定理可知当n3时，时， Kn是哈密尔顿图。是哈密尔顿图。是哈密尔顿图，是哈密尔顿图，但不满足定理的条件但不满足定理的条件故该定理的条件是哈密尔顿图的充分条件，但不是故该定理的条件是哈密尔顿图的充分条件，但不是必要条件。必要条件。欧拉图和哈密尔顿图欧拉图和哈密尔顿图 说明：判断一个图是否哈密尔顿图，往往要结合定义说明：判断一个图是否哈密尔顿图，往往要结合定义进行。由定义知：一个图若有度为进行。由定义知：一个图若有度为

50、1 1的顶点，一定不的顶点，一定不是哈密尔顿图，只可能有哈密尔顿路；若图是哈密尔是哈密尔顿图，只可能有哈密尔顿路；若图是哈密尔顿图，则图中顿图，则图中2 2度顶点关联的边必属于所有哈密尔顿度顶点关联的边必属于所有哈密尔顿圈；一个顶点关联的边再多，一个哈密尔顿圈只能用圈；一个顶点关联的边再多，一个哈密尔顿圈只能用其两条边。其两条边。左图不是哈密尔顿图，左图不是哈密尔顿图，因图中二度顶点所关联因图中二度顶点所关联的的8 8条边（红边）已构条边（红边）已构成圈，而此圈不是哈密成圈，而此圈不是哈密尔顿圈。尔顿圈。欧拉图和哈密尔顿图欧拉图和哈密尔顿图 问题：问题：一个旅行售货员想访问若干城市（假定一个旅

51、行售货员想访问若干城市（假定各城镇之间均有路可通），然后返回。问如何各城镇之间均有路可通），然后返回。问如何安排路线使其能恰好访问每个城镇一次且走过安排路线使其能恰好访问每个城镇一次且走过的总路程最短？这个问题称为旅行售货员问题，的总路程最短？这个问题称为旅行售货员问题，它的图论模型为：在赋权完全图它的图论模型为：在赋权完全图G中求具有最中求具有最小权的哈密尔顿圈，这个圈称为小权的哈密尔顿圈，这个圈称为最优圈最优圈。求最优圈，目前还没有一个理想的算法。求最优圈，目前还没有一个理想的算法。欧拉图和哈密尔顿图欧拉图和哈密尔顿图 一个可行解法：一个可行解法： （1）任取）任取G 的一个哈密尔顿圈的一

52、个哈密尔顿圈C。 （2）修改修改 C 为为 Cij 使使Cij 比比 C 优，其方法为：设优，其方法为：设 C = v1 v2vn v1，若存在整数，若存在整数 i，j，满足满足0 i+1j 23 = w (cd) + w(ab) 取取 C = b c d a b如图（如图（c）所示）所示(a) bacd10181171412欧拉图和哈密尔顿图欧拉图和哈密尔顿图 (b) bacd10181171412(c) bacd10181171412另：最优另：最优Hamilton圈规划表达式圈规划表达式设设 dij 是两个点是两个点 i 与与 j 之间的距离，之间的距离，xij 0 或或 1（1表示连接

53、，表示连接，0 表示不连接），则有：表示不连接），则有：, 1, 1.min),(= = = ViijVjijAjiijijxxtsxd每个顶点只有一条边出去每个顶点只有一条边出去除起点和终点外，各边不构成圈除起点和终点外，各边不构成圈欧拉图和哈密尔顿图欧拉图和哈密尔顿图 每个顶点只有一条边进入每个顶点只有一条边进入例：例：图图 G 如所示，求如所示，求G的的最优最优HamiltonHamilton圈。圈。v1v7v2v3v4v6v5123465156432解：对顶点编号为解：对顶点编号为1到到7，找到各边的权找到各边的权 = =04100510022406110010031006051001

54、00100515063100100100100604100210010034012310010010010w决策变量为决策变量为0 ijx注：没有的边则取值注：没有的边则取值超过所有边权之和，超过所有边权之和，以顶点以顶点1 为起点。为起点。欧拉图和哈密尔顿图欧拉图和哈密尔顿图 求解程序为：求解程序为：!define sets;sets: cities/1.7/:level; !level(i)= the level of city; link(cities, cities): distance, !The distance matrix; x; ! x(i,j)=1 if we use li

55、nk i, j;endsets欧拉图和哈密尔顿图欧拉图和哈密尔顿图 !define datas;data: !Distance matrix, it need not be symmetirc; distance = 0 1 100 100 100 3 2 1 0 4 3 100 100 2 100 4 0 6 100 100 100 100 3 6 0 5 1 5 100 100 100 5 0 6 100 3 100 100 1 6 0 4 2 2 100 5 100 4 0 ;enddata欧拉图和哈密尔顿图欧拉图和哈密尔顿图 ! Minimize total distance of t

56、he links;min=sum(link(i,j)|i #ne# j: distance(i,j)*x(i,j);n=size(cities); !The model size;!For city i;for(cities(i) :! It must be entered; sum(cities(j)| j #ne# i: x(j,i)=1;! It must be departed; sum(cities(j)| j #ne# i: x(i,j)=1; );欧拉图和哈密尔顿图欧拉图和哈密尔顿图 for(cities(i) :! level(j)=levle(i)+1, if we link

57、 j and i; for(cities(j)| j #gt# 1 #and# j #ne# i : level(j) = level(i) + x(i,j) - (n-2)*(1-x(i,j) + (n-3)*x(j,i); ); );! Make the xs 0/1;for(link : bin(x);! For the first and last stop;for(cities(i) | i #gt# 1 : level(i)=1+(n-2)*x(i,1); );欧拉图和哈密尔顿图欧拉图和哈密尔顿图 求解结果为：求解结果为：目标值为目标值为28解为：解为：X( 1, 7) 1.000

58、000X( 2, 1) 1.000000X( 3, 2) 1.000000X( 4, 3) 1.000000X( 5, 4) 1.000000X( 6, 5) 1.000000X( 7, 6) 1.000000v1v7v2v3v4v6v5123465156432欧拉图和哈密尔顿图欧拉图和哈密尔顿图 着色、匹配、平面图着色、匹配、平面图四色问题四色问题1840年数学家麦比乌斯（年数学家麦比乌斯（Mbius）提出一个猜想：）提出一个猜想：任何平面地图，总可以把它的一个国家用四种颜色任何平面地图，总可以把它的一个国家用四种颜色的一种着染，使相邻国家着不同色。的一种着染，使相邻国家着不同色。这就是著名

59、的这就是著名的四色猜想四色猜想。1890年希五德（年希五德（Heawood）指出指出“4换为换为5”猜想成立。猜想成立。1976年两位数学家在三台百年两位数学家在三台百万次的电子计算机上花了万次的电子计算机上花了1200小时证明了猜想成立。小时证明了猜想成立。猜想成为定理。猜想成为定理。映射映射设设A, B是两个集合，是两个集合，是是A到到B的一个映射，记为的一个映射，记为 ：AB，对，对记记特别地当特别地当 Bb 时，时，-1(B)也记为也记为 -1(b)。着色、匹配、平面图着色、匹配、平面图BBAA , )(|) ( | )() (1BxxBAaaA = = = = f ff ff ff

60、f定义：定义：给定图给定图G =(V,E),称映射称映射：E 1,2, k为为 G 的一个的一个k-边着色边着色，简称，简称边着色边着色，称，称 1,2, k 为为色集色集。若。若为为G 的边着色且的边着色且e,e E当当e 与与e相邻相邻时，时，(e) (e) ，则称该着色是，则称该着色是正常正常的。图的。图 G 的正的正常常 k-边着色的最小边着色的最小 k 值称为值称为 G 的的边色数边色数，记为，记为c (G), 简记为简记为c 。 若图若图 G 存在一个正常存在一个正常 k-边着色，则称边着色，则称 G 是是 k-边可边可着色的着色的。若若为图为图G 的边着色，的边着色，e为为G的边