天大《离散数学》学习笔记八.pdf

离散数学（1）学习笔记八主 题：离散数学（1）学习笔记 内 容：离散数学（1）学习笔记八 图论的基本概念、连通性 教学目的、要求:掌握：图的基本概念及其性质，通路和回路，图的连通性的判别方法理解：通路、回路的概念了解：图的同构教学内容：基本内容：图的基本概念，图的同构，通路和回路，图的连通性重点：图的概念，结点次数和边关系的定理难点：判别图的同构基本要求1熟悉图的基本概念及其性质2了解图的同构3理解通路、回路的概念，掌握其判别方法第六章图论图论（graphic theory）是一门既古老又年轻的学科说它古老，是因为早在18 世纪初，学者们便已运用现在称之为图的工具来解决一些困难的问题；说它年轻，是因为直到20 世纪中、后期，图的理论研究和应用研究才得到广泛的重视，图论作为一个数学的分支，才真正确立自己的地位对于离散结构的刻划，图是一种有力的工具我们已经看到，有限集合上的关系可用一一种直观的图有向图来表示；我们可以想象，在运筹规划、网络研究中，在计算机程序流程分析中，都会遇到由称为“结点”和“边”的东西组成的图因此，对图论基础知识的学习，以及对有广泛应用价值的各种特殊图的了解是十分必要的。

本章的任务是，讨论图的基本概念及有关术语，研究图的基本性质6.1 图论的基本概念 6.1.1 图的实例 1736年瑞士数学家欧拉（Euler）解决了当时很有名的哥尼斯堡七桥问题，并发表了第一篇图论方向的论文哥尼斯堡（曾名为加里宁格勒）位于立陶宛的普雷格尔河畔河中有两个小岛，城市与小岛由七座小桥相联（如图6.l（a）所示）当时城中居民热衷于这样一个问题：游人是否可能从城市或小岛的一点出发，经由七座桥，并且只经由每座桥一次，然后回到原地许多人久而不得其解，名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 10 页 -离散数学（1）学习笔记八但欧拉却用一个十分简明的工具-一张图（如图 6.1（b）所示）解决了这一问题图中的结点用以表示河两岸及两个小岛，边用以表示小桥，如果游人可以作出所要求的那种游历，那么必可从图的某一结点出发，经过每条边一次且仅经过一次后又回到原结点这时，对每个结点而言，每离开一次，总相应地要进入一次，而每次进出不得重复同一条边，因而它应当与偶数条边相联结由于图6.1 之（b）中并非每个结点都与偶数条边相联结，因此游人不可能作出所要求的游历ab图 6.1图 6.1 之（b）是（a）的抽象。

我们看到，与几何图形不同，我们不关心（b）中图形的结点的位置，也不关心边的长短、形状，只关心结点与边的联结关系这就是说，我们要研究的图是不同于几何图形的另一种数学结构6.1.2 图的基本概念图是用于描述现实世界中离散客体之间关系的有用工具在集合论中采用过以图形来表示二元关系的办法，在那里，用点来代表客体，用一条由点 a 指向点b 的有向线段来代表客体a 和 b 之间的二元关系aRb，这样，集合上的二元关系就可以用点的集合V 和有向线的集合E 构成的二元组（V，E）来描述同样的方法也可以用来描述其它的问题当我们考察全球航运时，可以用点来代表城市，用线来表示两城市间有航线通达；当研究计算机网络时，可以用点来表示计算机及终端，用线表示它们之间的信息传输通道；当研究物质的化学结构时，可以用点来表示其中的化学元素，而用线来表示元素之间的化学键在这种表示法中，点的位置及线的长短和形状都是无关紧要的，重要的是两点之间是否有线相连从图形的这种表示方式中可以抽象出图的数学概念来定义 6.1 一个（无向）图 G 是一个二元组（V（G），E（G），其中 V（G）是一个有限的非空集合，其元素称为结点；E（G）是一个以不同结点的无序对为元素，并且不含重复元素的集合，其元素称为边。

