第四篇图论
自从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 和2
e 3v 4
u 2 u 5
u 6
4 v
2
3 v
是相互邻接的。
二、图的变体
若在定义4-1-1.1中去掉边集E中“不含重复元素”的限制条件，则得到多重图的定义。在多重图中，允许两条或两条以上的边与同一对结点关联，这些边称为平行边。由于可能有多条边与同一个结点对相关联，为区别起见，有时也对各边加以编号。图4-1-1.3是多重图的一个例子。
若在多重图的基础上，进一步去掉边是由不同结点的无序对表示的条件，即允许形如uu
e=的边（称为环）存在，则得到广义图或伪图的定义。图4-1-1.4是伪图的一个例子。
图4-1-1.3 图4-1-1.4
为了区别于多重图和伪图，以后称满足定义4-1-1.1的图为简单图。很明显，将多重图和伪图中的平行边代之以一条边，去掉环，就可以得到一个简单图。这样得到的简单图称为原来图的基图。在研究某些图论问题，如连通，点着色，点独立集，哈密顿图和平面性问题时只要考虑对应的基图就行了。因此，简单图将是本课程的主要讨论对象。“图”将作为一个概括性的词加以使用。
另外，有向图也是极重要的研究对象，在计算机科学中尤其有用。只要在定义4-1-1.1中把“无序对”换成“有序对”就得到了有向图的定义。有向图的“边”用形如)
,(v
u
e=的序偶表示，其意义是e是一条由结点u指向结点v的有向边，并且称e是u的出边，是v的入边。自然，),(v
u和)
,(u
v是不同的边。
类似于图定义的扩充，也可以定义出相应的多重有向图和有向伪图，并把上面定义的有向图相应称为简单有向图。“有向图”将作为概括性的词加以使用。图
v
v
25
4-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 ）—图∑∈==V
v m v d E V G 2)(),,(。即点度之和等于边数的两倍。
证明： 根据点度的定义，在计算点度时每条边对于它所关联的结点被计算了两次。因此，G 中点度的总和恰为边数m 的2倍。
推论 9—1.1.1 在任何图中，奇数度的结点数必是偶数。
证明 设V 1和V 2分别是图G 的奇度结点集和偶度结点集。由定理4-1-1.1应有∑∑∈∈=+2
12)()(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 V
v V v ==-∈+∈∑∑)()(。 证明：任何一条有向边，在计算点度时提供一个出度和一个入度。因此，任意有向图出度之和等于入度之和等于边数。
四、基本图例
图中度为零的结点称为孤立结点。
只由孤立结点构成的图),(Φ=V G 称为零图，特别地，只由一个孤立结点构成的图称为平凡图。
各点度相等的图称为正则图。特别地，点度为k 的正则图又称为k 度正则图。显然，零图是零度正则图。
任何两个结点都相互邻接的简单图称为完全图。n 阶的完全图是))1(2
1,(-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 1
K 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 的子图。特别地，当12V V =时，称H 是G 的生成子图；当12E E ?或12V V ?时，称H 是G 的真子图；当12V V =且12E E =或Φ=2E 时，称H 是G 的平凡子图。
由一个图产生其子图的方法。
删点子图。设v 是图G 的一个结点，从G 中删去结点v 及其关联的全部边以后得到的图，称为G 的删点子图，记为G-v ，图4-1-1.9是图G 及其删点子图的例子。一般地，设},,,{21k v v v S =是),(E V G =的结点集V 的子集，则},,,{21k v v v G -就是从G 中删去结点k v v v ,,,21 以及它们关联的全部边后得到
的G 的删点子图，也可以简记为G-S 。
图4-1-1.9
删边子图。设e 是图G 的一条边，从G 中删去边e 之后得到的图称为G 的删边子图，记为e G -。一般地，设{}t e e e T ,,,21 =是G=（V ，E ）的边集E 的
子集，则G-T 就是从G 中删去T 中的全部边以后得到的图。图4-1-1.10是删边
子图的例子。G G-v
图4-1-1.10
点诱导子图。设G=（V ，E ）是一个图，V S ?，则),()(E S S G '=是一个以S 为结点集，以{}E uv S v u uv E ∈∈=',,为边集的图，称为G 的点诱导子图。图4-1-1.11是点诱导子图的一个例子。
图4-1-1.11
边诱导子图。设G=（V ，E ）是一个图，E T ?并且Φ≠T ，则G （T ）是一个以T 为边集，以T 中各边关联的全部结点为结点集的图，称为G 的边诱导子图。例如图4-1-1.11中点诱导子图{}),(21v v G 也可以看成是边诱导子图{}),,(321e e e G 。
2．补图
定义4-1-1.5 设),(E V G 和),(E V G ''=是两个简单图。若
{}E uv V u v uv E V V ?∈='=',,,，即边E uv '∈当且但当E uv ?，则称G 是G 的补图。 显然，G 可以看成是某完全图n K 的删边子图E K n -。图4-1-1.12是一个图及其补图的例子。
G-{e 1,e 2
}
G G
e e 3 2
v G({v 1,v 2})
图 4-1-1.12
上面定义过的删点子图、删边子图、点诱导子图和边诱导子图，对于有向图同样适用。
六、图的同构
一个图的图形表示不一定是唯一的，但有很多表面上看来似乎不同的图却可以有着极为相似图形表示，这些图之间的差别仅在于结点和边的名称的差异，而从邻接关系的意义上看，它们本质上都是一样的，可以把它们看成是同一个图的不同表现形式。这就是图的同构概念。
定义 4-1-1.6 设),(E V G =和),(E V G ''='是两个图，如果存在双射
V V '→:?，使得E v u E uv '∈?∈)()(??，则称G 和G '同构，并记之为G G '?。
这个定义也适用于有向图，只须在边的表示法中作相应的代换就行了。 图4-1-1.13中两个图形代表的图是同构的。因为存在着双射?，使5,81()(3≠≤≤=+i i u v i i ?，这里下标是在mod8的意义下确定的），15)(u v =?。
图 4-1-1.13
一般说来，要判定两个图是否同构是非常困难的，尚无一个简单的方法可以
v 1 v 2 v 3
4
5
6v 1 v 23 v 4
v 56 G
G v
2 3 425u 4
u 1 u 3
u 6 78
通用。
但在某些情况下可根据同构的必要条件有效地排除不同构的情况。根据定义，同构的图除了有相同的结点数和边数外，对应的结点度数也必须相同，不满足这些条件的图不可能同构。例如图4-1-1.14中的两个图不是同构的。因为如果两图同构，两个无环的4度结点必须对应。但左图的4度结点的邻接结点，其结点度都不小于3，而右图的4度结点却有一个2度的邻接结点，因此不可能建立起双射。
图 4-1-1.14
容易知道，图的同构关系是图集上的等价关系。凡是同构的图将不予区别，只须考虑等价类中的代表元。由于我们感兴趣的主要是图的结构性质，在大多数情况下，不再标出图的全部结点名称和边的名称。
4-1-1 习 题
1．设G 是一个（n ,m ）简单图，证明2n C m ≤，等号成立当且仅当G 是完全图。
2．证明在不少于两人的一群人中，至少有两个人在这群人中有相同数目的朋友。
3．确定下面的序列中哪些是图的序列？若是图的序列，画出一个对应的图来。
（1）（3，2，0，1，5）； （2）（6，3，3，2，2）；
（3）（4，4，2，2，4）； （4）（7，6，8，3，9，5）
4．在(n ，m )－图中，证明恒有?≤≤n
m 2δ。 5．证明在竞赛图G =（V ，E ）中22))(())((v d v d V u V v +∈-∈∑∑=。
离散数学图论与系中有图题目
————————————————————————————————作者：————————————————————————————————日期：
图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Powell 给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第1步、 将图的结点按度数的非增顺序排列；第2步、用第1种颜色给第1个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。 例1 分别求右面两图的色数 （1）由于（1）中图G 中无奇数长的基本回路，由定理可知()2G χ=。 （2）由于（2）中图G 含子图轮图4W ，由于()44W χ=，故()4G χ≥。又因 为此图的最大度()4G ?=，G 不是完全图，也不是奇数长的基本回路，由定理可知()()4G G χ≤?=，因而()4G χ=。 （对n 阶轮图n W ，n 为奇数时有()3n W χ=，n 为偶数时有()4n W χ=；对n 阶零图n N ，有()1n N χ=；完全图n K ，有()n K n χ=；对于二部图12,,,G V V E E =<>=Φ时即()1n N χ=，E ≠Φ时即()2G χ=；在彼得森图G 中，存在奇数长的基本回路，因而()3G χ≥，又彼得森图既不是完全图也不是长度为奇数的基本回路，且()3G ?=，由定理()3G χ≤，故()3G χ=） 例 2 给右边三个图的顶点正常着 色，每个图至少需要几种颜色。 答案：（1） ()2G χ=；（2） ()3G χ=； （3）()4G χ= 例3 有8种化学品A,B,C,D,P,R,S,T 要放进贮藏室保管。出于安全原因， 下列各组药品不能贮在同一个室内：A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B, 4个结点、6个结点和8个结点的三次正则图 (2) (1) (3) (2)(1)
离散数学图论单元测验题 一、单项选择题(本大题共10小题，每小题2分，共20分) 1、在图G ＝
图论练习题 一.选择题 1、设G是一个哈密尔顿图，则G一定是( )。 (1) 欧拉图(2) 树(3) 平面图(4)连通图 2、下面给出的集合中，哪一个是前缀码？() (1) {0，10，110，101111}(2) {01，001，000，1} (3) {b，c，aa，ab，aba}(4) {1，11，101，001，0011} 3、一个图的哈密尔顿路是一条通过图中()的路。 4、设G是一棵树，则G 的生成树有( )棵。 (1) 0(2) 1(3) 2(4) 不能确定 5、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。 6、一棵无向树的顶点数n与边数m关系是()。 7、一个图的欧拉回路是一条通过图中( )的回路。 8、有n个结点的树，其结点度数之和是()。 9、下面给出的集合中，哪一个不是前缀码( )。 (1) {a，ab，110，a1b11} (2) {01，001，000，1} (3) {1，2，00，01，0210} (4) {12，11，101，002，0011} 10、n个结点的有向完全图边数是( )，每个结点的度数是( )。 11、一个无向图有生成树的充分必要条件是( )。 12、设G是一棵树，n,m分别表示顶点数和边数，则 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。 13、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( )片树叶。 14、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。 15、设G是有n个结点m条边的连通平面图，且有k个面，则k等于: (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。 16、设T是一棵树，则T是一个连通且( )图。 17、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16 18、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 12
离散数学11春图论部分综合练习辅导 大家好！本学期的第二次教学辅导活动现在开始，本次活动主要是针对第二单元图论的重点学习内容进行辅导，方式同样是通过讲解一些典型的综合练习作业题目，帮助大家进一步理解和掌握图论的基本概念和方法． 图论作为离散数学的一部分，主要介绍图论的基本概念、理论与方法．教学内容主要有图的基本概念与结论、图的连通性与连通度、图的矩阵表示、最短路问题、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用等． 本次综合练习主要是复习这一单元的主要概念与计算方法，与集合论一样，也安排了五种类型，有单项选择题、填空题，判断说明题、计算题、证明题．这样的安排也是为了让同学们熟悉期末考试的题型，能够较好地完成这一部分主要内容的学习． 下面是本学期第4，5次形考作业中的部分题目． 一、单项选择题 单项选择题主要是第4次形考作业的部分题目． 第4次作业同样也是由10个单项选择题组成，每小题10分，满分100分．在每次作业在关闭之前，允许大家反复多次练习，系统将保留您的最好成绩，希望大家要多练几次，争取好成绩．需要提醒大家的是每次练习的作业题目可能不一样，请大家一定要认真阅读题目． 1．设图G ＝
第四篇图论 自从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）分别简
离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝
图三 7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( )． 图四 A ．（a ）是强连通的 B ．（b ）是强连通的 C ．（c ）是强连通的 D ．（d ）是强连通的 应该填写：D 8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )． A ．G 连通且边数比结点数少1 B ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 D ．G 中没有回路． 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结 点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 ? ? ? ? ? c a b e d ? f 图四
图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Powell 给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第1步、 将图的结点按度数的非增顺序排列；第2步、用第1种颜色给第1个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。 例1 分别求右面两图的色数 （1）由于（1）中图G 中无奇数长的基本回路，由定理可知()2G χ=。 （2）由于（2）中图G 含子图轮图4W ，由于()44W χ=，故()4G χ≥。又因 为此图的最大度()4G ?=，G 不是完全图，也不是奇数长的基本回路，由定理可知()()4G G χ≤?=，因而()4G χ=。 （对n 阶轮图n W ，n 为奇数时有()3n W χ=，n 为偶数时有()4n W χ=；对n 阶零图n N ，有()1n N χ=；完全图n K ，有()n K n χ=；对于二部图12,,,G V V E E =<>=Φ时即()1n N χ=，E ≠Φ时即()2G χ=；在彼得森图G 中，存在奇数长的基本回路，因而()3G χ≥，又彼得森图既不是完全图也不是长度为奇数的基本回路，且()3G ?=，由定理()3G χ≤，故()3G χ=） 例 2 给右边三个图的顶点正常着 色，每个图至少需要几种颜色。 答案：（1） ()2G χ=；（2） ()3G χ=； （3）()4G χ= 例3 有8种化学品A,B,C,D,P,R,S,T 要放进贮藏室保管。出于安全原因， 下列各组药品不能贮在同一个室内：A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B, 4个结点、6个结点和8 个结点的三次正则图 (2) (1) (3) (2) (1)
第八章图论 例1、下面哪些数的序列,可能是一个图的度数序列?如果可能,请试画出它的图. 哪些可能不是简单图?a) (1,2,3,4,5) b) (2,2,2,2,2) c) (1,2,3,2,4) d) (1,1,1,1,4) e) (1,2, 2,4,5) 解:a)不是, 因为有三个数字是奇数. b) c) d)是. e) 不是简单图,因为它有5个结点, 有一个结点度为5, 必然有环或平行边. 例2、已知无向简单图G中,有10条边,4个3度结点,其余结点的度均小于或等于2,问G中至少有多少个结点?为什么? 解:已知边数|E|=10, ∑deg(v)=2|E|=20其中有4个3度结点, 余下结点度之和为: 20-3×4=8 因为G是简单图, 其余每个结点度数≤2, 所以至少还有4个结点.所以G中至少有8个结点. 强连通、单侧连通和弱连通 在简单有向图G中,如果任何两个结点间相互可达, 则称G是强连通. 如果任何一对结点间, 至少有一个结点到另一个结点可达, 则称G是单侧连通. 如果将G看成无向图后(即把有向边看成无向边)是连通的,则称G是弱连通. 在简单有向图中,具有强连通的最大子图,称为强分图.具有单侧连通的最大子图,称为单侧分图. 具有弱连通的最大子图,称为弱分图. 注：我每次都会被各种分图弄糊涂！！考试时要注意啊，千万不要错了 利用可达性矩阵求强分图，注意初等矩阵变换的知识不要忘了！！ 令图G=
离散数学图论部分综合练习 1．设图G ＝
总 结 第八章 图论 8.1 图的基本概念 8.1.1 图 定义8.1―1 一个图G 是一个三重组〈V (G ),E (G ),ΦG 〉,其中V (G )是一个非空的结点(或叫顶点)集合,E (G )是边的集合,ΦG 是从边集E 到结点偶对集合上的函数。一个图可以用一个图形表示。 定义中的结点偶对可以是有序的,也可以是无序的。若边e 所对应的偶对〈a ,b 〉是有序的,则称e 是有向边。有向边简称弧,a 叫弧e 的始点,b 叫弧e 的终点,统称为e 的端点。称e 是关联于结点a 和b 的,结点a 和结点b 是邻接的。若边e 所对应的偶对(a ,b )是无序的,则称e 是无向边。无向边简称棱,除无始点和终点的术语外,其它术语与有向边相同 每一条边都是有向边的图称为有向图。每一条边都是无向边的图称为无向图。 有向图和无向图也可互相转化。例如,把无向图中每一条边都看作两条方向不同的有向边,这时无向图就成为有向图。又如,把有向图中每条有向边都看作无向边,就得到无向图。这个无向图习惯上叫做该有向图的底图。 在图中,不与任何结点邻接的结点称为弧立结点。全由孤立结点构成的图称为零图。关联于同一结点的一条边称为自回路。 在有向图中,两结点间(包括结点自身间)若同始点和同终点的边多于一条,则这几条边称为平行边。在无向图中,两结点间(包括结点自身间)若多于一条边,则称这几条边为平行边。两结点a 、b 间互相平行的边的条数称为边［a ,b ］的重数。仅有一条时重数为1,无边时重数为0。 定义8.1―2 含有平行边的图称为多重图。非多重图称为线图。无自回路的线图称为简单图。仅有一个结点的简单图称为平凡图。 定义 8.1―3 赋权图G 是一个三重组〈V ,E ,g 〉或四重组〈V ,E ,f ,g 〉,其中V 是结点集合, E 是边的集合,f 是定义在V 上的函数,g 是定义在E 上的函数。 8.1.2 结点的次数 定义 8.1―4 在有向图中,对于任何结点v ,以v 为始点的边的条数称为结点v 的引出次数(或出度),记为deg +(v );以v 为终点的边的条数称为结点v 的引入次数(或入度),记为deg -(v );结点v 的引出次数和引入次数之和称为结点v 的次数(或度数),记作deg (v )。在无向图中,结点v 的次数是与结点v 相关联的边的条数,也记为deg (v )。孤立结点的次数为零。 定理8.1―1 设G 是一个(n ,m )图,它的结点集合为V ={v 1,v 2,…,v n},则 定理8.1―2 在图中,次数为奇数的结点必为偶数个。 定义8.1―5 各结点的次数均相同的图称为正则图,各结点的次数均为k 时称为k ―正则图。 8.1.3 图的同构 定义8.1.6 设G =〈V ,E 〉和G ′=〈V ′,E ′〉是两个图,若存在从V 到V ′的双射函数1deg()2n i i m υ==∑
作业答案：图论部分 P165:习题九 1、 给定下面4个图（前两个为无向图，后两个为有向图）的集合表示，画出它们的图形表 示。 （1）111,G V E =<>，112345{,,,,}V v v v v v =，11223343345{(,),(,),(,),(,),(,)}E v v v v v v v v v v = （2）222,G V E =<>，21V V =，11223344551{(,),(,),(,),(,),(,)}E v v v v v v v v v v = （3）13331,,,D V E V V =<>=31223324551{,,,,,,,,,}E v v v v v v v v v v =<><><><><> （4）24441,,,D V E V V =<>=31225523443{,,,,,,,,,}E v v v v v v v v v v =<><><><><> 解答： （1） （2） 10、是否存在具有下列顶点度数的5阶图？若有，则画出一个这样的图。 （1）5，5，3，2，2；（2）3，3，3，3，2；（3）1，2，3，4，5；（4）4，4，4，4，4 解答：（1）（3）不存在，因为有奇数个奇度顶点
。 14、设G 是(2)n n ≥阶无向简单图，G 是它的补图，已知12(),()G k G k δ?==，求()G ?， ()G δ。 解答：2()1G n k ?=--；1()1G n k δ=--。 15、图9.19中各对图是否同构？若同构，则给出它们顶点之间的双射函数。 解答： （c ）不是同构，从点度既可以看出，一个点度序列为4，3，3，3，3而另外一个为4，4，3，3，1 （d ）同构，同构函数为 12()3 45 x a x b f x x c x d x e =??=??==??=?=?? 16、画出所有3条边的5阶简单无向图和3条边的3阶简单无向图。 解答： （1）三条边一共提供6度；所以点度序列可能是 ①3，3，0，0，0，0；②3，2，1，0，0，0；③3，1，1，1，0，0；④2，2，2，0，0，0；⑤2，2，1，1，0，0；⑥2，1，1，1，1，0；⑦1，1，1，1，1，1； 由于是简单图，①②两种情形不可能 图形如下：