第四部分图与网络分析（书第六部分） 图论是运筹学的一个分支，己广泛应用于物理学、化学、控制论、信息论、管理科学、电子计算机 等各个领域。在实际生活、生产和科学研究中，有很多问题可以用图论的理论和方法来解决。例如，在 组织生产中，为完成某项生产任务，各工序之间之间怎样衔接，才能使生产任务完成得又快有好。邮递 员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按怎样的路线走，所走的路线最短。 再例如，各种通信网络的合理架设，交通网络的合理分布等问题，应用图论的方法求解都很简便。 下面是著名的哥尼斯堡七桥问题（图见书P251)。当时那里的人民热衷于这样的问题：一个散步者 能否走过七座桥，并且每座桥只走过一次，最后回到出发点。 1736年欧拉将此问题归结为图形的一笔画问题（图见书P251):能否从某有点出发，不重复地一笔 画出此图形，最后回到出发点。欧拉证明了此图形是不可能一笔画的，因为只有每个点都与偶数条线关 联的图形才能一笔画。这是图论方面的第一篇论文。 第六章图与网络优化（书第10章) §6.1图的基本概念 在实际生活中，人们为了反映一些对象之间的关系，常常在纸上用点和线画出各种各样的示意图。 例如：铁路图，电话线分布图，比赛情况图。 例6.1.1某单位储存八种化学药品，其中某些药品是不能存放在一个库房的。为了反映这个情况， 可以用点，，g分别表示这八种药品，若药品不能与y放一起，则在与y之间画一条连线，如图 (书p252)。 可见，可以用由点和点与点之间的线所构成的图，反映实际生活种某些对象之间的某种特定的关系。 图：由点和连线组成，其中 点：表示研究的对象： 连线：表示两个对象之间的特定关系。 注6.1.1在一般情况下，图中点之间的相对位置，连线的长短曲直，对于反映对象之间的关系并 不重要。 6.1.1无向图 若图中反映的对象之间的关系具有对称性（即与y有关系，则y与也有关系），则这时的图称 为无向图，或简称图。对象之间的关系用不带箭头的连线表示，称为边。 无向图记作G=-(V,E),:点的集合，E:边的集合。连接点V,y,∈V的边记作e=[y,v,]或[y,]。 无向图G=(V,E)中点和边的个数分别记作p(G)和q(G)。 对无向图G=(V,E)(如图P253,10-7): 若边e=[y,y]∈E,则称y,v,是e的端点，V,V,相邻，e是，v,的关联边。 若e=[y,y]eE,则称e是环。 若两个点之间有多于一条的边，称这些边是多重边。 一个无环无多重边的图称为简单图：一个无环但有多重边的图称为多重图。以后说到无向图，若无 特别说明，均指简单图。 设v∈V,则v的关联边的个数称为v的次，记作dc(v),或简记d(v)。若d(v)=l,称v为悬挂点，1 第四部分 图与网络分析（书第六部分） 图论是运筹学的一个分支，已广泛应用于物理学、化学、控制论、信息论、管理科学、电子计算机 等各个领域。在实际生活、生产和科学研究中，有很多问题可以用图论的理论和方法来解决。例如，在 组织生产中，为完成某项生产任务，各工序之间之间怎样衔接，才能使生产任务完成得又快有好。邮递 员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按怎样的路线走，所走的路线最短。 再例如，各种通信网络的合理架设，交通网络的合理分布等问题，应用图论的方法求解都很简便。 下面是著名的哥尼斯堡七桥问题（图见书 P251）。当时那里的人民热衷于这样的问题：一个散步者 能否走过七座桥，并且每座桥只走过一次，最后回到出发点。 1736 年欧拉将此问题归结为图形的一笔画问题（图见书 P251）：能否从某有点出发，不重复地一笔 画出此图形，最后回到出发点。欧拉证明了此图形是不可能一笔画的，因为只有每个点都与偶数条线关 联的图形才能一笔画。这是图论方面的第一篇论文。 第六章 图与网络优化（书第 10 章） §6.1 图的基本概念 在实际生活中，人们为了反映一些对象之间的关系，常常在纸上用点和线画出各种各样的示意图。 例如：铁路图，电话线分布图，比赛情况图。 例 6.1.1 某单位储存八种化学药品，其中某些药品是不能存放在一个库房的。为了反映这个情况， 可以用点 v1,…, v8 分别表示这八种药品，若药品 vi 不能与 vj 放一起，则在 vi 与 vj 之间画一条连线，如图 （书 p252）。 可见，可以用由点和点与点之间的线所构成的图，反映实际生活种某些对象之间的某种特定的关系。 图：由点和连线组成，其中 点：表示研究的对象； 连线：表示两个对象之间的特定关系。 注 6.1.1 在一般情况下，图中点之间的相对位置，连线的长短曲直，对于反映对象之间的关系并 不重要。 6.1.1 无向图 若图中反映的对象之间的关系具有对称性（即 vi 与 vj 有关系，则 vj与 vi也有关系），则这时的图称 为无向图，或简称图。对象之间的关系用不带箭头的连线表示，称为边。 无向图记作 G=(V,E)，V：点的集合，E：边的集合。连接点 ,i j vv V∈ 的边记作 [, ] i j e vv = 或[,] j i v v 。 无向图 G=(V,E)中点和边的个数分别记作 p(G)和 q(G)。 对无向图 G=(V,E)（如图 P253,10-7）： 若边 [, ] i j e vv E = ∈ ，则称 ,i j v v 是 e 的端点， ,i j v v 相邻，e 是 ,i j v v 的关联边。 若 [,] i i e vv E = ∈ ，则称 e 是环。 若两个点之间有多于一条的边，称这些边是多重边。 一个无环无多重边的图称为简单图；一个无环但有多重边的图称为多重图。以后说到无向图，若无 特别说明，均指简单图。 设v V∈ ，则 v 的关联边的个数称为 v 的次，记作 ( ) G d v ，或简记 d v( ) 。若 d v( ) =1，称 v 为悬挂点