离散数学_第五部分_图论-new.pdf

一、本部分主要内容 图的基本概念：图、通路和回路、图的连通性、图的矩阵表示 图的可行遍性：欧拉图、哈密顿图、带权图及其应用 树：无向树及其性质、生成树与最小生成树、根树及其应用 平面图及图的着色：平面图、欧拉公式、平面图的判断、对偶图、点着色、面着色、边着色 支配集、覆盖集、独立集与匹配简介 第四部分 图论二、基本要求 深刻理解图论中的基本概念及其它们之间的相互关系 记住图论中的主要定理并能灵活地应用它们证明相关定理或命题 熟练掌握图论中所用的证明方法，如直接证明法、归纳法、反证法、扩大路径法等 应用握手定理及树的性质解无向图、无向树 会求最小生成树、最优树及最佳前缀码 会用临接矩阵求有向图中的通路、回路数 本章的主要内容 图及相关的诸多概念 通路与回路 图的连通性 图的矩阵表示 预备知识 多重集合——元素可以重复出现的集合 无序集——AB={(x,y) | xAyB} 第十四章 图的基本概念一、无向图与有向图的定义 1． 无向图的定义 定义 14.1 无向图 G = , 其中 （1）V  为顶点集，元素称为顶点 （2）E 为 VV 的多重集，其元素称为无向边，简称边 设 V = {v2, v2, …,v5}, E = {(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5)} 则 G = 为一无向图，用图 1 表示 G 第一节 图图12. 有向图的定义 定义 14.2 有向图 D=, 只需注意 E 是 VV 的多重子集 图 2 表示的是一个有向图，试写出它的 V 和 E 图 2 注意：图的数学定义与图形表示，在同构（待叙）的意义下是一一对应的 3． 关于无向图和有向图诸多定义或表示 （1）图 ① 可用 G 泛指图（无向的或有向的） ② V(G), E(G), V(D), E(D) ③ n 阶图 （2）有限图 （3）n 阶零图与平凡图 （4）空图—— （5）用 ek表示无向边或有向边 （6）顶点与边的关联关系 ① 关联、关联次数 ② 环 ③ 孤立点 （7）顶点之间的相邻与邻接关系 （8）邻域与关联集 ① vV(G) (G 为无向图) }{)()(})(),()(|{)(vvNvNvvuGEvuGVuuvNv的闭邻域的邻域v 的关联集 })(|{)(关联与veGEeevI ② vV(D) (D 为有向图) }{)()()()()(})(,)(|{)(})(,)(|{)(vvNvNvvvvNvvuDEvuDVuuvvvuDEuvDVuuvvDDDDDDD的闭邻域的邻域的先驱元集的后继元集（9）标定图与非标定图 （10）基图 二、多重图与简单图 定义 14.3 （1）无向图中的平行边及重数 （2）有向图中的平行边及重数（注意方向性） （3）多重图 （4）简单图 在定义 14.3 中定义的简单图是极其重要的概念 三、顶点的度数及握手定理 1． 顶点的度数（度） 定义 14.4 及衍生的概念 （1）设 G=为无向图, vV, d(v)——v 的度数, 简称度 （2）设 D=为有向图, vV, d+(v)——v 的出度 d(v)——v 的入度 d(v)——v 的度或度数 （3）(G), (G) （4）+(D), +(D), (D), (D), (D), (D) （5）奇顶点度与偶度顶点 2. 图论基本定理——握手定理 定理 14.1 设 G=为任意无向图，V={v1,v2,…,vn}, |E|=m, 则 证 G 中每条边（包括环）均有两个端点，所以在计算 G 中各顶点度数之和时，每条边均提供 2 度，当然 m 条边共提供 2m度. 定理 14.2 设 D=为任意有向图，V={v1,v2,…,vn}, |E|=m, 则 本定理的证明类似于定理 14.1 mvdnii2)(1 mvdvdmvdniiniinii 111)()(,2)(且推论 任何图（无向的或有向的）中，奇度顶点的个数是偶数. 证 设 G=为任意图，令 V1={v | vVd(v)为奇数} V2={v | vVd(v)为偶数} 则 V1V2=V, V1V2=，由握手定理可知 由于 2m,  2)( Vvvd均为偶数，所以 1)( Vvvd为偶数，但因为 V1中顶点度数为奇数，所以|V1|必为偶数. 握手定理为图论中最重要的定理，因而必须牢记它的内容并且会应用它.  VvVvVvvdvdvdm21)()()(23. 图的度数列 （1） V={v1, v2, …, vn}为无向图 G 的顶点集， 称 d(v1), d(v2), …, d(vn)为 G 的度数列 （2）V={v1, v2, …, vn}为无向图 D 的顶点集， D 的度数列：d(v1), d(v2), …, d(vn) D 的出度列：d+(v1), d+(v2), …, d+(vn) D 的入度列：d(v1), d(v2), …, d(vn) （3）非负整数列 d=(d1, d2, …, dn)是可图化的，是可简单图化的. 易知：(2, 4, 6, 8, 10)，(1, 3, 3, 3, 4) 是可图化的，后者又是可简单图化的（为什么？） ，而(2, 2, 3, 4, 5)，(3, 3, 3, 4) 都不是可简单图化的，特别是后者也不是可图化的（为什么？） 四、图的同构 定义 14.5 设 G1=, G2=为两个无向图（两个有向图） ， 若存在双射函数 f： V1V2, 对于vi,vjV1, (vi,vj)E1（E1）当且仅当(f(vi),f(vj))E2（E2） ，并且, (vi,vj)（）与 (f(vi),f(vj))（）的重数相同，则称 G1与 G2是同构的，记作 G1G2. 几点说明： 图之间的同构关系具有自反性、对称性和传递性. 能找到多条同构的必要条件，但它们全不是充分条件： ① 边数相同，顶点数相同 ② 度数列相同 ③ 对应顶点的关联集及邻域的元素个数相同，等等 若破坏必要条件，则两图不同构 判断两个图同构是个难题 试画出 4 阶 3 条边的所有非同构的无向简单图（答案为 3 个） （1） （2） （3） （4） 图 3 图 3 中， （1）与（2）不同构（度数列不同） ， （3）与（4）也不同构. （1） （2） 图 4 图 4 中（1）与（2）的度数列相同，它们同构吗？为什么？ 五、完全图与竞赛图 1．定义 14.6 （1）n (n1) 阶无向完全图——每个顶点与其余顶点均相邻的无向简单图. 简单性质：边数1,2) 1(nnnm （2）n (n1)阶有向完全图——每对顶点之间均有两条方向相反的有向边的有向简单图. 简单性质：1),1(2),1(nnnnm （3）n (n1) 阶竞赛图——基图为 Kn的有向简单图. 简单性质：边数1,2) 1(nnnm 图 5 中， （1）为 K5， （2）为 3 阶有向完全图， （3）为 4 阶竞赛图. 图 5 六、正则图 定义 14.7 n 阶 k 正则图——==k 的无向简单图 简单性质：边数2nkm （由握手定理得） Kn是 n1 正则图，彼得松图（见书上图 14.3（1）所示， 记住它） 七、子图 定义 14.8 G=, G= （1）GG —— G为 G 的子图，G 为 G的母图 （2）若 GG 且 V=V，则称 G为 G 的生成子图 （3）若 VV 或 EE，称 G为 G 的真子图 （4）V（VV 且 V）的导出子图，记作 G[V] （5）E（EE 且 E）的导出子图，记作 G[E] 例 画出 K4的所有非同构的生成子图 图 6 八、补图 定义 14.9 设 G=为 n 阶无向简单图， 以 V 为顶点集，以所有使 G 成为完全图 Kn的添加边组成的集合为边集的图，称为 G 的补图，记作G. 若 GG, 则称 G 是自补图. 相对于 K4, 求图 6 中所有图的补图，并指出哪些是自补图. 问：互为自补图的两个图的边数有何关系？ 一、通路与回路的定义 定义 14.11 给定图 G=（无向或有向的） ，G 中顶点与边的交替序列  = v0e1v1e2…elvl，vi1, vi是 ei的端点. （1）通路与回路：为通路；若 v0=vl，为回路，l 为回路长度. （2）简单通路与回路：所有边各异，为简单通路，又若 v0=vl，为简单回路 （3）初级通路（路径）与初级回路（圈） ：中所有顶点各异，则称为初级通路（路径） ，又若除 v0=vl，所有的顶点各不相同且所有的边各异，则称为初级回路（圈） （4）复杂通路与回路：有边重复出现 第二节 通路与回路几点说明 表示法 ① 定义表示法 ② 只用边表示法 ③ 只用顶点表示法（在简单图中） ④ 混合表示法 环（长为 1 的圈）的长度为 1，两条平行边构成的圈长度为2，无向简单图中，圈长3，有向简单图中圈的长度2. 不同的圈（以长度3 的为例） ① 定义意义下 无向图：图中长度为 l（l3）的圈，定义意义下为 2l 个 有向图：图中长度为 l（l3）的圈，定义意义下为 l 个 ② 同构意义下：长度相同的圈均为 1 个 试讨论 l=3 和 l=4 的情况 二、图中通路与回路的长度的讨论 定理 14.5 在 n 阶图 G 中， 若从顶点 vi到 vj（vivj） 存在通路，则从 vi到 vj存在长度小于或等于 n1 的通路. 推论 在 n 阶图 G 中，若从顶点 vi到 vj（vivj）存在通路，则从 vi到 vj存在长度小于或等于 n1 的初级通路（路径）. 定理 14.6 在一个 n 阶图 G 中，若存在 vi到自身的回路，则一定存在 vi到自身长度小于或等于 n 的回路. 推论 在一个 n 阶图 G 中，若存在 vi到自身的简单回路，则一定存在长度小于或等于 n 的初级回路. 一、无向图的连通性与连通度 1． 无向图的连通性 （1）顶点之间的连通关系：G=为无向图 ① 若 vi与 vj之间有通路，则 vivj ② 是 V 上的等价关系 R={| u,v V 且 uv} （2）G 的连通性与连通分支 ① 若u,vV，uv，则称 G 连通 ② V/R={V1,V2,…,Vk}，称 G[V1], G[V2], …,G[Vk]为连通分 支，其个数 p(G)=k（k1） ；k=1，G 连通 第三节 图的连通性（3）短程线与距离 ① u 与 v 之间的短程线：uv，u 与 v 之间长度最短的通路 ② u 与 v 之间的距离：d(u,v)——短程线的长度 ③ d(u,v)的性质： d(u,v)0, u≁v 时 d(u,v)= d(u,v)=d(v,u) d(u,v)+d(v,w)d(u,w) 2. 无向图的连通度 （1）删除顶点及删除边 ① Gv ——从 G 中将 v 及关联的边去掉 ② GV——从 G 中删除 V中所有的顶点 ③ Ge ——将 e 从 G 中去掉 ④ GE——删除 E中所有边 （2）点割集与边割集 ① 点割集与割点 定义 14.16 G=, VV V为点割集——p(GV)>p(G)且有极小性 v 为割点——{v}为点割集 图 7 图 7 中，{v1,v4}，{v6}是点割集，v6是割点. {v2,v5}是点割集吗？ ② 边割集与割边 定义 14.17 G=, EE E是边割集——p(GE)>p(G)且有极小性 e 是割边（桥）——{e}为边割。