离散数学之图论

1第四篇图论自从1736年欧拉（L.Euler）利用图论的思想解决了哥尼斯堡（Konigsberg）七桥问题以来，图论经历了漫长的发展道路。在很长一段时期内，图论被当成是数学家的智力游戏，解决一些著名的难题。如迷宫问题、匿门博奕问题、棋盘上马的路线问题、四色问题和哈密顿环球旅行问题等，曾经吸引了众多的学者。图论中许多的概论和定理的建立都与解决这些问题有关。1847年克希霍夫（Kirchhoff）第一次把图论用于电路网络的拓扑分析，开创了图论面向实际应用的成功先例。此后，随着实际的需要和科学技术的发展，在近半个世纪内，图论得到了迅猛的发展，已经成了数学领域中最繁茂的分支学科之一。尤其在电子计算机问世后，图论的应用范围更加广泛，在解决运筹学、信息论、控制论、网络理论、博奕论、化学、社会科学、经济学、建筑学、心理学、语言学和计算机科学中的问题时，扮演着越来越重要的角色，受到工程界和数学界的特别重视，成为解决许多实际问题的基本工具之一。图论研究的课题和包含的内容十分广泛，专门著作很多，很难在一本教科书中概括它的全貌。作为离散数学的一个重要内容，本书主要围绕与计算机科学有关的图论知识介绍一些基本的图论概论、定理和研究内容，同时也介绍一些与实际应用有关的基本图类和算法，为应用、研究和进一步学习提供基础。第4-1章无向图和有向图学习要求：仔细领会和掌握图论的基本概论、术语和符号，对于图论研究的一些最基本的课题，如道路问题、连通性问题和着色的问题等，应掌握主要的定理内容和证明方法以及基本的构造方法，以便为下一章研究提供理论工具。学习本章要用到集合和线性代数矩阵运算的知识，特别是集合数和矩阵秩的概念。§4-1-1图的基本概念图是用于描述现实世界中离散客体之间关系的有用工具。在集合论中采用过以图形来表示二元关系的办法，在那里，用点来代表客体，用一条由点a指向点b的有向线段来代表客体a和b之间的二元关系aRb，这样，集合上的二元关系就可以用点的集合V和有向线的集合E构成的二元组（V，E）来描述。同样的2方法也可以用来描述其它的问题。当我们考察全球航运时，可以用点来代表城市，用线来表示两城市间有航线通达；当研究计算机网络时，可以用点来表示计算机及终端，用线表示它们之间的信息传输通道；当研究物质的化学结构时，可以用点来表示其中的化学元素，而用线来表示元素之间的化学键。在这种表示法中，点的位置及线的长短和形状都是无关紧要的，重要的是两点之间是否有线相连。从图形的这种表示方式中可以抽象出图的数学概念来。一、图定义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）表示。根据图的这种定义，很容易利用图形来表示图。图形的表示方法具有直观性，可以帮助我们了解图的性质。在图的图形表示中，每个结点用一个小圆点表示，每条边uv用一条分别以结点v和u为端点的联线表示。图4-1-1.1中，（a）是图),,,,,,,,,(4342324131214321vvvvvvvvvvvvvvvvG的图形表示；（b）是图H=65323121654321,,,,,,,,,uuuuuuuuuuuuuu的图形表示。在某些情况下，图的图形表示中，可以不标记每个结点的名称。(a)(b)图4-1-1.1须注意，一个图的图形表示法可能不是唯一的。表示结点的圆点和表示边的线，它们的相对位置是没有实际意义的。因此，对于同一个图，可能画出很多表面不一致的图形来。例如图4-1-1.1的（a）图还可以有图9—1.2中的两种图形表示。v1v2v3v4u1u2u3u4u5u63图4-1-1.2图G的结点数称为G的阶，用字母n的表示。G的边数用m表示，也可以表示成mGE)(。一个边数为m的n阶图可简称为（n，m）—图。如图4-1-1.1的（a）和（b）分别表示一个（4，6）—图和一个（6，4）—图。若uve是图G的一条边，则称结点u和v是相互邻接的，并且说边e分别与u和v相互关联。若G的两条边1e和2e都与同一个结点关联时，称1e和2e是相互邻接的。二、图的变体若在定义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的图为简单图。很明显，将多重图和伪图中的平行边代之以一条边，去掉环，就可以得到一个简单图。这样得到的简单图称为原来图的基图。在研究某些图论问题，如连通，点着色，点独立集，哈密顿图和平面性问题时只要考虑对应的基图就行了。因此，简单图将是本课程的主要讨论对象。“图”将作为一个概括性的词加以使用。另外，有向图也是极重要的研究对象，在计算机科学中尤其有用。只要在定v3v1v2v4v1v2v3v4v5v4v3v1v2v2v3v4v14义4-1-1.1中把“无序对”换成“有序对”就得到了有向图的定义。有向图的“边”用形如),(vue的序偶表示，其意义是e是一条由结点u指向结点v的有向边，并且称e是u的出边，是v的入边。自然，),(vu和),(uv是不同的边。类似于图定义的扩充，也可以定义出相应的多重有向图和有向伪图，并把上面定义的有向图相应称为简单有向图。“有向图”将作为概括性的词加以使用。图4-1-1.5中（a）、（b）和（c）分别是简单有向图、多重有向图和有向伪图的例子。(a)图4-1-1.5有时也要考虑有向图的基图。一个有向图的基图是当去掉的边方向后得到的无向图（可以含有平行边和环）。根据不同的应用，图的定义还有别的一些扩充形式，如权图、标号图、无限图、混合图、根图、超图等。三、图论基本定理下面将从数量方面去建立图的元素的基本关系。定义4-1-1.2图G中结点v的度（简称点度）)(vdG是G中与v关联的边的数目。每个环在计度时算作两条边。图G中最大的点度和最小的点度分别记为G和G。在不致引起混淆的地方，)(vdG，G和G分别简写成)(vd，和。在图4-1-1.4中3,6,4)(,6)(,6)(,5)(,3)(54321vdvdvdvdvd。由图中各结点的度构成的序列称为该图一个度序列。例如图4-1-1.4的一个度序列是（3，5，6，6，4）。度序列在某些图论专题中也是重要的研究工具。下面介绍图论中最基本的定理，它是欧拉1736年在解决“Konigsberg七桥问题”时建立的第一个图论结果，很多重要结论都与它有关。定理4-1-1.1（图论基本定理—握手定理）对于任何（n，m）—图（b）(c)v1v2v35VvmvdEVG2)(),,(。即点度之和等于边数的两倍。证明：根据点度的定义，在计算点度时每条边对于它所关联的结点被计算了两次。因此，G中点度的总和恰为边数m的2倍。推论9—1.1.1在任何图中，奇数度的结点数必是偶数。证明设V1和V2分别是图G的奇度结点集和偶度结点集。由定理4-1-1.1应有212)()(VvVvmvdvd。上式左端第二项是偶数之和，从而第一项必然也是偶数，即1V必须是偶数。在有向图中，点度的概念稍有不同。定义4-1-1.3有向图G中，结点v的入度)(vd是与v关联的入边的数目，出度)(vd是与v关联的出边的数目。有向图的最大出度、最大入度、最小出度、最小入度分别记为、、、。例在图4-1-1.5（c）中，1)(,2)(,2)(,2)(,3)(32211vdvdvdvdvd2,1,2,3,2)(3vd。定理4-1-1.2对于任何（n，m）—有向图G=（V，E），mvdvdVvVv)()(。证明：任何一条有向边，在计算点度时提供一个出度和一个入度。因此，任意有向图出度之和等于入度之和等于边数。四、基本图例图中度为零的结点称为孤立结点。只由孤立结点构成的图),(VG称为零图，特别地，只由一个孤立结点构成的图称为平凡图。各点度相等的图称为正则图。特别地，点度为k的正则图又称为k度正则图。显然，零图是零度正则图。任何两个结点都相互邻接的简单图称为完全图。n阶的完全图是))1(21,(nnn—图，特别记之为nK。图4-1-1.6是常用的几个完全图。显然，nK6是（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,nYnX，如果X中每个结点与Y中的全部结点都邻接，则称G为完全二部图，并记之为21,nnK。图4-1-1.8中（a）和（b）都是二部图，其中(a)图的黑点属于一部，其余结点属于另一部，(b)图是3,3K，其二部分划是明显的。图4-1-1.8五、子图与补图1．子图K1K2K3K4K5（a）（b）（a）（b）7定义4-1-1.4设),(11EVG和),(22EVH是两个图，若满足12VV且12EE，则称H是G的子图。特别地，当12VV时，称H是G的生成子图；当12EE或12VV时，称H是G的真子图；当12VV且12EE或2E时，称H是G的平凡子图。由一个图产生其子图的方法。删点子图。设v是图G的一个结点，从G中删去结点v及其关联的全部边以后得到的图，称为G的删点子图，记为G-v，图4-1-1.9是图G及其删点子图的例子。一般地，设},,,{21kvvvS是),(EVG的结点集V的子集，则},,,{21kvvvG就是从G中删去结点kvvv,,,21以及它们关联的全部边后得到的G的删点子图，也可以简记为G-S。图4-1-1.9删边子图。设e是图G的一条边，从G中删去边e之后得到的图称为G的删边子图，记为eG。一般地，设teeeT,,,21是G=（V，E）的边集E的子集，则G-T就是从G中删去T中的全部边以后得到的图。图4-1-1.10是删边子图的例子。图4-1-1.10点诱导子图。设G=（V，E）是一个图，VS，则),()(ESSG是一个以S为结点集，以EuvSvuuvE,,为边集的图，称为G的点诱导子图。图4-1-1.11是点诱导子图的一个例子。G-{e1,e2}Ge1e2vGG-v8图4-1-1.11边诱导子图。设G=（V，E）是一个图，ET并且T，则G（T）是一个以T为边集，以T中各边关联的全部结点为结点集的图，称为G的边诱导子图。例如图4-1-1.11中点诱导子图),(21vvG也可以看成是边诱导子图),,(321eeeG。2．补图定义4-1-1.5设),(EVG和),(EVG是两个简单图。若EuvVuvuvEVV,,,，即边Euv当且但当Euv，则称G是G的补图。显然，G可以看成是某完全图nK的删边子图EKn。图4-1-1.12是一个图及其补图的例子。图4-1-1.12上面定义过的删点子图、删边子图、点诱导子图和边