第四篇图论自从1736年欧拉（L.Euler）利用图论的思想解决了哥尼斯堡（Konigsberg）七桥问题以来，图论经历了漫长的发展道路。

在很长一段时期内，图论被当成是数学家的智力游戏，解决一些著名的难题。

如迷宫问题、匿门博奕问题、棋盘上马的路线问题、四色问题和哈密顿环球旅行问题等，曾经吸引了众多的学者。

图论中许多的概论和定理的建立都与解决这些问题有关。

1847年克希霍夫（Kirchhoff）第一次把图论用于电路网络的拓扑分析，开创了图论面向实际应用的成功先例。

此后，随着实际的需要和科学技术的发展，在近半个世纪内，图论得到了迅猛的发展，已经成了数学领域中最繁茂的分支学科之一。

尤其在电子计算机问世后，图论的应用范围更加广泛，在解决运筹学、信息论、控制论、网络理论、博奕论、化学、社会科学、经济学、建筑学、心理学、语言学和计算机科学中的问题时，扮演着越来越重要的角色，受到工程界和数学界的特别重视，成为解决许多实际问题的基本工具之一。

图论研究的课题和包含的内容十分广泛，专门著作很多，很难在一本教科书中概括它的全貌。

作为离散数学的一个重要内容，本书主要围绕与计算机科学有关的图论知识介绍一些基本的图论概论、定理和研究内容，同时也介绍一些与实际应用有关的基本图类和算法，为应用、研究和进一步学习提供基础。

第4-1章无向图和有向图学习要求：仔细领会和掌握图论的基本概论、术语和符号，对于图论研究的一些最基本的课题，如道路问题、连通性问题和着色的问题等，应掌握主要的定理内容和证明方法以及基本的构造方法，以便为下一章研究提供理论工具。

学习本章要用到集合和线性代数矩阵运算的知识，特别是集合数和矩阵秩的概念。

§4-1-1 图的基本概念图是用于描述现实世界中离散客体之间关系的有用工具。

在集合论中采用过以图形来表示二元关系的办法，在那里，用点来代表客体，用一条由点a指向点b的有向线段来代表客体a和b之间的二元关系aRb，这样，集合上的二元关系就可以用点的集合V和有向线的集合E构成的二元组（V，E）来描述。

同样的方法也可以用来描述其它的问题。

当我们考察全球航运时，可以用点来代表城市，用线来表示两城市间有航线通达；当研究计算机网络时，可以用点来表示计算机及终端，用线表示它们之间的信息传输通道；当研究物质的化学结构时，可以用点来表示其中的化学元素，而用线来表示元素之间的化学键。

在这种表示法中，点的位置及线的长短和形状都是无关紧要的，重要的是两点之间是否有线相连。

从图形的这种表示方式中可以抽象出图的数学概念来。

一、图定义4-1-1.1一个（无向）图G是一个二元组（V（G），E（G）），其中V （G）是一个有限的非空集合，其元素称为结点；E（G）是一个以不同结点的无序对为元素，并且不含重复元素的集合，其元素称为边。

我们称V（G）和E（G）分别是G的结点集和边集。

在不致引起混淆的地方，常常把V（G）和E（G）分别简记为V 和E 。

我们约定，由结点u 和结点v 构成的无序对用uv （或vu ）表示。

根据图的这种定义，很容易利用图形来表示图。

图形的表示方法具有直观 性，可以帮助我们了解图的性质。

在图的图形表示中，每个结点用一个小圆点表示，每条边u v 用一条分别以结点v 和u 为端点的联线表示。