名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 10 页 -离散数学（1）学习笔记八我们称 V（G）和 E（G）分别是 G 的结点集和边集在不致引起混淆的地方，常常把 V（G）和 E（G）分别简记为 V 和 E我们约定，由结点u 和结点v 构成的无序对用 uv（或 vu）表示根据图的这种定义，很容易利用图形来表示图图形的表示方法具有直观性，可以帮助我们了解图的性质在图的图形表示中，每个结点用一个小圆点表示，每条边 u v 用一条分别以结点v 和 u 为端点的联线表示图6.2 中，（a）是图),(4342324131214321vvvvvvvvvvvvvvvvG的 图 形 表 示；（b）是 图H=()65323121654321,uuuuuuuuuuuuuu的图形表示在某些情况下，图的图形表示中，可以不标记每个结点的名称a)(b)图 6.2 须注意，一个图的图形表示法可能不是唯一的表示结点的圆点和表示边的线，它们的相对位置是没有实际意义的图 G 的结点数称为 G 的阶，用字母 n 的表示G 的边数用 m表示，也可以表示成mGE=)(一个边数为 m 的 n 阶图可简称为（n，m）图。

如图 6.2 的（a）和（b）分别表示一个（4，6）图和一个（6，4）图若uve=是图 G 的一条边，则称结点u 和 v是相互邻接的，并且说边e分别与 u 和 v 相互关联若 G 的两条边1e 和2e 都与同一个结点关联时，称1e 和2e 是相互邻接的另外，有向图也是极重要的研究对象，在计算机科学中尤其有用只要在定义 6.1 中把“无序对”换成“有序对”就得到了有向图的定义有向图的“边”用形如),(vue=的序偶表示，其意义是e是一条由结点 u 指向结点 v 的有向边，并且称 e是 u 的出边，是 v 的入边自然，),(vu和),(uv是不同的边不与任何结点相邻的结点称为孤立结点只由孤立结点构成的图),(=VG称为零图，特别地，只由一个孤立结点构成的图称为平凡图各点度相等的图称为正则图特别地，点度为 k 的正则图又称为k 度正则图v1v2v3v4u1u2u3u4u5u6名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 10 页 -离散数学（1）学习笔记八显然，零图是零度正则图任 何 两 个 结 点 都 相 互 邻 接 的 简 单 图 称 为 完 全 图n 阶 的 完 全 图 是)1(21,(-nnn图，特别记之为nK。

图 6.3 是常用的几个完全图显然，nK 是（n-1）度正则图图 6.3 类似地，可以定义有向完全图每对结点u 和 v 之间皆有边（u,v）和（v,u）联结的简单有向图称为有向完全图每对结点u 和 v 之间恰有一条边（u,v）（或（v,u）联结的简单有向图称为竞赛图图6.4（a）是三阶有向完全图，（b）是4 阶的竞赛图图 6.4 定义 6.2 设),(11EVG=和),(22EVH=是两个图，若满足12VV?且12EE?，则称 H 是 G 的子图特别地，当12VV=时，称 H 是 G 的生成子图；当12EE?或12VV?时，称 H 是 G 的真子图；当12VV=且12EE=或=2E时，称 H 是 G 的平凡子图定义 6.3 设),(EVG和),(EVG=是两个简单图若EuvVuvuvEVV?=,，即边Euv当且但当Euv?，则称 G 是 G的补图显然，G 可以看成是某完全图nK 的删边子图EKn-图 6.5 是一个图及其补图的例子K1K2K3K4K5（a）（b）名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 10 页 -离散数学（1）学习笔记八图6.5 6.1.3 图中结点的次数 下面将从数量方面去建立图的元素的基本关系。

定义 6.4 图 G 中结点 v 的度（简称点度）)(vdG是 G 中与 v 关联的边的数目每个环在计度时算作两条边图 G 中最大的点度和最小的点度分别记为G?和G在不致引起混淆的地方，)(vdG，G?和G分别简写成)(vd，?和下面介绍图论中最基本的定理，它是欧拉1736 年在解决“Konigsberg 七桥问题”时建立的第一个图论结果，很多重要结论都与它有关定 理6.1（图 论 基 本 定 理 握 手 定 理）对 于 任 何（n，m）图=VvmvdEVG2)(),(即点度之和等于边数的两倍证明：根据点度的定义，在计算点度时每条边对于它所关联的结点被计算了两次因此，G 中点度的总和恰为边数m 的 2 倍推论 6.1 在任何图中，奇数度的结点数必是偶数证明设 V1和 V2分别是图 G 的奇度结点集和偶度结点集由定理 6.1 应有=+212)()(VvVvmvdvd上式左端第二项是偶数之和，从而第一项必然也是偶数，即1V必须是偶数在有向图中，点度的概念稍有不同定义 6.5 有向图 G 中，结点 v 的入度)(vd-是与 v 关联的入边的数目，出度)(vd+是与 v 关联的出边的数目有 向 图 的 最 大 出 度、最 大 入 度、最 小 出 度、最 小 入 度 分 别 记 为-+-+?000。

定理 6.2 对于任何（n，m）有向图 G=（V，E），mvdvdVvVv=-+)()(v1v2v3v4v5v6v1v2v3v4v5v6GG名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 10 页 -离散数学（1）学习笔记八证明：任何一条有向边，在计算点度时提供一个出度和一个入度因此，任意有向图出度之和等于入度之和等于边数6.1.4 图的同构一个图的图形表示不一定是唯一的，但有很多表面上看来似乎不同的图却可以有着极为相似图形表示，这些图之间的差别仅在于结点和边的名称的差异，而从邻接关系的意义上看，它们本质上都是一样的，可以把它们看成是同一个图的不同表现形式这就是图的同构概念定义 6.6 设),(EVG=和),(EVG=是两个图，如果存在双射VV:?，使得EvuEuv?)()(?，则称 G 和G同构，并记之为GG?这个定义也适用于有向图，只须在边的表示法中作相应的代换就行了图 6.6 中 两 个 图 形 代 表 的 图 是 同 构 的因 为 存 在 着 双 射?，使5,81()(3=+iiuvii?，这里下标是在 mod8 的意义下确定的），15)(uv=?图6.6 一般说来，要判定两个图是否同构是非常困难的，尚无一个简单的方法可以通用。

但在某些情况下可根据同构的必要条件有效地排除不同构的情况根据定义，同构的图除了有相同的结点数和边数外，对应的结点度数也必须相同，不满足这些条件的图不可能同构例如图6.7 中的两个图不是同构的因为如果两图同构，两个无环的 4 度结点必须对应但左图的 4 度结点的邻接结点，其结点度都不小于 3，而右图的 4 度结点却有一个2 度的邻接结点，因此不可能建立起双射图6.7 v1v2v3v4v5v6v7v8u2u5u4u1u3u6u7u8名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 10 页 -离散数学（1）学习笔记八容易知道，图的同构关系是图集上的等价关系凡是同构的图将不予区别，只须考虑等价类中的代表元由于我们感兴趣的主要是图的结构性质，在大多数情况下，不再标出图的全部结点名称和边的名称6.1.5 多重图、赋权图 若在定义 6.1 中去掉边集 E 中“不含重复元素”的限制条件，则得到多重图的定义在多重图中，允许两条或两条以上的边与同一对结点关联，这些边称为平行边由于可能有多条边与同一个结点对相关联，为区别起见，有时也对各边加以编号图 6.8 是多重图的一个例子图 6.8 有时，在一个图中边的旁侧可附加一些数字，以刻画此边的某些数量特征，称为边的权，而此边叫有权边，而具有有权边的图称为有权图，而无有权边的图称为无权图。

6.2 通路、回路和连通性6.2.1 通路和回路 在图或有向图中，常常要考虑从确定的结点出发，沿结点和边连续地移动而到达另一确定的结点的问题从这种由结点和边（或有向边）的序列的构成方式中可以抽象出图的道路概念定义 6.7 图（或有向图）G（V，E）中的非空序列kkve。