第六章__图与网络.ppt

Chapter 1 第六章 图与网络Graph Theory Network Analysis 图论 Graph Theory 哥尼斯堡七桥问题 (K?nigsberg Bridge Problem) Leonhard Euler (1707-1783) 将此问题归结为一笔画问题，证明了这是不可能的，每个点都只与奇数条线相关联。 欧拉在1736年发表第一篇图论方面的论文，奠基了图论中的一些基本定理。 例1 下图是我国北京、上海等十个城市间的铁路交通图，反映了这十个城市间的铁路分布情况。这里用点代表城市，用点和点之间的连线代表这两个城市之间的铁路线。 例2 有甲、乙、丙、丁、戊五个球队，它们之间比赛的情况用图表示出来 已知甲队和其他各队都比赛过一次，乙队和甲、丙队比赛过，丙队和甲、乙、丁队比赛过，丁队和甲、丙、戊队比赛过，戊队和甲、丁队比赛过。为了反映这个情况，可以用点 分别代表这五个队，某两个队之间比赛过，就在这两个队所相应的点之间联一条线，这条线不过其他的点。 例3 某单位储存八种化学药品，其中某些药品是不能存放在同一个库房里的。用点 分别代表这八种药品，若药品vi和药品vj是不能存放在同一个库房的，则在vi和vj之间联一条线。 从这个图中可以看到，至少要有四个库房，因为 必须存放在不同的库房里。 事实上，四个库房就足够了。例如 各存放在一个库房里(这一类寻求库房的最少个数问题，属于图论中的所谓染色问题，一般情况下是尚未解决的)。 第一节 图的基本概念 图：由点及点与点的连线构成，反映了实际生活中某些对象之间的某些特定关系 点：代表研究的对象； 连线：表示两个对象之间特定的关系。 图：是反映对象之间关系的一种抽象 一般情况下，图中点的相对位置如何，点与点之间连线的长短曲直，对反映对象之间的关系并不重要。 关系的对称性和非对称性： 对象之间的“关系”具有“对称性”，就是说，如果甲与乙有这种关系，那么同时乙与甲也有这种关系。 实际生活中，有许多关系不具有这种对称性。 如例2，如果人们关心的是五个球队比赛的胜负情况，那么从原图中就看不出来了。为了反映这一类关系，可以用一条带箭头的连线表示。 边、弧、无向图、有向图 两点之间不带箭头的连线称为边，带箭头的连线称弧。 如果一个图G由点及边所构成，则称之为无向图(也简称为图)，记为G=(V, E) ，式中V，E分别是G的点集合和边集合。一条连结点 的边记为［ ］(或 ［ ］)。 如果一个图D由点及弧所构成，则称为有向图，记为D=(V，A)，式中V，A分别表示D的点集合和弧集合。一条方向是从vi指向vj的弧，记为( )。 图的重要概念 图G或D中的点数记为p(G)或p(D)，边(弧)数记为q(G)(q(D))，分别简记为p，q。 无向图G=(V，E)常用的一些名词和记号： 若边e =［u，v］∈E，则称u，v是e的端点，也称u，v是相邻的。称e是点u(及点v)的关联边。 若图G中，某个边e的两个端点相同，则称e是环。 若两个点之间有多于一条的边，称这些边为多重边。 一个无环，无多重边的图称为简单图；一个无环，但允许有多重边的图称为多重图。 以点v为端点的边的个数称v的次，记为dG(v)或d(v)。 称次为1的点为悬挂点，悬挂点的关连边称为悬挂边，次为零的点称为孤立点。 定理1 图G=(V，E)中，所有点的次之和是边数的两倍，即 若链 中，点 都是不同的，则称之为初等链；若 中， 都是不同的，则称之为初等圈。 若链(圈)中含的边均不相同，则称之为简单链（圈）。以后说到链(圈)，除非特别交代，均指初等链(圈)。 连通图 图G中，若任何两点之间至少有一条链，则称G是连通图，否则称为不连通图。 若G是不连通图，它的每个连通的部分称为G的一个连通分图(也简称分图)。 和有向图有关的概念和术语 设给定一个有向图，D=(V，A)，从D中去掉所有弧上的箭头，就得到一个无向图，称之为D的基础图，记之为G(D)。 给定D中的一条弧a=(u，v)，称u为a的始点，v为a的终点，称弧a是从u指向v的。 设 是D中的一个点弧交错序列，如果这个序列在基础图G(D)中所对应的点边序列是一条链，则称这个点弧交错序列是D的一条链。 如果