图4-1-1.1中，（a ）是图{}{}),,,,,,,,,(4342324131214321v v v v v v v v v v v v v v v v G 的图形表示；（b ）是图H={}{}()65323121654321,,,,,,,,,u u u u u u u u u u u u u u 的图形表示。

在某些情况下，图的图形表示中，可以不标记每个结点的名称。

(a ) (b )图4-1-1.1须注意，一个图的图形表示法可能不是唯一的。

表示结点的圆点和表示边的线，它们的相对位置是没有实际意义的。

因此，对于同一个图，可能画出很多表面不一致的图形来。

例如图4-1-1.1的（a ）图还可以有图9—1.2中的两种图形表示。

图4-1-1.2图G 的结点数称为G 的阶，用字母n 的表示。

G 的边数用m 表示，也可以表示成m G E =)(。

一个边数为m 的n 阶图可简称为（n ，m ）—图。

如图4-1-1.1的（a ）和（b ）分别表示一个（4，6）—图和一个（6，4）—图。

若uv e =是图G 的一条边，则称结点u 和v 是相互邻接的，并且说边e 分别与u 和v 相互关联。

若G 的两条边1e 和2e 都与同一个结点关联时，称1e 和2e 3v 4u 2 u 5u 64 v23 v是相互邻接的。

二、图的变体若在定义4-1-1.1中去掉边集E中“不含重复元素”的限制条件，则得到多重图的定义。

在多重图中，允许两条或两条以上的边与同一对结点关联，这些边称为平行边。

由于可能有多条边与同一个结点对相关联，为区别起见，有时也对各边加以编号。

图4-1-1.3是多重图的一个例子。

若在多重图的基础上，进一步去掉边是由不同结点的无序对表示的条件，即允许形如uue=的边（称为环）存在，则得到广义图或伪图的定义。

图4-1-1.4是伪图的一个例子。

图4-1-1.3 图4-1-1.4为了区别于多重图和伪图，以后称满足定义4-1-1.1的图为简单图。

很明显，将多重图和伪图中的平行边代之以一条边，去掉环，就可以得到一个简单图。

这样得到的简单图称为原来图的基图。

在研究某些图论问题，如连通，点着色，点独立集，哈密顿图和平面性问题时只要考虑对应的基图就行了。

因此，简单图将是本课程的主要讨论对象。

“图”将作为一个概括性的词加以使用。

另外，有向图也是极重要的研究对象，在计算机科学中尤其有用。

只要在定义4-1-1.1中把“无序对”换成“有序对”就得到了有向图的定义。

有向图的“边”用形如),(vue=的序偶表示，其意义是e是一条由结点u指向结点v的有向边，并且称e是u的出边，是v的入边。

自然，),(vu和),(uv是不同的边。

类似于图定义的扩充，也可以定义出相应的多重有向图和有向伪图，并把上面定义的有向图相应称为简单有向图。

“有向图”将作为概括性的词加以使用。

图vv254-1-1.5中（a ）、（b ）和（c ）分别是简单有向图、多重有向图和有向伪图的例子。

(a )图4-1-1.5有时也要考虑有向图的基图。

一个有向图的基图是当去掉的边方向后得到的无向图（可以含有平行边和环）。

根据不同的应用，图的定义还有别的一些扩充形式，如权图、标号图、无限图、混合图、根图、超图等。

三、图论基本定理下面将从数量方面去建立图的元素的基本关系。

定义 4-1-1.2 图G 中结点v 的度（简称点度）)(v d G 是G 中与v 关联的边的数目。

每个环在计度时算作两条边。

图G 中最大的点度和最小的点度分别记为G ∆和G δ。

在不致引起混淆的地方，)(v d G ，G ∆和G δ分别简写成)(v d ，∆和δ。

在图4-1-1.4中 3,6,4)(,6)(,6)(,5)(,3)(54321==∆=====δv d v d v d v d v d 。

由图中各结点的度构成的序列称为该图一个度序列。

例如图4-1-1.4的一个度序列是（3，5，6，6，4）。

度序列在某些图论专题中也是重要的研究工具。

下面介绍图论中最基本的定理，它是欧拉1736年在解决“Konigsberg 七桥问题”时建立的第一个图论结果，很多重要结论都与它有关。

定理4-1-1.1 （图论基本定理—握手定理）对于任何（n ，m ）—图∑∈==Vv m v d E V G 2)(),,(。

即点度之和等于边数的两倍。

证明： 根据点度的定义，在计算点度时每条边对于它所关联的结点被计算了两次。

因此，G 中点度的总和恰为边数m 的2倍。

推论 9—1.1.1 在任何图中，奇数度的结点数必是偶数。

证明 设V 1和V 2分别是图G 的奇度结点集和偶度结点集。

由定理4-1-1.1应有∑∑∈∈=+212)()(V v V v m v d v d 。

上式左端第二项是偶数之和，从而第一项必然也是偶数，即1V 必须是偶数。

在有向图中，点度的概念稍有不同。

定义 4-1-1.3 有向图G 中，结点v 的入度)(v d -是与v 关联的入边的数目，出度)(v d +是与v 关联的出边的数目。

有向图的最大出度、最大入度、最小出度、最小入度分别记为-+-+∆∆δδ、、、。

例 在图4-1-1.5（c ）中，1)(,2)(,2)(,2)(,3)(32211=====+-+-+v d v d v d v d v d 2,1,2,3,2)(3===∆=∆=-+-+-δδv d 。

定理 4-1-1.2 对于任何（n ，m ）—有向图G =（V ，E ），m v d v d Vv V v ==-∈+∈∑∑)()(。

证明：任何一条有向边，在计算点度时提供一个出度和一个入度。

因此，任意有向图出度之和等于入度之和等于边数。

四、基本图例图中度为零的结点称为孤立结点。

只由孤立结点构成的图),(Φ=V G 称为零图，特别地，只由一个孤立结点构成的图称为平凡图。

各点度相等的图称为正则图。

特别地，点度为k 的正则图又称为k 度正则图。

显然，零图是零度正则图。

任何两个结点都相互邻接的简单图称为完全图。

n 阶的完全图是))1(21,(-n n n —图，特别记之为n K 。

图4-1-1.6是常用的几个完全图。

显然，n K 是（n -1）度正则图。

图9—1.6类似地，可以定义有向完全图。

每对结点u 和v 之间皆有边（u ,v ）和（v ,u ）联结的简单有向图称为有向完全图。

每对结点u 和v 之间恰有一条边（u ,v ）（或（v ,u ））联结的简单有向图称为竞赛图。

图4-1-1.7（a ）是三阶有向完全图，（b ）是4阶的竞赛图。

图4-1-1.7图G=（V ，E ）的结点集可以分划成两个子集X 和Y ，使得它的每一条边的一个关联结点在X 中，另一个关联结点在Y 中，这类图称为二部图，又常说G 是具有二部分划（X ，Y ）的图。

设G 是具有二部分划（X ，Y ）的图，21,n Y n X ==，如果X 中每个结点与Y 中的全部结点都邻接，则称G 为完全二部图，并记之为21,n n K 。

图4-1-1.8中（a ）和（b ）都是二部图，其中(a )图的黑点属于一部，其余结点属于另一部，(b )图是3,3K ，其二部分划是明显的。

K 1K 2 K 3 K 4 K 5（a ） （b ）（a ） （b ）图4-1-1.8五、子图与补图1．子图定义 4-1-1.4 设),(11E V G =和),(22E V H =是两个图，若满足12V V ⊆且12E E ⊆，则称H 是G 的子图。