《运筹学课件 第八章 图与网络分析.ppt》由会员分享，可在线阅读，更多相关《运筹学课件 第八章 图与网络分析.ppt（67页珍藏版）》请在金锄头文库上搜索。
1、运筹学教程引言引言 图图论论是是专专门门研研究究图图的的理理论论的的一一门门数数学学分分支支，属属于于离离散散数数学学范范畴畴，与与运运筹筹学学有有交交叉叉，它它有有200多多年年历历史史，大大体体可可划划分分为为三三个个阶阶段段：第第一一阶阶段段是是从从十十八八世世纪纪中中叶叶到到十十九九世世纪纪中中叶叶，处处于于萌萌芽芽阶阶段段，多多数数问问题题围围游游戏戏而而产产生生，最最有有代代表表性性的的工工作作是是所所谓谓的的Euler七七桥桥问问题题，即即一笔画问题。一笔画问题。第八章第八章 图与网络分析图与网络分析运筹学教程第第二二阶阶段段是是从从十十九九世世纪纪中中叶叶到到二二十十世世纪纪中
2、中叶叶，这这时时，图图论论问问题题大大量量出出现现，如如Hamilton问问题题，地地图图染染色色的的四四色色问问题题以以及及可可平平面面性性问问题题等等，这这时时，也也出出现现用用图图解解决决实实际际问问题题，如如Cayley把把树树应应用用于于化化学领域，学领域，Kirchhoff用树去研究电网络等用树去研究电网络等.运筹学教程第第三三阶阶段段是是二二十十世世纪纪中中叶叶以以后后，由由生生产产管管理理、军军事事、交交通通、运运输输、计计算算机机网网络络等等方方面面提提出出实实际际问问题题，以以及及大大型型计计算算机机使使大大规规模模问问题题的的求求解解成成为为可可能能，特特别别是是以以Fo
3、rd和和Fulkerson建建立立的的网网络络流流理理论论，与与线线性性规规划划、动动态态规规划划等等优优化化理理论论和和方方法法相相互互渗渗透透，促促进进了了图图论论对对实际问题的应用。实际问题的应用。运筹学教程例：例：哥尼斯堡七桥问题哥尼斯堡七桥问题 哥哥尼尼斯斯堡堡（现现名名加加里里宁宁格格勒勒）是是欧欧洲洲一一个个城城市市，Pregei河河把把该该城城分分成成两两部部分分，河河中中有有两两个个小小岛岛，十十八八世世纪纪时时，河河两两边边及及小小岛岛之之间间共共有有七七座座桥桥，当当时时人人们们提提出出这这样样的的问问题题：有有没没有有办办法法从从某某处处（如如A）出出发发，经经过过各各
4、桥桥一次且仅一次最后回到原地呢？一次且仅一次最后回到原地呢？运筹学教程ABCD运筹学教程 最最后后，数数学学家家Euler在在1736年年巧巧妙妙地地给给出出了了这这个个问问题题的的答答案案，并并因因此此奠奠定定了了图图论论的的基基础础，Euler把把A、B、C、D四四块块陆陆地地分分别别收收缩缩成成四四个个顶顶点点，把把桥桥表表示示成成连连接接对对应应顶顶点点之之间间的的边边，问问题题转转化化为为从从任任意意一一点点出出发发，能能不不能能经经过过各各边边一一次次且且仅仅一一次次，最最后后返返回回该该点点。这这就是著名的就是著名的Euler问题。问题。运筹学教程ACBD运筹学教程例例：哈哈密密
5、顿顿（Hamilton）回回路路是是十十九九世世纪纪英英国国数数学学家家哈哈密密顿顿提提出出，给给出出一一个个正正12面面体体图图形形，共共有有20个个顶顶点点表表示示20个个城城市市，要要求求从从某某个个城城市市出出发发沿沿着着棱棱线线寻寻找找一一条条经经过过每每个个城城市市一一次次而而且且仅仅一一次次，最最后后回回到到原原处处的的周周游游世世界界线线路路（并并不不要要求求经过每条边）。经过每条边）。运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程运筹学教程 图的基本概念
6、图的基本概念 图论是专门研究图的理论的一图论是专门研究图的理论的一门数学分支，主要研究点和线之间的门数学分支，主要研究点和线之间的 几何关系。几何关系。运筹学教程一、图与网络的基本概念一、图与网络的基本概念一、图与网络的基本概念一、图与网络的基本概念1 1、图及其分类、图及其分类、图及其分类、图及其分类定义定义定义定义1 1：（图）一个图由点集：（图）一个图由点集：（图）一个图由点集：（图）一个图由点集V V和和和和V V中的元素无序对的一个中的元素无序对的一个中的元素无序对的一个中的元素无序对的一个集合，记为集合，记为集合，记为集合，记为 G=G=（V V，E E）其中：其中：其中：其中：V
7、= V= （ v v1 1， v v2 2，. . v vmm）是）是）是）是mm个顶点集合；个顶点集合；个顶点集合；个顶点集合； E= E= （ e e1 1， e e2 2，. e. en n） 是是是是n n条边集合。条边集合。条边集合。条边集合。当当当当V V和和和和E E为有限集合时，为有限集合时，为有限集合时，为有限集合时，GG为有限图。为有限图。为有限图。为有限图。2 2个点个点个点个点u,vu,v属于属于属于属于V V，如果边如果边如果边如果边(u,v)(u,v)属于属于属于属于E E， u,vu,v相邻相邻相邻相邻； u,vu,v为边为边为边为边(u,v)(u,v)的的的的端
8、点端点端点端点。具有公共端点具有公共端点具有公共端点具有公共端点u u的两条边，称为点的两条边，称为点的两条边，称为点的两条边，称为点u u的的的的关联边。关联边。关联边。关联边。第一节第一节 图与网络的基本知识图与网络的基本知识运筹学教程如果任一边如果任一边如果任一边如果任一边(u,v)(u,v)属于属于属于属于E E且端点无序，且端点无序，且端点无序，且端点无序，无向边无向边无向边无向边；图；图；图；图GG为为为为无向无向无向无向图。图。图。图。如果任一边如果任一边如果任一边如果任一边(u,v)(u,v)属于属于属于属于E E且端点有序，且端点有序，且端点有序，且端点有序，有向边有向边有向
9、边有向边；图；图；图；图GG为为为为有向有向有向有向图图图图m(Gm(G)= E )= E ，表示图表示图表示图表示图GG的边数；的边数；的边数；的边数；n(G)= V n(G)= V ，表示图表示图表示图表示图GG的点数；的点数；的点数；的点数；运筹学教程环（自回路）：一条边的两个端点如果相同。环（自回路）：一条边的两个端点如果相同。环（自回路）：一条边的两个端点如果相同。环（自回路）：一条边的两个端点如果相同。两个点之间多于一条边的，多重边。两个点之间多于一条边的，多重边。两个点之间多于一条边的，多重边。两个点之间多于一条边的，多重边。定义定义定义定义2 2：不含环和多重边的图，简单图。：
10、不含环和多重边的图，简单图。：不含环和多重边的图，简单图。：不含环和多重边的图，简单图。 含有多重边的图，多重图。含有多重边的图，多重图。含有多重边的图，多重图。含有多重边的图，多重图。有向图中的两点之间有不同方向的两条边，不是多重边。有向图中的两点之间有不同方向的两条边，不是多重边。有向图中的两点之间有不同方向的两条边，不是多重边。有向图中的两点之间有不同方向的两条边，不是多重边。简单图运筹学教程定义定义定义定义3 3：每一对顶点间都有边相连的无向简单图，完全图。每一对顶点间都有边相连的无向简单图，完全图。每一对顶点间都有边相连的无向简单图，完全图。每一对顶点间都有边相连的无向简单图，完全图
11、。有向完全图：指每一对顶点间有且仅有一条有向边的简单有向完全图：指每一对顶点间有且仅有一条有向边的简单有向完全图：指每一对顶点间有且仅有一条有向边的简单有向完全图：指每一对顶点间有且仅有一条有向边的简单图。图。图。图。定义定义定义定义4:4:图图图图G=(V,E)G=(V,E)的点集的点集的点集的点集V V可以分为可以分为可以分为可以分为2 2个非空子集个非空子集个非空子集个非空子集X,YX,Y，使得使得使得使得E E中每条边的两个端点必有一个端点属于中每条边的两个端点必有一个端点属于中每条边的两个端点必有一个端点属于中每条边的两个端点必有一个端点属于X X，另一个端点属另一个端点属另一个端点
12、属另一个端点属于于于于Y Y，GG为二部图（偶图），有时记为：为二部图（偶图），有时记为：为二部图（偶图），有时记为：为二部图（偶图），有时记为： G=(X,Y,E)G=(X,Y,E)V1V4V3V2XY运筹学教程 2 2、顶点的次、顶点的次 定义定义5 5：以点以点以点以点v v为端点的边的个数称为点为端点的边的个数称为点为端点的边的个数称为点为端点的边的个数称为点v v的次，记作的次，记作的次，记作的次，记作d(v)d(v), , , ,如次为零的点称为弧立点；如次为零的点称为弧立点；如次为零的点称为弧立点；如次为零的点称为弧立点；次为次为次为次为1 1 1 1的点称为悬挂点。悬挂点的边称
13、为悬挂边。的点称为悬挂点。悬挂点的边称为悬挂边。的点称为悬挂点。悬挂点的边称为悬挂边。的点称为悬挂点。悬挂点的边称为悬挂边。次为奇数的点称为奇点，次为偶数的点称为偶点。次为奇数的点称为奇点，次为偶数的点称为偶点。次为奇数的点称为奇点，次为偶数的点称为偶点。次为奇数的点称为奇点，次为偶数的点称为偶点。 偶点：偶点：偶点：偶点：d(d(v v) )= = = =偶数；偶数；偶数；偶数； 奇点：奇点：奇点：奇点：d d( (v v) )= = = =奇数；奇数；奇数；奇数；运筹学教程v1v1v3v3v2v2v4v4v6v6v5v5e1e1e3e3e5e5e6e6e4e4e8e8e7e7e2e2运筹学
14、教程V= V= （ v v1 1， v v2 2，. v. v6 6）E= E= （ e e1 1， e e2 2，. e. e8 8）（e e1 1）= = （v v1 1， v v2 2）（e e2 2）= = （v v1 1， v v2 2）（e e7 7）= = （v v3 3， v v5 5）（e e8 8）= = （v v4 4， v v4 4） (e(e8 8)= (v)= (v4 4， v v4 4), ),称为自回路称为自回路称为自回路称为自回路( (环环环环) )；v v6 6是孤立点，是孤立点，是孤立点，是孤立点，v v5 5为悬挂点，为悬挂点，为悬挂点，为悬挂点，e e
15、7 7为悬挂边，顶点为悬挂边，顶点为悬挂边，顶点为悬挂边，顶点v v3 3的次为的次为的次为的次为4 4，顶点，顶点，顶点，顶点v v4 4的次为的次为的次为的次为4 4。运筹学教程定理定理定理定理1 1 在一个图中，所有顶点次的和等于边的两倍。在一个图中，所有顶点次的和等于边的两倍。在一个图中，所有顶点次的和等于边的两倍。在一个图中，所有顶点次的和等于边的两倍。定理定理定理定理2 2 在任意一个图中，次为奇数的顶点必为偶数在任意一个图中，次为奇数的顶点必为偶数在任意一个图中，次为奇数的顶点必为偶数在任意一个图中，次为奇数的顶点必为偶数个。个。个。个。定义定义定义定义6 6：有向图中，以：有向
16、图中，以：有向图中，以：有向图中，以v vi i为始点的边数称为点为始点的边数称为点为始点的边数称为点为始点的边数称为点v vi i的的的的出出出出次，次，次，次，d d+ +(v(vi i); ); 以以以以v vi i为为为为终点的边数称为点终点的边数称为点终点的边数称为点终点的边数称为点v vi i的的的的入次，入次，入次，入次，d d- -(v(vi i); );所有顶点的入次之和所有顶点的入次之和所有顶点的入次之和所有顶点的入次之和= =所有顶点的出次之和；所有顶点的出次之和；所有顶点的出次之和；所有顶点的出次之和；运筹学教程3 3、子图、子图、子图、子图定义定义定义定义：设：设：设
17、：设G=G=（V V，E E）和）和）和）和GG1 1= =（V V1 1，E E1 1）。）。）。）。 如果如果如果如果V V1 1 V V， E E1 1 E E则称则称则称则称GG1 1为为为为GG的子图；的子图；的子图；的子图； 如果如果如果如果GG1 1 = =（ V V1 1，E E1 1 ）是）是）是）是G=G=（V V，E E）子图，子图，子图，子图，并且并且并且并且V V1 1 = = V V，则称则称则称则称GG1 1为为为为GG的生成子图；的生成子图；的生成子图；的生成子图；运筹学教程v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4
18、e3e3e2e2运筹学教程v1v1v5v5v4v4v2v2e1e1e5e5e3e3（a a）的子图的子图的子图的子图运筹学教程v1v1v5v5v4v4v2v2v3v3e8e8e6e6e5e5e2e2（a a）的生的生的生的生成子图成子图成子图成子图运筹学教程二、连通图二、连通图二、连通图二、连通图定义定义定义定义8:8:如果图中的某些点、边可以排列成点和边的交错序列如果图中的某些点、边可以排列成点和边的交错序列如果图中的某些点、边可以排列成点和边的交错序列如果图中的某些点、边可以排列成点和边的交错序列( (v v0 0 ,e ,e1 1 ,v ,v1 1 ,e ,e2 2 ,v ,v2 2，e
19、 e3 3 ,v ,v3 3 ,v,vn-1 n-1 , e, en n ， v vn n ） ，e ei i=(v=(vi-1i-1,v ,vi i) )，则称此为一条链。则称此为一条链。则称此为一条链。则称此为一条链。由两两相邻的点及其相关联边构成的点边序列。由两两相邻的点及其相关联边构成的点边序列。由两两相邻的点及其相关联边构成的点边序列。由两两相邻的点及其相关联边构成的点边序列。初等链：初等链：链中无重复的点和边；链中无重复的点和边；定义定义定义定义9 9：无向图中，如一条链中起点和终点重合，则称此链为无向图中，如一条链中起点和终点重合，则称此链为无向图中，如一条链中起点和终点重合，则
20、称此链为无向图中，如一条链中起点和终点重合，则称此链为圈。圈。圈。圈。初等圈：圈初等圈：圈中无重复的点和边；中无重复的点和边；有向图中，当有向图中，当有向图中，当有向图中，当链（圈）链（圈）链（圈）链（圈）上的边方向相同时，为上的边方向相同时，为上的边方向相同时，为上的边方向相同时，为道路（回路）道路（回路）道路（回路）道路（回路）。运筹学教程道路道路道路道路回路回路链链初等链初等链初等圈初等圈链、初等链、初等圈链、初等链、初等圈链、初等链、初等圈链、初等链、初等圈道路、回路道路、回路运筹学教程连通图：连通图：图中任意两点之间均至少有一图中任意两点之间均至少有一条通路，否则称为不连通图。条通路
21、，否则称为不连通图。运筹学教程v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2有向图有向图有向图有向图运筹学教程v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2有向图有向图有向图有向图运筹学教程v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2有向图有向图有向图有向图运筹学教程v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2有向图有向图有向图有向图运筹学教程v1v1v5v5v
22、4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2有向图有向图有向图有向图运筹学教程v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2有向图有向图有向图有向图运筹学教程v1v1v5v5v4v4v2v2v3v3e1e1e8e8e7e7e6e6e5e5e4e4e3e3e2e2链链链链运筹学教程v1v1v5v5v4v4v2v2e1e1e7e7e6e6e3e3运筹学教程v1v1v5v5v4v4v2v2e1e1e7e7e6e6e3e3运筹学教程v1v1v5v5v4v4v2v2e1e1e7e7e6e6e3e3运筹学教
23、程v1v1v5v5v4v4v2v2e1e1e7e7e6e6e3e3圈圈圈圈运筹学教程三、图的矩阵表示三、图的矩阵表示三、图的矩阵表示三、图的矩阵表示 一个图非常直观，但是不容易计算，特一个图非常直观，但是不容易计算，特一个图非常直观，但是不容易计算，特一个图非常直观，但是不容易计算，特别不容易在计算机上进行计算，一个有效的别不容易在计算机上进行计算，一个有效的别不容易在计算机上进行计算，一个有效的别不容易在计算机上进行计算，一个有效的解决办法是将图表示成矩阵形式，通常采用解决办法是将图表示成矩阵形式，通常采用解决办法是将图表示成矩阵形式，通常采用解决办法是将图表示成矩阵形式，通常采用的矩阵是邻
24、接矩阵、边长邻接矩阵、弧长矩的矩阵是邻接矩阵、边长邻接矩阵、弧长矩的矩阵是邻接矩阵、边长邻接矩阵、弧长矩的矩阵是邻接矩阵、边长邻接矩阵、弧长矩阵和关联矩阵。阵和关联矩阵。阵和关联矩阵。阵和关联矩阵。1 1、邻接矩阵、邻接矩阵、邻接矩阵、邻接矩阵 邻接矩阵邻接矩阵邻接矩阵邻接矩阵A A表示图表示图表示图表示图GG的顶点之间的邻接关系，的顶点之间的邻接关系，的顶点之间的邻接关系，的顶点之间的邻接关系，它是一个它是一个它是一个它是一个nxnnxn的矩阵，如果两个顶点之间有边相的矩阵，如果两个顶点之间有边相的矩阵，如果两个顶点之间有边相的矩阵，如果两个顶点之间有边相联时，记为联时，记为联时，记为联时，
25、记为1 1，否则为，否则为，否则为，否则为0 0。运筹学教程定义定义定义定义1212：对于对于对于对于G=(V,E)G=(V,E)，构造矩阵构造矩阵构造矩阵构造矩阵A=(A=(a aij ij) )nxnnxna aij= ij= 1 1, , （vi,vjvi,vj） E E 0 0矩阵矩阵矩阵矩阵A A为邻接矩阵。为邻接矩阵。为邻接矩阵。为邻接矩阵。运筹学教程V1V3V5V6V4V2v1 v2 v3 v4 v5 v6运筹学教程2 2、权矩阵、权矩阵、权矩阵、权矩阵 在图的各边上一个数量指标，具体表示这条边在图的各边上一个数量指标，具体表示这条边在图的各边上一个数量指标，具体表示这条边在图的
26、各边上一个数量指标，具体表示这条边的权（距离，单价，通过能力等），以边长代替邻的权（距离，单价，通过能力等），以边长代替邻的权（距离，单价，通过能力等），以边长代替邻的权（距离，单价，通过能力等），以边长代替邻接矩阵中的元素得到边长邻接矩阵。接矩阵中的元素得到边长邻接矩阵。接矩阵中的元素得到边长邻接矩阵。接矩阵中的元素得到边长邻接矩阵。定义定义定义定义1111：赋权图赋权图赋权图赋权图G=(V,E)G=(V,E)，其边（其边（其边（其边（vi,vjvi,vj）有权有权有权有权w wij ij, ,构构构构造矩阵造矩阵造矩阵造矩阵A=(A=(a aij ij) )nxnnxna aij= ij=
27、 w wij ij, , （vi,vjvi,vj） E E 0 0矩阵矩阵矩阵矩阵A A为权矩阵。为权矩阵。为权矩阵。为权矩阵。运筹学教程v1v2v5v4v3924386745 v1 v2 v3 v4 v5运筹学教程四、欧拉回路与中国邮政问题四、欧拉回路与中国邮政问题四、欧拉回路与中国邮政问题四、欧拉回路与中国邮政问题1 1、欧拉回路与道路、欧拉回路与道路、欧拉回路与道路、欧拉回路与道路定义定义定义定义1313：连通图连通图连通图连通图GG，如果存在一条道路，经过每边一次且仅如果存在一条道路，经过每边一次且仅如果存在一条道路，经过每边一次且仅如果存在一条道路，经过每边一次且仅一次，则称这条路为
28、欧拉道路；一次，则称这条路为欧拉道路；一次，则称这条路为欧拉道路；一次，则称这条路为欧拉道路；如果存在一条回路，经过每边一次且仅一次，则称这条路为如果存在一条回路，经过每边一次且仅一次，则称这条路为如果存在一条回路，经过每边一次且仅一次，则称这条路为如果存在一条回路，经过每边一次且仅一次，则称这条路为欧拉回路；欧拉回路；欧拉回路；欧拉回路；具有欧拉回路的图为欧拉图。具有欧拉回路的图为欧拉图。具有欧拉回路的图为欧拉图。具有欧拉回路的图为欧拉图。定理定理定理定理3 3：无向连接图无向连接图无向连接图无向连接图GG是欧拉图，当且仅当是欧拉图，当且仅当是欧拉图，当且仅当是欧拉图，当且仅当GG中无奇中无
29、奇中无奇中无奇 点。点。点。点。推论推论推论推论1 1：无向连接图无向连接图无向连接图无向连接图GG为为为为欧拉图，当且仅当欧拉图，当且仅当欧拉图，当且仅当欧拉图，当且仅当GG的的的的边集可划为若边集可划为若边集可划为若边集可划为若干个初等回路。干个初等回路。干个初等回路。干个初等回路。推论推论推论推论2 2：无向连接图无向连接图无向连接图无向连接图GG为欧拉道路，当且仅当为欧拉道路，当且仅当为欧拉道路，当且仅当为欧拉道路，当且仅当GG恰好有恰好有恰好有恰好有2 2个奇个奇个奇个奇点。点。点。点。运筹学教程定理定理定理定理4 4：连通有向图连通有向图连通有向图连通有向图GG是欧拉图，当且仅当它
30、每个奇点的出次等是欧拉图，当且仅当它每个奇点的出次等是欧拉图，当且仅当它每个奇点的出次等是欧拉图，当且仅当它每个奇点的出次等于入次。于入次。于入次。于入次。2 2、中国邮路问题、中国邮路问题、中国邮路问题、中国邮路问题一个邮递员，从邮局出发，走遍所有街道后回到邮局，如何安一个邮递员，从邮局出发，走遍所有街道后回到邮局，如何安一个邮递员，从邮局出发，走遍所有街道后回到邮局，如何安一个邮递员，从邮局出发，走遍所有街道后回到邮局，如何安排，使其总的路程最短？排，使其总的路程最短？排，使其总的路程最短？排，使其总的路程最短？图论：给定一个连通图，每边有非负权，要求一条回路过每边图论：给定一个连通图，每
31、边有非负权，要求一条回路过每边图论：给定一个连通图，每边有非负权，要求一条回路过每边图论：给定一个连通图，每边有非负权，要求一条回路过每边至少一次，且满足总权最小。至少一次，且满足总权最小。至少一次，且满足总权最小。至少一次，且满足总权最小。定理定理定理定理5 5：已知图：已知图：已知图：已知图G*=G+EG*=G+E1 1无奇点，则无奇点，则无奇点，则无奇点，则L(EL(E1 1)= l(e)= l(e)最小的充要条件最小的充要条件最小的充要条件最小的充要条件（1 1）每条边最多重复一次；）每条边最多重复一次；）每条边最多重复一次；）每条边最多重复一次；（2 2）对图）对图）对图）对图GG中
32、每个初等圈，重复边的长度和不超过圈长的中每个初等圈，重复边的长度和不超过圈长的中每个初等圈，重复边的长度和不超过圈长的中每个初等圈，重复边的长度和不超过圈长的1/21/2；运筹学教程例：求解网络的中国邮路问题例：求解网络的中国邮路问题例：求解网络的中国邮路问题例：求解网络的中国邮路问题v1v3v6v9v8v7v4v5v2第一步：确定初始可行方案第一步：确定初始可行方案第一步：确定初始可行方案第一步：确定初始可行方案先检查图中是否有奇点，如果无奇点，为欧拉图；如果先检查图中是否有奇点，如果无奇点，为欧拉图；如果先检查图中是否有奇点，如果无奇点，为欧拉图；如果先检查图中是否有奇点，如果无奇点，为欧
33、拉图；如果有奇点，图中的奇点的个数比为偶数个，所以可以两两有奇点，图中的奇点的个数比为偶数个，所以可以两两有奇点，图中的奇点的个数比为偶数个，所以可以两两有奇点，图中的奇点的个数比为偶数个，所以可以两两配对，构造二重边。图中有配对，构造二重边。图中有配对，构造二重边。图中有配对，构造二重边。图中有4 4个奇点，个奇点，个奇点，个奇点，v2,v4,v6,v8,v2,v4,v6,v8,配对配对配对配对 v2-v4,v6-v8v2-v4,v6-v8，构造二重边。重复边构造二重边。重复边构造二重边。重复边构造二重边。重复边 的总长：的总长：的总长：的总长：2 2l l2323+ 2+ 2l l3636
34、+ + l l6969+ + l l9898+ + l l2323+ 2+ 2l l8787+ 2+ 2l l7474+ + l l4141+ + l l1212=51=51v1v3v6v9v8v7v4v5v2343449545642343449545642运筹学教程第二步：调整可行方案，使重复边最多为一次第二步：调整可行方案，使重复边最多为一次第二步：调整可行方案，使重复边最多为一次第二步：调整可行方案，使重复边最多为一次重复边重复边重复边重复边 的总长：的总长：的总长：的总长：l l6969+ + l l9898+ + l l4141+ + l l1212=21=21第三步：检查每个初等圈
35、是否第三步：检查每个初等圈是否第三步：检查每个初等圈是否第三步：检查每个初等圈是否定理条件定理条件定理条件定理条件2 2，如果不满足，进行，如果不满足，进行，如果不满足，进行，如果不满足，进行调整，直至满足为止。调整，直至满足为止。调整，直至满足为止。调整，直至满足为止。圈圈圈圈v1v2v5v4v1v1v2v5v4v1总长度总长度总长度总长度2424，重复边，重复边，重复边，重复边1414，14/2114/21大于大于大于大于1/21/2，调整调整调整调整（v2,v5v2,v5），（），（），（），（v5,v4v5,v4）代替（代替（代替（代替（v1,v2v1,v2），），），），(v1,v4
36、)(v1,v4)v1v3v6v9v8v7v4v5v2圈圈圈圈v1v2v5v4v1v1v2v5v4v1总长度总长度总长度总长度2424，重复边重复边重复边重复边6+4=106+4=10v1v3v6v9v8v7v4v5v2343449545642运筹学教程重复边重复边重复边重复边 的总长：的总长：的总长：的总长：l l6969+ + l l9898+ + l l4545+ + l l5252=17=17再再再再检查圈检查圈检查圈检查圈v2v3v6v9v8v5v2v2v3v6v9v8v5v2总长总长总长总长=24,=24,重复边重复边重复边重复边 的长的长的长的长度度度度1313，继续调整，继续调整
37、，继续调整，继续调整v1v3v6v9v8v7v4v5v2再次调整的重复边重复边重复边重复边 的总长：的总长：的总长：的总长：=15=15，满足条件要求。，满足条件要求。，满足条件要求。，满足条件要求。图中任一欧拉回路为最优邮递回路。图中任一欧拉回路为最优邮递回路。图中任一欧拉回路为最优邮递回路。图中任一欧拉回路为最优邮递回路。方法：简单；但要检查每一个初等圈。方法：简单；但要检查每一个初等圈。方法：简单；但要检查每一个初等圈。方法：简单；但要检查每一个初等圈。v1v3v6v9v8v7v4v5v26434524运筹学教程总结总结: :图的基本概念图的基本概念G=G=（V V，E E）子图子图矩阵
38、表示矩阵表示含含元素的个数元素的个数点的次点的次边边特殊的图特殊的图点边关系点边关系简简单单图图多多重重图图连通图连通图树树生成子图生成子图G=(V,E) 矩阵表示矩阵表示矩阵表示矩阵表示A A 邻接矩阵邻接矩阵B B 权矩阵权矩阵边边e=(u,v) 关联边关联边 端点端点 重重重重合合合合环环自回路自回路自回路自回路多重边多重边 平行边平行边平行边平行边多于多于1条边条边简单图简单图不含不含不含不含多重图多重图含含含含点的次点的次点的次点的次 0 1 奇数奇数 偶数偶数 子图子图孤孤立立点点悬悬挂挂点点奇奇点点偶偶点点悬挂边悬挂边顶点数顶点数n边数边数m点边关系点边关系各种链的概念各种链的概念子子图图生成生成子图子图初等链（无重复边、无重复点的链)链、圈（即起点与终点同）点边交替序列序列各种链的概念 （无向图）初等圈（无重复边、无重复点的圈)连通图连通图 点边关系点边关系各种链的概念各种链的概念通路通路生成树生成树子子图图生成生成子图子图有向图道路、回路经过每边一次且仅一次欧拉道路欧拉回路运筹学教程1.思考题思考题子图与生成子图的区别是什么？子图与生成子图的区别是什么？2.讨论题讨论题中国邮路问题的解题步骤？中国邮路问题的解题步骤？运筹学教程小结:1.图的基本知识。2.图的矩阵表示。3.欧拉道路与欧拉回路。
