第五章图与网络

图论起源于1736年欧拉(Euler)的第一篇图论论文,解决了“哥尼斯堡的七桥问题”。图论是应用十分广泛的运筹学分支，它广泛地应用在物理学、化学、信息论、科学管理等领域。在实际生活中，许多问题可以用图论的理论与方法来解决，如在组织生产中，工序之间怎样衔接，才能使任务又快又好地完成等。

哥尼斯堡七桥问题：在哥尼斯堡的匹格河上有七座桥，见图5-1，如何不重复地走完七桥后回到起点？其中A、B表示两座岛屿，C、D表示河两岸。

第一节图的基本概念

在实际生活中，许多研究的对象往往可以用一个图表示，如公路、铁路图及管网图等，运筹学研究的图是上述各类图的抽象概括，表明研究对象之间的联系。通常用点表示研究对象,用点与点之间的线表示研究对象之间的特定关系。由于在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图、工程图等本质上是不同的。

图：由点和点与点之间的连线组成。若点与点之间的连线没有方向，称为边，由此构成的图为无向图，记为=(V，E)。V表示点的集合，E是边的集合。|V|=n表示点的个数，|E|=m表示边的条数。如果给图中的点及边赋以具体的含义和权数，如距离、费用、容量等，这样的图称为网络图。

图5-2中点用v表示，边用表示，对每一条边可用它所连接的点表示，如=[，]。

图5-2

端点、关联边、相邻：若有边可表示为=[，]，，是边的端点，称为点或的关联边，若与同一条边关联，称点与相邻，若与具有公共的端点，称边与相邻。

环、多重边、简单图：如果边的两个端点相同，则称边为环，如图5-1中边就是环，如果两个点之间有多于一条边，称为具有多重边，如，对于无环无多重边的图称为简单图。

次、奇点、偶点、孤立点：对某一个点相关联的边的数目称为点的次(也称为度)，记为d()，次为奇数的点称为奇点，次为偶数的点称为偶点，次为0的点称为孤立点，与次为1的点相连的边称为悬挂边。

链、圈、连通图：图中点、边的交错序列，若其中各边，，…，互不相同，且对任意的和均相邻，称为链，如果链中所有的端点，…，均不相同，这样的链称为初等连；若链中的起点与终点重合，则称为圈；若圈中的顶点不相同，则称为初等圈。若在一个图中，任意两点之间至少存在一条链，这样的图称为连通图，否则称为不连通的。

有向图、路：若图中点与点之间的连线是带箭头的，这样的图称为有向图，带箭头的连线称为弧，记为，其中V是点集合，A是弧集合。将D中弧上的箭头去点，得到一个无向图，称之为D的基础图。D中的链称为路，类似有回路，初等路。

子图、部分图(支撑子图)：图=(，)和图=(，)，如果有，称是的一个子图。若有，，则称是的部分图，注意部分图是子图，但子图不一定是部分图。

对要研究的问题确定具体对象及对象之间的性质联系，并用具体图的形式表示出来，这就是用图模型解决问题的思想，可以解决一些其他方法难于解决的问题。

【例5.1】有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛，表5-1带*表示各运动员报名参加的比赛项目，问六个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。

表5-1 各运动员报名参加的比赛项目

解：把比赛项目作为研究的对象，用点表示，如果两个项目没有同一名运动员参加，在代表项目之间的点连一条线，得到图5-3。在该图中只要找出一个点的序列，使一次排列的两个点相邻，即能做到每名运动员不连续参加两项比赛。从图中可以看出这样的点列只有一种：ACBFED。