课程名称：《运筹学》第_16_讲次1、图与网络的基本知识2、树授课题目3、最短路问题本讲目的要求及重点难点：【目的要求】1、正确理解图的基本概念与基本定理；2、理解树与最小支撑数的概念及求最小树的算法，理解欧拉图与最优投递路线问题的解法；3、熟练掌握赋权的最短通路问题及其Dijkstra算法，[重点及难点】求最短路问题。内容[本讲课程的引入]图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。[本讲课程的内容]一、图与网络的基本知识1、图与网络的基本概念在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。我们用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。一般来说，通常用点表示研究对象，用点与点之间的线表示研究对象之间的特定关系。由于在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显得并不重要，因此，图论中的图与几何图形或工程制图等本质上是不同的
课程名称：《运筹学》 第 16 讲次 授课题目 1、图与网络的基本知识 2、树 3、最短路问题 本讲目的要求及重点难点： 目的要求] 1、正确理解图的基本概念与基本定理；2、理解树与最小支撑数的概念及求 最小树的算法，理解欧拉图与最优投递路线问题的解法；3、熟练掌握赋权的最短通路问 题及其 Dijkstra 算法， [重点及难点] 求最短路问题。 内 容 [本讲课程的引入] 图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交 通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同 图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网 络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。随着科学技术的进步，特别 是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系 统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来 越受到工程技术人员和经营管理人员的重视。 [本讲课程的内容] 一、 图与网络的基本知识 1、 图与网络的基本概念 在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样 的示意图。我们用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关 系。一般来说，通常用点表示研究对象，用点与点之间的线表示研究对象之间的特定关系。由于在一 般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显得并 不重要，因此，图论中的图与几何图形或工程制图等本质上是不同的
内容定义1一个图是由点集V=和V中元素的无序对的一个集合E=(e所构成的二元组，记为G-(V，E)，其中V中的元素v,叫做顶点，V表示图G的点集合：E中的元素e,叫做边，E表示图G的边集合。例8.1在图8—2中：V=(11,'2,1'3,V4,'s,Ve)E=(e,e,es,ey,es,es,er,eg,eg,eo)eio其中ei=(vi,V2)，e2=(i,V2)e, =(v2,V3], ex =(V3,V4,图8—2e,=(11,V3),eg=(V3,Vs),en=(V3,Vs),eg=(vs,V6),eg=(V6,Ve],e1o=(v1,V6)如果两个点u,veV，且边(u,")eE，则称u,v两点相邻。u,v称为边(u,v)的端点。如果两条边er,e,eE，且它们有一个公共端点u，则称e,e,相邻，边ei,e,称为点u的关联边。通常，我们把点与点之间不带箭头的线叫做边，带箭头的线（V中元素的有序对）叫做弧。如果一个图是由点和边所构成的，则称其为无向图，记作G=(V，E)，连接点的y，eV边记作[vi,，或者[yj.。图8—2是无向图。如果一个图是由点和弧所构成的，那么称为它为有向图，记作D=(V,A)，其中V表示有向图D的点集合，A表示有向图D的弧集合。一条方向从vi指向y的弧，记作(vi.y)。图8—3为有向图。其中=(,24V%)A= ((11, 1), (12, V), (/2, 15),(12, V5), (13, V5s), (v4, Vs ),图8—3(vs, V4), (vs, V6) )一条边的两个端点是相同的，那么称为这条
内 容 定义 1 一个图是由点集 V v j 和 V 中元素的无序对的一个集合 { }k E e 所构成的 二元组，记为 G=(V，E)，其中 V 中的元素 j v 叫做顶点，V 表示图 G 的点集合；E 中的元 素 k e 叫做边，E 表示图 G 的边集合。 例 8.1 在图 8—2 中： V v1 ,v2 ,v3 ,v4 ,v5 , v6 { , , , , , , , , } 1 2 3 4 5 6 7 8 9 10 E e ，e e e e e e e e e 其中 { , } 1 1 2 e v v ， { , } 2 1 2 e v v ， { , } 3 2 3 e v v ， { , } 4 3 4 e v v ， { , } 5 1 3 e v v ， { , } 6 3 5 e v v ， { , } 7 3 5 e v v ， { , } 8 5 6 e v v ， { , } 9 6 6 e v v ， { , } 10 1 6 e v v 。 如果两个点 u,v V ，且边 (u,v) E ，则称 u,v 两点相邻。u,v 称为边 (u,v) 的端 点。 如果两条边 ei , ej E ，且它们有一个公共端点 u ，则称 i j e , e 相邻，边 i j e , e 称为点 u 的关联边。 通常，我们把点与点之间不带箭头的线叫做边，带箭头的线（V 中元素的有序对）叫 做弧。如果一个图是由点和边所构成的，则称其为无向图，记作 G=(V，E)，连接点的 vi , v j V 边记作[vi , vj ]，或者[vj , vi ]。 图 8—2 是无向图。 如果一个图是由点和弧所构成的，那么称为它为有向图，记作 D=(V, A)，其中 V 表示 有向图 D 的点集合，A 表示有向图 D 的弧集合。一条方向从 vi 指向 vj 的弧，记作(vi , vj )。 图 8—3 为有向图。 其中 V = {v1 , v2 , v3 , v4 , v5 , v6 }， A = {(v1 , v3 ) , (v2 , v1) , (v2 , v3 ) , (v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) } 一条边的两个端点是相同的,那么称为这条 v1 v2 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 图 8—2 v4 v6 v1 v2 v3 v5 图 8—3
内容边是环。如图8—2中的边（%%）是环。如果两个端点之间有两条以上的边，那么称为它们为多重边。如图8—2中的边（"），（2"）。定义2一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。定义3每一对顶点间都有边相连的无向简单图称为完全图。有n个顶点的无向完全图记作K，。有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。定义4以点为端点的边的个数称为点v的度，记作d(v)。例如在图8—2中，d(v)=4，d(%)=4。度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。定理1所有顶点度数之和等于所有边数的2倍。证明因为在计算各个点的度时，每条边被它的两个端点各用了一次。定理2在任一图中，奇点的个数必为偶数。证明设V1，V2分别是图G中奇点和偶点的集合，由定理1，有d(v)+d(v)=d(v)=2q因为d(v)是偶数，d()vEVveNveN也是偶数，因此d(v)也必是偶数，从而V1中的点数是偶数。veN定义5有向图中，以v,为始点的边数称为点v的出次，用d+（y）表示；以v为终点的边数称为点v,的入次，用d-(v）表示：V,点的出次和入次之和就是该点的次。结论：所有顶点的入次之和等于所有顶点的出次之和。定义6设Gj=（V1,E1），G2=（V2,E2）如果V2V1,E2CE1称G2是GI的子图：如果V2=V1,E2CE1称G2是G1的部分图或支撑子图。2enSVe6Pei56es2O(c)(a)(bh)图8—4
内 容 边是环。如图 8—2 中的边（v 6 ,v6）是环。如果两个端点之间有两条以上的边，那么 称为它们为多重边。如图 8—2 中的边（v 1 ,v2） ，（v 2 ,v1）。 定义 2 一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。 定义 3 每一对顶点间都有边相连的无向简单图称为完全图。有 n 个顶点的无向完全 图记作 Kn 。 有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。 定义 4 以点 v 为端点的边的个数称为点 v 的度，记作 d(v) 。 例如在图 8—2 中，d(v1)= 4，d(v6)= 4。 度为零的点称为弧立点，度为 1 的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数 的点称为奇点，度为偶数的点称为偶点。 定理 1 所有顶点度数之和等于所有边数的 2 倍。 证明 因为在计算各个点的度时，每条边被它的两个端点各用了一次。 定理 2 在任一图中，奇点的个数必为偶数。 证明 设 V1，V2 分别是图 G 中奇点和偶点的集合，由定理 1 ，有 1 2 ( ) ( ) ( ) 2 v V v V v V d v d v d v q 因为 vV d(v) 是偶数， 2 ( ) v V d v 也是偶数，因此 1 ( ) v V d v 也必是偶数，从而 V1 中的点数是偶数。 定义 5 有向图中，以 i v 为始点的边数称为点 i v 的出次，用 ( ) i d v 表示；以 i v 为终 点的边数称为点 i v 的入次，用 ( ) i d v 表示； i v 点的出次和入次之和就是该点的次。 结论：所有顶点的入次之和等于所有顶点的出次之和。 定义 6 设 G1 =（ V1 , E1 ），G2 =（ V2 ,E2 ）如果 V2 V1 , E2 E1 称 G2 是 G1 的子图；如果 V2 = V1 , E2 E1 称 G2 是 G1 的部分图或支撑子图。 e5 e7 v1 v2 v6 v5 v7 e1 e6 e8 (b) v1 v2 v3 v4 v5 v6 v7 e1 e6 e7 e9 e10 e11 (c) v1 v2 v3 v4 v6 v5 v7 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 (a) 图 8—4
内容在图8一4中（b）为（a）的子图，（c）为（a）的子图在实际应用中，给定一个图G=（V，E）或有向图D=（V，A），在V中指定两个点，一个称为始点（或发点），记作，一个称为终点（或收点），记作，其余的点称为中间点。对每一条弧（"，)EA，对应一个数Wij，称为弧上的“权”。通常把这种赋权的图称为网络。2、连通图定义7由两两相邻的点及其相关联的边构成的点边序列称为链。如:。，eV,e22e，a，m,记作（o，，P2,)其链长为n，其中v。，v分别称为链的起点和终点。若链中所含的边均不相同，则称此链为简单链；所含的点均不相同的链称为初等链，也称通路。e3e1V3e6VsV5图8—6在图8—5图8s5(，e4，4，e7，v，e7，图，，%1为一条链，起点为2，终点为%，链长为4S=(，e4，V4，e7，'s，es，4，eg，%1为一条连接2和%简单链。S,=z，e4，4，eg，%为一条连接和%初等链。。与"，的一条链，若"。≠，则称该链为开链，否则称为闭链或回路或圈；如果在一个圈中所含的边均不相同，称此圈为简单圈；除起点和终点外链中所含的点均不相同的圈，叫做初等圈。在图8—5中，S={，，，e4，4，es，，2，]为一个圈。在图8—6中，S={y，es，es，4，es，）为一个圈，且为初等圈。定义9图中任意两点之间均至少有一条通路，则称此图为连通图，否则称为不连通图。任何一个不连通图都可以分为若干个连通子图，每一个称为原图的分图
内 容 在图 8—4 中（b）为（a）的子图，（c）为（a）的子图 在实际应用中，给定一个图 G=（V，E）或有向图 D=（V，A），在 V 中指定两个点， 一个称为始点（或发点），记作 v1 ，一个称为终点（或收点），记作 v n ，其余的点称为 中间点。对每一条弧 (vi ,v j ) A ，对应一个数 wi j ，称为弧上的“权”。通常把这种赋权 的图称为网络。 2、 连通图 定义 7 由两两相邻的点及其相关联的边构成的点边序列称为链。 如:v 0 ，,e1， v 1，,e2，v 2，e 3 ， v 3 ,.,v n-1 , e n ， v n，记作（ v 0 ， v 1 ， v 2， v 3 , ., v n-1 ， v n ）， 其链长为 n ，其中 v 0 ，v n分别称为链的起点和终点 。若链中所含的边均不相同，则称此 链为简单链；所含的点均不相同的链称为初等链 , 也称通路。 在图 8—5 中，S1 ={v 2 ，e4 ，v4 ，e 7 ，v5 ，e 7 ，v4 ，e 9 ，v6 }为一条链，起点 为 v 2 ，终点为 v6 ，链长为 4。 S2 ={v 2 ，e4 ，v4 ，e 7 ，v5 ，e 8 ，v4 ，e 9 ，v6 }为一条连接 v 2 和 v6 简单链。 S3 ={v 2 ，e4 ，v4 ， e 9 ，v6 }为一条连接 v 2 和 v6 初等链。 v 0 与 v n 的一条链，若 v 0 ≠ v n 则称该链为开链，否则称为闭链或回路或圈；如果 在一个圈中所含的边均不相同，称此圈为简单圈；除起点和终点外链中所含的点均不相同 的圈，叫做初等圈。 在图 8—5 中，S3 ={ v 1，,e 1 ，v 2 ，e4 ，v4 ， e5 ，v 3 ，e 2 ，v 1 }为一个圈。 在图 8—6 中，S ={ v 3，,e 6，v 5 ，e8 ，v4 ，e 5 ，v3 }为一个圈，且为初等圈。 定义 9 图中任意两点之间均至少有一条通路，则称此图为连通图，否则称为不连通 图。任何一个不连通图都可以分为若干个连通子图，每一个称为原图的分图。 e 3 v 1 v 2 v 3 v4 v5 e7 e8 v6 ,e 1 e 2 e4 e5 e6 e9 e10 图 8—5 e 3 e7 v e8 1 v 2 v 3 v4 v5 v6 ,e 1 e 2 e4 e5 e6 e9 e10 图 8—6
内容二、树1、树的概念和性质在各种各样的图中，有一类图是十分简单又非常具有应用价值，这就是树。例8.3已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。如果用六个点，…，代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就做成一个图。表示任意两个城市之间均可以V通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。图8一8是一个不含圈的连通图，代表了一个电话线网。图8—8定义13一个连通的无圈的无向图叫做树。树中次为1的点称为树叶，次大于1的点称为分支点。作为树T的定义，下列定义是等价的：（1）T是一个树。（设其顶点数为n，边数为m）(2）T无圈，且m=n-1。（3）T连通，且m=n-1。（4）T无圈，但在树中不相邻的两个点之间加上一条边，那么恰好得到一个圈。（5）T中任意两个顶点之间有且仅有一条链。（6）T连通，但去掉T的任一条边，T就不连通。由定理3很容易得出以下结论：从一个树中任意去掉一条边，那么剩下的图不是连通图，亦即，在点集合相同的图中，树是含边数最少的连通图。2、图的生成树定义14设图K=(V,E)是图G=(V,E)的一支撑子图，如果图K=(V,E)是一个V4(b)(a)图8—9
内 容 二、树 1、 树的概念和性质 在各种各样的图中，有一类图是十分简单又非常具有应用价值，这就是树。 例 8.3 已知有六个城市，它们之间 要架设电话线，要求任意两个城市均可以互相 通话，并且电话线的总长度最短。如果用六个点 v 1 ，.，v 6代表这六个城市，在任意两个 城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话 网就做成一个图。表示任意两个城市之间均可以 通话，这个图必须是连通图。并且，这个图必须 是无圈的。否则，从圈上任意去掉一条边，剩下 的图仍然是六个城市的一个电话网。图 8—8 是 一个不含圈的连通图，代表了一个电话线网。 定义 13 一个连通的无圈的无向图叫 做树。树中次为 1 的点称为树叶，次大于 1 的点称为分支点。 作为树 T 的定义，下列定义是等价的： （1）T 是一个树。（设其顶点数为 n ，边数为 m ） （2）T 无圈，且 m n 1。 （3）T 连通，且 m n 1。 （4）T 无圈，但在树中不相邻的两个点之间加上一条边，那么恰好得到一个圈。 （5）T 中任意两个顶点之间有且仅有一条链。 （6）T 连通，但去掉 T 的任一条边，T 就不连通。 由定理 3 很容易得出以下结论：从一个树中任意去掉一条边，那么剩下的图不是连通图， 亦即，在点集合相同的图中，树是含边数最少的连通图。 2、 图的生成树 定义 14 设图 ( , ) K V E1 是图 G=(V , E )的一支撑子图， 如果图 ( , ) K V E1 是一个 v 1 v 2 v 3 v 4 v 5 v 6 图 8—8 v 1 v 2 v 3 v 4 v 5 （a） v 1 v 2 v 3 v 4 v 5 （b） 图 8—9