离散数学 图论.doc

122 第六章第六章 图论基础图论基础 图是建立和处理离散数学模型的一种重要工具 图论是一门应用性很强的学科 许多 学科 诸如运筹学 网络理论 控制论 化学 生物学 物理学 社会科学 计算机科学 等 凡是研究事物之间关系的实际问题或理论问题 都可以建立图论模型来解决 随着计 算机科学的发展 图论的应用也越来越广泛 同时图论也得到了充分的发展 这里将主要 介绍与计算机科学关系密切的图论的内容 6 1 图的基本概念 我们已知集合的笛卡尔积的概念 为了定义无向图 还需要给出集合的无序积的概念 任意两个元素 a b 构成的无序对无序对 Unordered pair 记作 a b 这里总有 abba 设为两个集合 无序对的集合称为集合 A 与 B 的无序积无序积BA BbAaba Unordered Product 记作 无序积与有序积的不同在于 BA若 称与关联的次数关联的次数为 2 若不是的端点 则称与的关联次数关联次数为vu euueeu 0 或称 e 与 u 不关联不关联 在图 6 1 3 中 是的端点 与 的 211 vve 1 v 2 v 1 e 1 e 1 v 2 v 关联次数均为 1 是孤立点 是环 与关联的次数为 2 5 v 2 e 2 e 2 v 当是有向边时 又称是的始点始点 Initial Point 是的终点终点 Terminal vue ueve Point 如果图的结点集和边集都是有限集 则称图为有限图有限图 Finite graph 本书讨论的VE 图都是有限图 若图中 为了方便起见 这样的图也称为 EVG nV mE 图图 有时也简称阶图阶图 这时图称为零图零图 Null Graph 图称为平平 mn n 0 n 0 1 凡图凡图 Trivial Graph 关联于同一对顶点的两条边称为平行边平行边 Parallel Edge 若是有向边方向应相同 平 行边的条数称为边的重数边的重数 不含平行边和环的图称简单图简单图 Simple Graph 在本书中除非特 别声明 一般是指简单图 6 1 2 结点的度结点的度 定义定义 6 1 3 设为一无向图 关联边的次数称为 v 的度数度数 简称 EVG Vv v 度度 Degree 记作的 d v 设为一有向图 v 作为边的始点的次数 称为 v 的出度出度 Out EVG Vv Degree 记作 v 作为边的终点的次数称为 v 的入度入度 In Degree 记作 v 作 vd vd 为边的端点的次数称为 v 的度数度数 简称度度 Degree 记作 显然 vd vdvdvd 在图 6 1 3 中 3 1 vd4 2 vd1 4 vd0 5 vd 在图 6 1 4 中 2 1 vd1 1 vd 0 4 vd0 4 vd2 22 vdvd 称度为 1 的结点为悬挂点悬挂点 Hanging point 与悬挂点关联的边称为悬挂边悬挂边 Hanging edge 如图 6 1 3 中 是悬挂点 是悬挂边 4 v 6 e 记 分别称为图的最大最大 max GVvvdG min GVvvdG G 度度 Max Degree 和最小度最小度 Min Degree 若是有向图 除了 还 EVG G G 有如下的定义 最大出度最大出度 VvvdG max 125 最大入度最大入度 VvvdG max 最小出度最小出度 VvvdG min 最小入度最小入度 VvvdG min 图 6 1 4 中 4 G2 G 2 G0 G 2 G1 G 例例 6 1 2 在图 6 1 3 中 而该图有 条边 1201443 54321 vdvdvdvdvdvd Vv 即结点度数和是边数的 倍 事实上这是图的一般性质 定理定理 6 1 1 设图为具有结点集的图 则 G 21n vvv mn mvd n i i 2 1 若为奇数 则称为奇点奇点 若为偶数 则称为偶点偶点 vdv vdv 推论推论 任一图中 奇点个数为偶数 证明证明 设 1 为奇点vvV 2 为偶点vvV 则 因为是偶数 所以也是偶数 而mvdvdvd VvVvVv 2 21 2 Vv vd 1 Vv vd 中每个点的度均为奇数 因此为偶数 1 Vv vd 1 V 对有向图 还有下面的定理 定理定理 6 1 2 设有向图 EVG 21n vvvv mE 则 mvdvd n i i n i i 11 以上两个定理及推论都很重要 要牢记并灵活运用 设是图的结点集 称为的度序列 如图 21n vvvv G 21n vdvdvdG 6 1 3 的度序列为 图 6 1 4 的度序列是 0 1 4 4 32 3 4 3 例例 6 1 3 图的度序列为 则边数是多少 G4 3 3 2 2m 能成为图的度序列吗 为什么 3 2 3 34 1 3 2 5 图有 12 条边 度数为 的结点有 个 其余结点度均小于 问图中至少GG 有几个结点 126 解解 由握手定理 所以 1443322 2 Vv vdm7 m 由于这两个序列中有奇数个是奇数 由握手定理的推论知 它们都不能成为图的 度序列 由握手定理 度数为 的结点有 个占去 18 度 还有 度由242 mvd 其余结点占有 其余结点的度数可为 当均为 时所用结点数最少 所以应由 个结2 1 0 点占有这 度 即图中至少有 个结点 G 例例 6 1 4 证明在个人的集体中 总有两个人在此团体中恰有相同个数的朋友 2 nn 解解 以结点代表人 二人如果是朋友 则在代表他们的结点间连上一条边 这样可 得无向简单图 每个人的朋友数即是图中代表他的结点的度数 于是问题转化为 阶Gn 无向简单图必有两个结点的度数相同 G 用反证法 设中每个结点的度数均不相同 则度序列为 说明图中G1 2 1 0 n 有孤立点 而图是简单图 这与图中有度结点相矛盾 所以必有两个结点的度数G1 n 相同 6 1 3 完全图和补图完全图和补图 定义定义 6 1 4 设是无向简单图 若每一对结点之间都有边相连 则称 EVG 为完全图完全图 Complete Graph 具有个结点完全图记作 Gn n K 设为有向简单图 若每对结点间均有一对方向相反的边相连 则称为 EVG G 有向有向 完全图完全图 具有个结点的有向完全图记作 n n D 例例 6 1 5 图 6 1 5 给出几个完全图的例子 由完全图的定义可知 无向完全图的边数为 而有向完全图的 n K 1 2 1 nnKE n 边数为 1 nnDE n 127 1 K 图 6 1 5 2 K 3 K 4 K 5 K 1 D 2 D 3 D 4 D 定义定义 6 1 5 设为阶 无向 简单图 从 n 阶完全图中删去的所有边后构成的Gn n KG 图称为的补图补图 Complement of graph 记作 类似地 可定义有向图的补图 GG 例例 6 1 6 图 6 1 6 中是的补图 GG 由补图的定义 显然有如下的结论 与互为补图 即 GGGG 若为阶图 则 且 Gn n KEGEGE GEGE 定义定义 6 1 6 各结点的度数均为的无向简单图称为 k 正则图正则图 Regular graph k 图 6 1 7 所示的图称为彼得森彼得森 Petersen 图图 是正则图 3 1 v 2 v 3 v 5 v 4 v GG 图 6 1 6 图 6 1 7 6 1 4 子图与图的同构子图与图的同构 定义定义 6 1 7 设 是两个图 若 且 则 EVG EVGVV EE 称是的子图子图 Subgraph 是的母图母图 Contained graph 记作 G GG G GG 若或 则称是的真子图真子图 Proper subgraph VV EE G G 128 若且 则称是的生成子图生成子图 Spanning subgraph VV EE G G 若且 以为结点集 以图中两个端点均在中的边为边集的子图 VV 1 1 V 1 VG 1 V 称为由 V1导出的导出子图导出子图 Induced subgraph 记作 1 VG 设 且 以为边集 以中的边关联的结点为结点集的图的子EE 1 1 E 1 E 1 EG 图 称为导出的边导出子图边导出子图 记作 1 E 1 EG f 1 G 1 e 2 e 4 e 5 e b a c d 1 e 2 e 3 e 4 e 5 e 6 e 7 e 8 e G b a c d f 图 6 1 8 2 G 1 e 2 e 4 e 5 e 6 e b a c f 3 G 2 e 3 e 4 e a cd f 例例 6 1 7 在图 6 1 8 中 均是的真子图 其中是的生成子图 321 GGGG 1 GG 是由导出的导出子图 是由导出的边导出 2 G 2 fcbaV 2 VG 3 G 4323 eeeE 子图 3 EG 由于在画图的图形时 结点的位置和边的几何形状是无关紧要的 因此表面上完全不 同的图形可能表示的是同一个图 为了判断不同图形是否表示同一个图形 在此我们给出 图的同构的概念 设有两个图 如果存在双射 使得 EVG 111 EVG 1 VVh 当且仅当 或者当且仅当Evu 1 Evfuf Evu vfuf 且它们的重数相同 则称图 G 与 G1同构同构 Isomorphism 记作 1 E 1 GG 定义 6 1 8 说明 两个图的结点之间 如果存在双射 而且这种映射保持了结点间的 邻接关系和边的重数 在有向图时还保持方向 则两个图是同构的 例例 6 1 8 图 6 1 9 中 其中 21 GG 21 VVf 6 2 1 iuvf ii43 GG 3 v 1 G 6 v 5 v 4 v 2 v 1 v 2 G 1 u 2 u 3 u 4 u 5 u 6 u 图6 1 9 4 v 3 v 2 v 1 v 3 G 1 u 2 u 4 u 4 G 3 u 129 其中 43 VVh 31 uvh 42 uvh 13 uvh 24 uvh 容易看出 两个图同构的必要条件是 结点数相同 边数相同 度序列相同 但这不是充分的条件 例如图 6 1 10 中图虽然满足以上 3 个条件 但不同构 图中的 4 个 3 度结点与中的 4 个 21 H H 1 H 2 H 3 度结点的相互间的邻接关系显然不相同 习题习题 6 1 6 1 1 画出下列各图的图形并求出各结点的度 出度 入度 edcbaVEVG 其中 cbabdacabaE eddd cabaEedcbaVEVH中中 ea edddadcb 6 1 2 下列各组数中 哪些能构成无向图的度序列 哪些能构成无向简单图的度序列 1 1 1 2 3 2 2 2 2 2 3 3 3 3 1 2 3 4 5 1 3 3 3 h g b i f c d a e j 1 G 63 12 5 10 8 9 4 7 2 G 图 6 1 11 6 1 3 设图若 G 有三个 3 度结点 两个 2 度结点 三个 1 度结点 8 VEVG 试问 G 有多少条边 6 1 4 图 G 有 12 条边 三个度为 4 的结点 其余结点的度均为 3 问图 G 有多少个结 图 6 1 10 H1H2 b cd e a 1 G 1 4 23 5 2 G 图 6 1 12 130 点 6 1 5 图 6 1 11 中与同构吗 若两图同构 写出结点之间的对应关系 若不同 1 G 2 G 构 则说明理由 6 1 6 图 6 1 12 中 G1与 G2 同构吗 为什么 6 2 图的连通性图的连通性 计算机网络中常见的一个问题是 网络中任何两台计算机是否可以通过计算机间的信 息传递而使其资源共享 我们可以用图论的方法对这个问题进行研究 其中用结点表示计 算机 用边表示通讯连线 因此 计算机的信息资源共享问题就变为 图中任何两个结点 之间是否都有连接通路存在 6 2 1 通路通路 在图论的研究中 经常要考虑这样的问题 如何从一个图中的给定结点出发 沿着一 些边移动到另一个结点 这种由结点和边形成的序列就引出了路的概念 定义定义 6 2 1 设是图 从图中结点到的一条通路通路或路径路径 walk 是图 EVG 0 v n v 的一个点 边的交错序列 其中 或者 122110nnn vevvevev 1iii vve iii vve 1 分别称为通路的起点起点 Initial Point 和终点终点 Terminal Point 而称 2 1 ni 0 v n v 为内点内点 Interior point 通路中包含的边数 n 称 121 n vvv 为通路的长度长度 Length 当起点和终点重合时则称其为回路回路 Circuit 若通路的边互不相同 则称其为链链 Chain n eee 21 如果一条链满足 则称其为闭链闭链 n vv 0 如果一条通路中结点互不相同 则称 n vvvv 210 其为道路道路 简称路路 Path 如果一条回路的起点和内部结点互不相同 则称其为 圈圈 Cycle 一般地称长度为 k 的圈为 k 圈圈 并称长度为 奇数的圈为奇圈奇圈 长度为偶数的圈为偶圈偶圈 例例 6 2 1 在图 6 2 1 中 是一条通路 也是一条链 2116455411 vevevevevp 是一回路 也是一闭链 4833222742 vevevevevp 是一条路 33211643 vevevevp 是一圈 4833211644 vevevevevp 在不引起混淆的情况下 通路有时也可用边的序列或结点的序列来表示 如上例中的 可记为 和 特别地 单独一个结点也是一个通路 其 3 p 4 p 3214 vvvv 43214 vvvvv 3 e 1 v 2 v 3 v 4 v 5 v 4 e 5 e 6 e 1 e 7 e 8 e 图 6 2 1 2 e 131 长度为 0 另外 由平行边和构成的通路及由一个环构成的通路均是回 1 e 2 euveue 21 ueu 路 定理定理 6 2 1 在一个 n 阶图中 如果从结点到存在一条通 EVG i v j v ji vv 路 则从到存在一条长度不大于的路 i v j v1 n 证证 假定从到存在一条通路 如果其中有相同的结点 例如 i v j v jki vvv e v 删去到的那些边 它仍是从到的通路 如此反复 jeeki vvvvv e v e v i v j v 的进行直到中没有重复结点为止 此时所得就是一条从到的路 路 jki vvv i v j v 的长度比所经结点数少 1 图中共个结点 故路的长度不超过 n1 n 定理定理 6 2 2 在一个阶图中 如果存在一经过的回路 则存在一经n EVG 1 v 过的长度不超过的圈 1 vn 定义定义 6 2 2 在图中 从结点到的最短通路 一定是路 称为与 EVG i v j v i v 间的短程线短程线 Geodesic 短程线的长度称到的距离距离 Distance 记作 若从 j v i v j v ji vvd 到不存在通路 则记 i v j v ji vvd 注意注意 在有向图中 不一定等于 但一般地有如下性质 ji vvd ij vvd 0 ji vvd 0 ii vvd 通常称为三角不等式三角不等式 kikjji vvdvvdvvd 6 2 2 图的连通性图的连通性 图的连通性分为无向图的连通性和有向图的连通性 而且有向图的连通性要比无向图 的连通性复杂些 定义定义 6 2 3 在一个无向图中 若存在从结点到的通路 当然也存在从到G i v j v j v 的通路 则称与是连通的连通的 Connected 规定到自身是连通的 i v i v j v i v 在一个有向图中 若存在从结点到的通路 则称从到是可达的可达的D i v j v i v j v Accessible 规定到自身是可达的 i v 定义定义 6 2 4 若无向图中任意两结点都是连通的 则称图是连通的连通的 Connected GG 规定平凡图是是连通的 易知 无向图中 结点之间的连通关系是等价关系 设为一无向图 是GGR 中结点之间的连通关系 由可将划分成个等价类 记作 GVR GV 1 kk 由它们导出的导出子图称为的连通分支连通分支 Connected k VVV 21 21k VGVGVGG Component 其个数应为 G 例如图 6 2 2 所示的图是连通图 图是一个非连通图 1 G1 1 G 2 G 3 2 G 132 G1G2 图 6 2 2 定义定义 6 2 5 设是一有向图 若略去中各有向边的方向后所得无向图是连通DDG 的 则称是连通的连通的 Connected 或称是弱连通的弱连通的 Weakly Connected Graph DD 如果中任意两点之间 到或到至少有一个可达 则称图是单向单向D ji vv i v j v j v i vD 连通的连通的 Unilaterally Connected Graph 如果中任意两结点都互相可达 则称是强连通的强连通的 Strongly Connected Graph DD 例如在图 6 2 3 中 是弱连通的 是单向连通的 是强连通的 1 G 2 G 3 G 注意注意 强连通一定是单向连通图 单向连通一定是弱连通图 但反之不真 图 6 2 3 G1G2G3 6 2 3 割边和割点割边和割点 定义定义 6 2 6 设是一个无向图 EVG EeVv 如果从图中删去结点 及相关联的边 后得到的子图的连通分支数多于原图Gv 的连通分支数 即则称是图的一个割点割点 cut vertex GvG vG 如果 则称为图的一个割边割边 cut edge 或桥桥 bridge GeG eG 显然 从连通图中删去一个割点或割边后得到的子图是不连通的 例例 6 2 2 图 6 2 4 中 是割点 都是割边 关于割边有如下的定理 64 v v 65 e e 定理定理 6 2 1 在图中是割边 当且仅当不在任何圈上 Gee 133 习题习题 6 2 6 2 1 给定图 6 2 5 试求 从 a 到 f 的所有链 从 a 到 f 的所有路 从 a 到 f 的所有短程线和距离 图中的所有从 a 出发的圈 6 2 2 试证明 若无向图 G 中只有两个奇点 则这两个结点一定是连通的 若有向图 G 中只有两个奇点 它们一个可达另一个或互相可达吗 6 2 3 在图 6 2 6 所示的 4 个图中 哪几个是强连通图 哪几个是单向连通图 哪几个 是连通图 弱连通图 6 2 4 证明定理 6 2 1 图 G 中的边 e 是割边 当且仅当 e 不在 G 的任何圈上 图 6 2 6 a b c d 6 2 5 u 是无向连通图 G V E 中的结点 证明 u 是 G 的割点当且仅当存在 v w V 使得 v 到 w 的每一条路都经过 u 6 3 图的矩阵表示 由图的数学定义可知 一个图可以用集合来描述 从前面的例子可以看出 图也可以 用点线图表示 图的这种图形表示直观明了 在较简单的情况下有其优越性 但对于较为 复杂的图 这种表示法显示了它的局限性 所以对于结点较多的图常用矩阵来表示 这样 便于用代数知识来研究图的性质 同时也便于计算机处理 在图的矩阵表示法中 要求图 是标定的 e1 图 6 2 4 v1 v2v3 v4v5 v6 v7 v8 e2 e3 e4e5 e6 e7 e8 e9 ab c def 图 6 2 5 134 6 3 1 无向图的关联矩阵无向图的关联矩阵 定义定义 6 3 1 设无向图 EVG 21n vvvV 21m eeeE 令 的一个环是关联若 点的端是若 联不关与若 ij ji ji ij ve ev ev m 2 1 0 则称为的关联矩阵关联矩阵 Incidence matrices 记作 mnij m G GM 例 6 3 1 图 6 3 1 中的图的关联矩阵是G 000000 101000 120100 000011 001111 GM 从关联矩阵不难看出下列性质 即每列元素的和为 2 因为每边恰有两个端点 2 1 2 1 mjm n i ij GM 若为简单图则每列恰有两个 1 第 行元素之和为的度 1 i m j ij vdm i i v 当且仅当为孤立点 0 1 m j ij m i v 若第列与第列相同 则说明与为平行边 jk j e k e 如果图是简单图 则关联矩阵是矩阵 10 6 3 2 无环有向图的关联矩阵无环有向图的关联矩阵 设是无环有向图 EVG 21n vvvV 21m eeeE v1 e2 e3 e4 图 6 3 1 v2 v3 v4v5 e1 e5 e6 v1 e2 e3 e4 图 6 3 2 v2 v3 v4 e1 e5 135 令 的终点为 不关联与 的起点为 ji ji ji ij ev ev ev m 1 0 1 则称为的关联矩阵 记作 mnij m G GM 10000 11110 01101 00011 GM 是图 6 3 2 的关联矩阵 由此可看出有如下性质 GM GM 0 1 n i ij mmj 2 1 每行中 1 的个数是该点的出度 1 的个数是该点的入度 其他与无向图关联矩阵相同的性质就不再罗列 6 3 3 有向图的邻接矩阵有向图的邻接矩阵 定义定义 6 3 3 设是有向图 令 EVG 21n vvvV 的边到没有 条的边有邻接到从 ji ji ij vv kvvk a 0 1 则称为的邻接矩阵邻接矩阵 Adjacency Matrix 记作 简记 nnij a 1 G GAA 0100 1010 0100 0101 A 矩阵是图 6 3 3 的邻接矩阵 不难看出图的邻接A 矩阵的如下性质 第 i 行元素的和为 vi的出度 1 1 i n j ij vda v1 图 6 3 3 v2 v3 v4 136 因此 n i i n i n j ij mvda 111 1 第 j 列元素的和为 vj的入度 因此 1 1 j n i ij vda n j j n j n i ij mvda 111 1 A 中所有元素的和是 G 中长度为 1 的通路的数目 而为 G 中长度为 1 的回 n i ii a 1 1 路 环 的数目 下面考察 Al的元素的意义 这里其中则 2 laA nxn l ij l 1 1 kj k l ik l ij aaa 为结点到长度为 的通路的数目 为始于 终于 长度为 的回路 l ij a i v j vl l ii a i vl 的数目 Al中所有元素的和为 G 中长为 的通路的总数 而 Al对角线上元素之和 n i n j l ij a 11 l 为 G 始于 终于 各结点的长为 l 的回路总数 n i l ii a 1 在图 6 3 3 中计算得 432 AAA 1010 0200 1010 1111 2 A 0200 2020 0200 1311 3 A 2020 0400 2020 3331 4 A 由以上各矩阵得 即 G 中到长为的通路分别为 1 条 1 2 13 a3 3 13 a3 4 13 a 1 v 3 v4 3 2 3 条 3 条 而 则 G 中以为起点 终点 的长为的回路各1 4 11 3 11 2 11 aaa 1 v4 3 2 有一条 由于 所以 G 中长度为 2 的通路总数为 10 其中长为 2 的回路10 11 2 n i n j ij a 总数为 5 若令 137 则表示从结点到长度小于或等于的通 1 2 rbAAAB r ij r r r ij b 1 v j vr 路总数 而表示以为起点 终点 长度小于或等于的回路总数 r ii b 1 vr 例如 与图 6 3 3 对应的矩阵为 3330 3630 3330 5854 4 B 无向图可类似地定义邻接矩阵 对有向图的邻接矩阵得到的结论 可并行地用到无向 图上 这里我们只介绍无向简单图的邻接矩阵 6 3 4 无向简单图的邻接矩阵无向简单图的邻接矩阵 定义定义 6 3 4 设是无简单向图 令 EVG 21n vvvV Evv Evv a ji ji ij 0 1 则称为的邻接矩阵邻接矩阵 Adjacency Matrix 记作 简记 nnij a G GAA 例如图 6 3 4 的邻接矩阵为 00000 00101 01001 00001 01110 A 无向图的邻接矩阵与有向图的邻接矩阵的最大不同在于它是对称的 且矩阵的每行 每列 的元素的和等于对应结点的度 其它性质都是类似的 这里就不再重复 而有读 者自行给出 6 3 5 有向图的可达矩阵有向图的可达矩阵 定义定义 6 3 5 设是有向图 令 EVG 21n vvvV 0 1 ji vv p ji ij 否则 可达 nipii 2 1 1 v1 e2 e3 e4 图 6 3 4 v2 v3 v4v5 e1 138 则称为G的可达矩阵可达矩阵 Accessibility Matrix 记 nnij p 作 简记 GPP 图 6 3 5 所示有向图G的可达矩阵为 1110 1110 1110 1111 P 因为 nnij n bAAAEB 12 则可达矩阵中的元素可按如下的方式得到 P 否则 0 0 1 ij ij b p 即可由邻接矩阵求可达矩阵 习题习题 6 3 6 3 1 设无向图 G V v1 v2 v3 v4 邻接矩阵 0011 0010 1101 1010 A 试问 deg v1 deg v2 图 G 是否为完全图 从 v1到 v2长为 3 的路有多少条 借助图解表示法写出从 v1到 v2长为 3 的每一条路 6 3 2 画出邻接矩阵为 A 的无向图 G 的图形 其中 11111 10101 11010 10111 11010 A 6 3 3 有向图 G 如图 6 3 5 所示 写出图 G 的邻接矩阵 A v5 图 6 3 5 v1 v2 v3v4 139 G 中长度为 3 的通路有多少条 其中有几条为回路 利用图 G 的邻接矩阵 A 的布尔运算求该图的可达性矩阵 P 并根据 P 来判断该图 是否为强连通图 单向连通图 v1 v2 v3 v4 图 6 3 6 e2 e1 e3 e4 e5 v1 v2 v3 v4 图 6 3 7 e1 e2 e3 e5 e4 6 3 4 求图 6 3 6 图 6 3 7 的关联矩阵 6 3 5 求图 6 3 6 图 6 3 7 的邻接矩阵 6 4 欧拉图与 Hamilton 哈密尔顿图 6 4 1 Euler 图图 18 世纪 普鲁士的哥尼斯堡 K nigsberg 城中有一条普雷格尔 Pregel 河 河上架设 的 7 座桥连接着两岸及河中的两个小岛 如图 6 4 1 a 图 6 4 1 A B C D b A B C a D 城里的人们喜欢散步 更期望能通过每个桥一次且仅一次再回到出发地 但谁都没能 成功 于是哥尼斯堡的人们将这个问题写信告诉了瑞士著名的数学家欧拉 L Euler 欧 拉在 1736 年证明了这样的散步是不可能的 他用点代表岛和两岸的陆地 用线表示桥 得到该问题的数学模型如图 6 4 1 使 七桥问题 转化为图论问题 因此 后来的图论 b 工作者将上述 七桥问题 作为图论的起点 并将欧拉作为图论的创始人 定义定义 6 4 1 设无向图是多重图 经过图的所有边的闭链称为欧拉回欧拉回 EVG G 路路 Euler Circuit 存在欧拉回路的图称为欧拉图欧拉图 Euler Graph 若图有一条经过图的GG 每条边的链 称其为欧拉链欧拉链 Eulerian trail 并称该图的半欧拉图半欧拉图 显然 欧拉图除孤立点外是连通的 这里不妨设欧拉图是连通图 140 例例 6 4 1 图 6 4 2 中各图哪些是欧拉图 哪些是半欧拉图 a b ce d a d e a b c b d a b c c d a b c d 图 6 4 2 此例中 图 是欧拉图 是半欧拉图 中不存在欧拉链 更不存在欧 a b c d 拉链 这是因为 图中有欧拉回路 对于图 读者可作类似的研究 a abcdeca b c 从上面的例子 我们发现 凡是结点的度均是偶数的图 都是欧拉图 这是否是一般 规律呢 回答是肯定的 定理定理 6 4 1 无向连通图是欧拉图 当且仅当图中无奇点 EVG G 证明证明 若是平凡图 则定理显然成立 因此我们下面讨论的都是非平凡图 G 必要性 设图有欧拉回路 是回路的起点和终点 图G 0110 vvvvC k 0 v 的所有边都出现在中 且每条边都只出现一次 但是结点却可能不止一次出现在GC i v 中 研究图中的结点 CG i v 若 则出现在中既不是起点 也不是终点 则在中出现一次 它就 0 vvi i vC i vC 关联两条边 因此等于结点在中出现的次数的 2 倍 i vd i vC 若 且在除起点和终点外的的中间出现次 则 0 vvi 0 vC 0 kk22 kvd i 因此 对中任何结点 均为偶数 G i v i vd 充分性 因为图是连通的 且每个结点均是偶数 则可按下列步骤构造一条 EulerG 回路 从任一结点开始 取一关联的边到 因为所有结点为偶点 所以可继续 0 v 0 v 1 e 1 v 取关联的边到 关联 vi 1的边 ei到 vi 每条边均为前面没取过的 如此继 1 v 2 e 2 v 续直到回到起点 得一回路 若包含中所有的边 0 v 01221101 veevevevevC kiii 1 CG 则就是中的欧拉回路 即为欧拉图 否则转 1 CGG 若的边集非空 中的每个结点均是偶点 又连通 与必 11 GCG 1 GG 1 G 1 C 有一结点重合 在中从出发重复步骤 又可得一回路 若 i v 1 G i v ii veuevC 2112 则是欧拉图 欧拉回路为GCC 21 G 112112211021 iiiii veveuevevevevCC 否则转 0 vek 重复步骤 直到构造一条包含的所有边的回路为止 此回路即为欧拉回路 G 因此 是欧拉图 G 由此定理容易得到如下的推论 推论推论 连通图具有一条到的 Euler 链 当且仅当和是中仅有的两个奇G i v j v i v j vG 点 定义定义 6 4 2 设是有向连通图 若中具有包含所有边的闭链 则称该闭链为欧拉有欧拉有GG 141 向回路向回路 并称为欧拉有向图欧拉有向图 G 若连通有向图具有一包含所有边的有向链 则称其为欧拉有向链欧拉有向链 并称为半欧半欧GG 拉有向图拉有向图 由欧拉有向图的定义 连通的有向欧拉图一定是强连通的 定理定理 6 4 2 一个连通的有向图是 Euler 图 具有 Euler 回路 当且仅当的所有GG 结点的入度等于出度 推论推论 连通有向图有一条到的 Euler 链 当且仅当G i v j v 存在使得 GVvv ji 1 ii vdvd 1 jj vdvd 而在中的所有结点的入度等于其出度 ji vvGV 1 2 3 图 6 4 3 例例 6 4 2 欧拉图和 Euler 欧拉链的一个典型的应用是一笔画的判定 即用笔连续移 动 笔不离纸 也不重复 将一个图描绘出来 这实质上就是判断图形是否存在欧拉链或 Euler 欧拉回路的问题 如图 6 4 3 图 都可一笔画 因为欧拉图 而 不能一笔画 图 6 4 4 中 a b 都可一笔画 因为图 a 是欧拉图 而图 b 是半欧拉图 而图 c 不能一笔 画 图 6 4 4 b a c 例例 6 4 3 图 6 4 5 表示的是一个展览馆的平面图 馆里各相邻房间之间都有门 共 16 扇 一个参观者来到展览馆门外 他想在参观过程中 把馆里所有的门都不重复地穿 行一遍后出来 这个想法能否实现 首先建立该问题的图论模型 将展览馆的 5 个房间和馆外场地用 6 个结点表示 两个 端点之间的边表示它们所在位置之间有一扇门 则得到如图 6 4 5 所示的图 b 于是 判断能否不重复地穿过展览馆的每扇门一次的问题就转化为图 b 是否是欧拉图 的问题 由图 6 4 5 中的图 b 可以看出 图中有 4 个奇点 由定理 6 4 1 图 b FDBA 不是欧拉图 即参观者的想法不能实现 142 a AB CD E F 图 6 4 5 4 5 b BA C D E F 例例 6 4 4 计算机鼓轮设计 布鲁英 布鲁英 De Bruijn 序列 序列 旋转鼓轮的表面分成 8 个扇面 如图 6 4 6 所示 00 01 10 11 图 6 4 7 e0 000 e1 001 e2 010 e3 011 e4 100 e5 101e 6 110 e7 111 b a c 图 6 4 6 图 6 4 6 中阴影部区表示用导体材料制成 空白区用绝缘材料制成 触点和与ba c 扇面接触时接触导体输出 1 接触绝缘体输出 0 鼓轮按逆时针旋转 触点每转一个扇区 就输出一个二进制信号 问鼓轮上的 8 个扇区应如何安排导体或绝缘体 使鼓轮旋转一周 触点输出一组不同的二进制信号 每转一个扇区 信号变成 前者右两位决定了后者左两位 因此 我 321 aaa 432 aaa 们把所有两位二进制数作结点 从每一个结点到引一条有向边表示这三 21a a 32a a 321 aaa 位二进制数 作出表示所有可能数码变换的有向图 如图 6 4 7 于是问题转化为在这个 有向图上求一条欧拉回路 这个有向图的 4 个结点的度数都是出度 入度各为 2 根据定 义 6 4 2 图 6 4 7 中有欧拉回路存在 例如是一 Euler 回路 对应于这 46735210 eeeeeeee 一回路的布鲁英序列是 因此材料应按此序列分布 00010111 用类似的论证 我们可以证明 存在一个个二进制的循环序列 其中个由 n 位 n 2 n 2 二进制数组成的子序列都互不相同 例如 16 个二进制数的布鲁英序列是 1011110000101001 6 4 2 哈密尔顿图哈密尔顿图 爱尔兰数学家哈密尔顿 William Hamilton 爵士 1859 年提出了一个 周游世界 的游 戏 这个游戏把一个正十二面体的二十个顶点看成地球上的二十个城市 棱线看成是连接 143 城市的航路 航空 航海线或陆路交通线 要求游戏者沿棱线走 寻找一条经过所有结 点 即城市 一次且仅一次的回路 如图 6 4 8所示 也就是在图 6 4 8中找一条包 a b 含所有结点的圈 图中的粗线所构成的圈就是这个问题的回答 b 对于任何连通图也有类似的问题 定义定义 6 4 3 若图具有一条包含的所有结点的圈 则称此圈为哈密尔顿圈哈密尔顿圈GG Hamiltonian cycle 并称为哈密尔顿图哈密尔顿图 Hamiltonian Graph 若图中具有一条包含所有GG 结点的路 则称该路为哈密尔顿路哈密尔顿路 Hamiltonian path 并称为半哈密尔顿图半哈密尔顿图 G 由定义可知哈密尔顿圈与哈密尔顿路通过图中的每个结点一次且仅一次 例如图G 6 4 8就是哈密尔顿图 哈密尔顿圈用粗线标出 b a b 图 6 4 8 a b c d 图 6 4 9 例例 6 4 56 4 5 图 6 4 9 中 图 中有哈密尔顿圈 图中有哈密尔顿路 中 a b c d 既没有哈密尔顿圈也没有哈密尔顿路 对于哈密尔顿图的判定不象欧拉图那样有好的充分必要条件 下面给出哈密尔顿图的 必要条件 定理定理 6 4 3 若是哈密尔顿图 则对于结点集的任一非空真子集有G GV GVS SSG 哈密尔顿图的必要条件可用来判定某些图不是哈密尔顿图 例例 6 4 66 4 6图 6 4 10 a 不是哈密尔顿图 图 6 4 10 a 中共有 9 个结点 如果取结点集 S 3 个白点 即 而这时3 S 如图 这说明图 6 4 10 a 不是哈密尔顿图 但要注意若一个图满足4 SG b 144 定理 6 4 3 的条件也不能保证这个图一定是哈密尔顿 n 图 如图 6 4 7 c 下面再来介绍几个哈密尔顿图的充分条件 图 6 4 10 o o o a b c 定理定理 6 4 5 Dirac 1952 设是具有个结点的无向简单图 若对于任意一个结G 3 n 点都有 则是哈密尔顿图 u2 nud G 定理定理 6 4 4 Ore 1960 若 G 是具有个结点的无向简单图 对于 G 中每一对 3 n 不相邻的结点均有 则 G 是一个哈密尔顿图 vu nvdud 图 6 4 11 定理 6 4 4 和 6 4 5 都是充分条件 即满足这些条件的图一定是哈密尔顿图 但不是所有 的哈密尔顿图都满足这些条件 例如图 6 4 11 是哈密尔顿图 但它不满足上述定理的条件 a b d c 图 6 4 12 习题习题 6 4 6 4 1 对图 6 4 12 中的 4 个图 判断哪些是欧拉图 哪些是哈密尔顿图 145 图 6 4 13 h 4 a b c d ef g i j h i c ba d e f g j k 5 a b d e c f g hi j 1 b a d e c f g h i j 2 b a c d ef g h i j o 3 6 4 2 n 为何值时 无向完全图 Kn是欧拉图 n 为何值时 Kn仅存在欧拉链而不存在欧拉回路 6 4 3 在图 6 4 13 所示的图中 那些图中有哈密尔顿圈 那些图中有哈密尔顿路 6 4 4 证明图 6 4 14 所示的图不是哈密尔顿图 6 4 5 设有 a b c d e f g 七个人 他们分别会讲的语 言如下 a 会讲英语 b 会讲汉语和英语 c 会讲英语 西班 牙语和俄语 d 会讲日语和汉语 e 会讲德语和西班牙语 f 会讲法语 日语和俄语 g 会讲法语和德语 能否将七这个 人的座位安排在圆桌旁 使得每个人均能与他身边的人交谈 6 5 最短路问题 前面研究了图论的基本概念和基本理论 下面将讨论这些理论重要应用 最短路问题 中 国邮递员问题 旅行售货员问题 这里先讨论最短路问题 6 5 1 最短路问题最短路问题 定义定义 6 5 1 对于图 G 的每条边 e 都对应给一个实数 w e 称 w e 为边 e 上的权权 Weight G 连同在它边上的权称为带权图带权图 Weighted Graph 又称网络网络 带权图常记作 G 其中 W w e e E 若 e 的端点是 u v 则常用 w u v 表示边 e 的权 定义定义 6 5 2 设 H 是带权图 G 的一个子图 H 的每条边的权的和称为 H 的权 若 H 是一条路 P 则称其权为路 P 的长长 在带权图中给定了结点 u 称为始点始点 Initial Point 及结点 v 称为终点终点 Terminal Point a c b d e f g h i j k l n m p o 图 6 4 14 146 若 u v 连通 则 u 到 v 可能有若干条路 这些路中一定有一条长最小的路 这样的路称为 从 u 到 v 的最短路最短路 Shortest path 最短路的长也称 u 到 v 的距离距离 Distance 记作 d u v 求给定两个结点之间最短路的问题称为最短路问题最短路问题 Shortest path problem 要注意的是 我们这里所说的长具有广泛意义 既可指普通意义的距离 也可以是时间或费用等等 下面介绍求从一个始点 v1到各点 vk 2 k n 的最短路的算法 在下面的讨论中 假定边 vi vj 的权 wij 0 如果结点 vi与 vj不邻接 则令 wij 在实际计算中可用任一足够大的数代替 并对图中每个结点令 wii 0 到目前为止 公认的求最短路的较好的算法是由迪克斯特拉 E W Dijkstra 荷兰计算机科学家 1930 2002 1959 年提出的标号法 算法的基本思想是 先给带权图 G 的每一个结点一个临时标号临时标号 Temporary label 简 称 T 标号 或固定标号固定标号 Permanent label 简称 P 标号 T 标号表示从始点到这一点的最 短路长的上界 P 标号则是从始点到这一点的最短路长 每一步将某个结点的 T 标号改变 为 P 标号 则最多经过 n 1 步算法停止 n 为 G 的结点数 最短路的 Dijkstra 算法 给始点 v1标上 P 标号 p v1 0 令 P v1 T0 V v1 给 T0中各结点标上 T 标号 t0 vj w1j j 2 3 n 令 r 0 转 若 则令 若 min krjr Tv vtvt rj 1krr vPP 1krr vTT 则结束 否则转 1r T 修改中各结点 vj的 T 标号 Tr 1 vj min tr vj tr vk wkj 转 1 r T 例例 6 5 1 图 6 5 1 a 中结点 v1到 v7的最短路 解解 在图 a 中用方框表示 P 标号 用圆框表示 T 标号 凡图中无标号的点即该点的 标号为 下同 T0中各元素的T标号为 t0 v2 0 1 vp 10 vP 7654320 vvvvvvT 2 如图 6 5 1 b 将 v4的标号 1 改为 P 标号 且 min 400 0 vtvt j Tvj 41401 vvvPP 修改 T1各结点的 T 标号为 765321 vvvvvT 2 1 2min min 42402021 wvtvtvt 8 71 8min min 43403031 wvtvtvt 10 91 min min 47407071 wvtvtvt 147 1 min 51 vt 7161 vtvt 图 6 5 1 6 1 v 1 3 v 4 v 5 v 6 v 7 v g 2 v 2 6 7 1 2 5 9 1 3 4 8 2 1 5 0 3 6 1 v 1 3 v 4 v 5 v 6 v 7 v h 2 v 2 6 7 1 2 5 9 1 3 4 8 2 1 5 0 3 6 1 v 1 3 v 4 v 5 v 6 v 7 v e 2 v 2 6 7 1 2 5 9 1 3 4 8 2 1 0 3 1 v 1 3 v 4 v 5 v 6 v 7 v f 2 v 2 6 7 1 2 5 9 1 3 4 8 2 1 5 0 3 1 v 1 3 v 4 v 5 v 6 v 7 v c 2 v 2 6 7 1 2 5 9 1 3 4 8 1 0 1 v 1 3 v 4 v 5 v 6 v 7 v d 2 v 2 6 7 1 2 5 9 1 3 4 8 2 1 0 1 v 1 3 v 4 v 5 v 6 v 7 v b 2 v 2 6 7 1 2 5 9 1 3 4 8 0 1 v 1 3 v 4 v 5 v 6 v 7 v 2 v 2 6 7 1 2 5 9 1 3 4 8 a 如图 6 5 1 c 依次类推可得各结点的 P 标号 标号过程如图 6 5 1 a h 由图 h 可 知 v1到 v7的距离为 6 v1到 v7的最短路为 7521 vvvv 6 5 2 中国邮递员问题中国邮递员问题 1962 年我国的管梅谷首先提出并研究了如下的问题 邮递员从邮局出发经过他投递的 每一条街道 然后返回邮局 邮递员希望找出一条行走距离最短的路线 这个问题被外国 148 人称为中国邮递员问题中国邮递员问题 Chinese Postman Problem 我们把邮递员的投递区域看作一个连通的带权无