图论

图论

内容提要

第一章 图的基本概念

图的基本概念；二部图及其性质；图的同构；关联矩阵与邻接矩阵。 路、圈与连通图；最短路问题。 树及其基本性质；生成树；最小生成树。

第二章 图的连通性

割点、割边和块；边连通与点连通；连通度；Whitney定理；可靠通信网络的设计。

第三章 匹配问题

匹配与最大匹配；完美匹配；二部图的最大匹配；指派问题与最大权匹配。

第四章 欧拉图与哈密尔顿图

欧拉图；中国邮递员问题；哈密尔顿图；旅行商问题。

第五章 支配集、独立集、覆盖集与团

支配集、点独立集、点覆盖集、边覆盖集与团的概念及其求法。

第六章 图的着色问题

点着色；边着色；平面图；四色猜想；色多项式；色数的应用。

第七章 网络流理论

有向图；网络与网络流的基本概念；最大流最小割定理；求最大流的标号算法；最小费用流问题；最小费用最大流；网络流理论的应用。

主要参考书

[1] J.A. Bondy and U.S. Murty, Graph theory with applications, 1976, 有中译本（吴望名等译）。 [2] B.Bollobas, Modern graph theory (现代图论)，科学出版社，2001。 [

一、选择题（每小题2分，共50分）

1、设D??V,E?为有向图，则有（ A ）

(A) E?V?V (B) E?V?V (C)V?V?E (D) V?V?E

2、设G??V,E?为无环的无向图，V＝6，E?16，则G 是（D ）

(A) 完全图 (B) 零图 (C) 简单图 (D) 多重图

3、含有5个结点，3条边的不同构的简单图有（ C ）

(A) 2个 (B) 3个 (C) 4个 (D) 5个

4、设图G有n个结点，m条边，且G中每个结点的度数不是k就是k?1，则G中度为k的结点的个数是（ D ）

(A) n/2个 (B) n(n?1)个 (C)nk个 (D) n(k?1)?2m个

5、给定下列序列，哪一个可以构成无向简单图的结点度数序列（ B ）

(A) (1,1,2,2,3)

图 论

第一节 图的基本概念

引入：柯尼斯堡七桥问题，能否从A地发出，各座桥恰好通过一次，最后回到出发地A？

结论：1736年，数学家欧拉首先解决了这个问题，由此开创了图论研究。这事实上是欧拉图的“一笔画问题”。答案是否定的，因为，对于每一个顶点，不论如何经过，必须有一条进路和一条出路，与每一个顶点相邻的线（关联边）必须是偶数条（除起点和终点外），而此图中所有点都只有奇数条关联边。在后面的应用中，我们将专门讨论这个问题。 定义：简单讲，一个图是由一些点和这些点之间的连线组成的。严格意义讲，图是一种数据结构，定义为：graph=（V，E）。V是一个非空有限集合，代表顶点（结点），E代表边的集合，一般用（Vx，Vy）表示，其中，Vx，Vy属于V。

分类：如果边是没有方向的，称为“无向图”。表示时用一队圆括号表示，如：（Vx，Vy），（Vy，Vx），当然这两者是等价的。并且说边（Vx，Vy）依附于（相关联）顶点Vx和Vy。 如果边是带箭头的，则称为“有向图”，表示时用一队尖括号表示，此时与是不同的，如的起点为VX，终点为VY。有向图中的边又称为弧。起点称为弧头、终点称为弧尾。

相邻：若两个结点U、V之间有一条边连接，则称这两个结

第十二章 图论在数学建模中的应用

图论是数学的一个既有古老的历史渊源而又十分年轻的分支，是一门生气勃勃、

广大前途的学科。它既很强的理论性，与数学的一些分支如数论、几何学及运筹学等都有密切联系，又有广泛的应用价值，图论在化学、统计学、生物学、信息论、计算机科学中都有很强的实际应用背景，并且饶有趣味，引人入胜。图论方法是建立数学模型的重要方法之一。利用图论知识，通过建立图论模型，解决实际问题是学习图论课程的重要目的之一。本章我们通过大量的实例，系统介绍如何利用图论知识建立数学模型，解决实际问题的基本方法和技巧，培养分析问题、解决问题的能力。

12.1图论在数学建模中的一些简单应用

本节将通过对在社会生产活动中有很强实际应用背景的一些简单实例的分析，展示如何利用图论知识，通过数学建模方法将实际问题转化为图论问题加以解决的基本方法和技巧。

例1.相识问题

1958年美国《数学月刊》发表了一个数学问题：在6人的集会上，总能找到或者3个人互相都认识，或者3个人谁也不认识谁，假定认识是相互的。 这个表面看来似乎无法下手的问题，可以通过图论法轻易获得解决。 分析与建模：用6个点（记为u1,u2,?,u6）表示6个人，若两个人互相认识，就在相应的两个点之间

一、图论的基础概念

以下概念不是定义，也不一定完全，只是一些常用的概念，比较通俗化。在以后具体的算法中再适当加入概念。

图： 由点和线组成的图形。 顶点： 图中的结点。

无向图： 边没有正反方向。

完全图： 在N个顶点的无向图中，边最大为n*（n-1）/2称为无向完全图 度： 与结点相连的边数。 有向图： 边有正反方向。

入度（出度）：连入（出）的边数。（对于有向图来说） 奇顶点：结点的度是奇数的点。

路径：如果从a到b可达（包括直接到达或者中间有其他结点）那么从a到b就有一条路径。一条路径就

是一种走法，路径的边数叫做路径长度。一条路径上的n个顶点的集合叫做连通集。

回路（环）：从a?b????a

简单路径：存在从a?b???e此条路径中每个结点不同。

有根图：有结点到其他任意结点连通，则此结点为根，一个图可以有多根。 连通图：若图中任意两个结点可以连通，则此图为连通图（无向图）。 强连通图：任意i到j都有从i到j的路径。（有向图） 强连通分支：强连通的最大子图。

道路：可以一笔画成的图，并且不重不漏。

*充分必要条件：图是连通的，且奇顶点的个数等于0或2

并且当且仅当

图 论

第一节 图的基本概念

引入：柯尼斯堡七桥问题，能否从A地发出，各座桥恰好通过一次，最后回到出发地A？

结论：1736年，数学家欧拉首先解决了这个问题，由此开创了图论研究。这事实上是欧拉图的“一笔画问题”。答案是否定的，因为，对于每一个顶点，不论如何经过，必须有一条进路和一条出路，与每一个顶点相邻的线（关联边）必须是偶数条（除起点和终点外），而此图中所有点都只有奇数条关联边。在后面的应用中，我们将专门讨论这个问题。 定义：简单讲，一个图是由一些点和这些点之间的连线组成的。严格意义讲，图是一种数据结构，定义为：graph=（V，E）。V是一个非空有限集合，代表顶点（结点），E代表边的集合，一般用（Vx，Vy）表示，其中，Vx，Vy属于V。

分类：如果边是没有方向的，称为“无向图”。表示时用一队圆括号表示，如：（Vx，Vy），（Vy，Vx），当然这两者是等价的。并且说边（Vx，Vy）依附于（相关联）顶点Vx和Vy。 如果边是带箭头的，则称为“有向图”，表示时用一队尖括号表示，此时与是不同的，如的起点为VX，终点为VY。有向图中的边又称为弧。起点称为弧头、终点称为弧尾。

相邻：若两个结点U、V之间有一条边连接，则称这两个结

图论复习题

第一章 图

主要内容：

1．图的基本概念和基本定理（重点是完全图、二部图、图的同构、握手定理等） 2．轨道和圈（最长轨理论）

练习题目：

1．5阶无向完全图的边数为__10_____。

2．图G1和G2的结点和边分别存在一一对应关系是G1和G2同构的_充分必要条件

______。

3．图G1和G2的结点和边分别存在一一对应关系是G1和G2同构的_充分必要条件

______。

4．设无向简单图的顶点个数为n，则该图最多有_n(n-1)/2_ 条边。

5．一个有n个结点的图，最少有___1____个连通分支。

6．有三个顶点的所有互不同构的简单无向图有___4____个。

7．单连通无向图G有12条边，G中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3．求G中有多少个结点．试作一个满足该条件的简单无向图． 解：设G中有x各结点，则3度的结点有x-7 根据握手定理有，1x2+2x2+4x3+3x(x-7)=2x12 解得x=9,故G中有9个结点。 满

足

条

件

的

图

如

下

：

8．单连通无向图G有9条边，G中有4个3度结点，2个1度结点，其余结点度数为2．求G中有多少个结点．试作一个满足该条件的简单无向图．

离散数学图论部分综合练习辅导

图论作为离散数学的一部分，主要介绍图论的基本概念、理论与方法。教学内容主要有图的基本概念与结论、图的连通性与连通度、图的矩阵表示、最短路问题、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用等。

本次综合练习主要是复习这一部分的主要概念与计算方法，与集合论一样，也安排了五种类型，有单项选择题、填空题，判断说明题、计算题、证明题。这样的安排也是为了让同学们熟悉期末考试的题型，能够较好地完成这一部分主要内容的学习。下面分别讲解。

一、单项选择题 1．设图G的邻接矩阵为

?0?0??1??0??00001110000010010??1?0? ?1?0??

则G的边数为( )．

A．5 B．6 C．3 D．4 正确答案：D

上学期的作业中，有的同学选择答案B。主要是对邻接矩阵的概念理解不到位。我们复习定义：

定义3.3.1 设G=是一个简单图，其中V={v1，v2，?， vn}，则 n阶方阵A（G）=（aij）称为G的邻接矩阵．其中各元素

aij??1????0vi与vj相邻vi与vj不相邻或i?j

而当给定的简单图是无向图时，邻

图论及网络总复习题

一、选择题

1、设G是由5个顶点构成的完全图，则从G中删去（ ）边可以得到树。 A．6 B．5 C．8 D．4 2、下面哪几种图不一定是树（ ）。 A．无回路的连通图

B．有n个结点，n-1条边的连通图 C．对每对结点间都有通路的图

D．连通但删去任意一条边则不连通的图。 3、5阶无向完全图的边数为（ ）。

A．5 B．10 C．15 D．20 4、把平面分成x个区域，每两个区域都相邻，问x最大为（ ） A．6 B．4 C．5 D．3

5、设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是（ ）

A．n/2 B．n(n+1) C．nk-2m D．n(k+1)-2m 6、图G1和G2的结点和边分别存在一一对应关系是G1和G2同构的（ ）。

A．充分条件 B．必要条件 C．充

图和子图 图

图 G = (V, E)， 其中 V = {v1,v2,......,v?} V ---顶点集，

E = {e1,e2,......,e?}

?---顶点数

E ---边集， ?---边数

例。 左图中， V={a, b,......,f}, E={p,q, ae, af,......,ce, cf} 注意， 左图仅仅是图G的几何实现（代表）， 它们有无穷多个。真正的 图G 是上面所给出式子，它与顶点的位置、边的形状等无关。不过今后对两者将经常不加以区别。

称 边 ad 与顶点 a (及d) 相关联。也称 顶点 b(及 f) 与边 bf 相关联。

称顶点a与e 相邻。称有公共端点的一些边彼此相邻，例如p与af 。

环（loop，selfloop）：如边 l。 棱（link）：如边ae。 重边：如边p及边q。 简单图：（simple graph）无环，无重边 平凡图：仅有一个顶点的图（可有多条环）。 一条边的端点：它的两个顶点。 记号：?(G)?V(G),?(G)?E(G).。

习题

1.1.1 若G为简单图，则

a