图论基础
第一讲图论基础知识
自从1736年欧拉（L.Euler）利用图论的思想解决了哥尼斯堡（Konigsberg）七桥问题以来，图论经历了漫长的发展道路。在很长一段时期内，图论被当成是数学家的智力游戏，解决一些著名的难题。如迷宫问题、匿门博奕问题、棋盘上马的路线问题、四色问题和哈密顿环球旅行问题等，曾经吸引了众多的学者。图论中许多的概论和定理的建立都与解决这些问题有关。
1847年克希霍夫（Kirchhoff）第一次把图论用于电路网络的拓扑分析，开创了图论面向实际应用的成功先例。此后，随着实际的需要和科学技术的发展，在近半个世纪内，图论得到了迅猛的发展，已经成了数学领域中最繁茂的分支学科之一。尤其在电子计算机问世后，图论的应用范围更加广泛，在解决运筹学、信息论、控制论、网络理论、博奕论、化学、社会科学、经济学、建筑学、心理学、语言学和计算机科学中的问题时，扮演着越来越重要的角色，受到工程界和数学界的特别重视，成为解决许多实际问题的基本工具之一。
图论研究的课题和包含的内容十分广泛，专门著作很多，很难在一本教科书中概括它的全貌。作为离散数学的一个重要内容，本书主要围绕与计算机科学有关的图论知识介绍一些基本的图论概论、定理和研究内容，同时也介绍一些与实际应用有关的基本图类和算法，为应用、研究和进一步学习提供基础。
第1章无向图和有向图
学习要求：仔细领会和掌握图论的基本概论、术语和符号，对于图论研究的一些最基本的课题，如道路问题、连通性问题和着色的问题等，应掌握主要的定理内容和证明方法以及基本的构造方法，以便为下一章研究提供理论工具。学习本章要用到集合和线性代数矩阵运算的知识，特别是集合数和矩阵秩的概念。
§4-1-1 图的基本概念
图是用于描述现实世界中离散客体之间关系的有用工具。在集合论中采用过以图形来表示二元关系的办法，在那里，用点来代表客体，用一条由点a指向点b的有向线段来代表客体a和b之间的二元关系aRb，这样，集合上的二元关系就可以用点的集合V和有向线的集合E构成的二元组（V，E）来描述。同样的
方法也可以用来描述其它的问题。当我们考察全球航运时，可以用点来代表城市，用线来表示两城市间有航线通达；当研究计算机网络时，可以用点来表示计算机及终端，用线表示它们之间的信息传输通道；当研究物质的化学结构时，可以用点来表示其中的化学元素，而用线来表示元素之间的化学键。在这种表示法中，点的位置及线的长短和形状都是无关紧要的，重要的是两点之间是否有线相连。从图形的这种表示方式中可以抽象出图的数学概念来。
一、图
定义1-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 为端点的联线表示。图1-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 )
图1-1-1.1
须注意，一个图的图形表示法可能不是唯一的。表示结点的圆点和表示边的线，它们的相对位置是没有实际意义的。因此，对于同一个图，可能画出很多表面不一致的图形来。例如图1-1-1.1的（a ）图还可以有图9—1.2中的两种图形表示。
3v 4
u 2
u 5
u 6
图1-1-1.2
图G 的结点数称为G 的阶，用字母n 的表示。G 的边数用m 表示，也可以表示成m G E =)(。一个边数为m 的n 阶图可简称为（n ，m ）—图。如图1-1-1.1的（a ）和（b ）分别表示一个（4，6）—图和一个（6，4）—图。
若uv e =是图G 的一条边，则称结点u 和v 是相互邻接的，并且说边e 分别与u 和v 相互关联。若G 的两条边1e 和2e 都与同一个结点关联时，称1e 和2e 是相互邻接的。
二、图的变体
若在定义1-1-1.1中去掉边集E 中“不含重复元素”的限制条件，则得到多重图的定义。在多重图中，允许两条或两条以上的边与同一对结点关联，这些边称为平行边。由于可能有多条边与同一个结点对相关联，为区别起见，有时也对各边加以编号。图1-1-1.3是多重图的一个例子。
若在多重图的基础上，进一步去掉边是由不同结点的无序对表示的条件，即允许形如uu e =的边（称为环）存在，则得到广义图或伪图的定义。图1-1-1.4是伪图的一个例子。
图1-1-1.3
图1-1-1.4
为了区别于多重图和伪图，以后称满足定义1-1-1.1的图为简单图。很明显，将多重图和伪图中的平行边代之以一条边，
去掉环，就可以得到一个简单图。这样得到的简单图称为原来图的基图。在研究某些图论问题，如连通，点着色，点独立集，哈密顿图和平面性问题时只要考虑对应的基图就行了。因此，简单图将是本课程的主要讨论对象。“图”将作为一个概括性的词加以使用。
另外，有向图也是极重要的研究对象，在计算机科学中尤其有用。只要在定
v v 254
v 2
3
v
义1-1-1.1中把“无序对”换成“有序对”就得到了有向图的定义。有向图的“边”用形如),(v u e =的序偶表示，其意义是e 是一条由结点u 指向结点v 的有向边，并且称e 是u 的出边，是v 的入边。自然，),(v u 和),(u v 是不同的边。
类似于图定义的扩充，也可以定义出相应的多重有向图和有向伪图，并把上面定义的有向图相应称为简单有向图。“有向图”将作为概括性的词加以使用。图1-1-1.5中（a ）、（b ）和（c ）分别是简单有向图、多重有向图和有向伪图的例子。
(a
)
图1-1-1.5
有时也要考虑有向图的基图。一个有向图的基图是当去掉的边方向后得到的无向图（可以含有平行边和环）。
根据不同的应用，图的定义还有别的一些扩充形式，如权图、标号图、无限图、混合图、根图、超图等。
三、图论基本定理
下面将从数量方面去建立图的元素的基本关系。
定义 1-1-1.2 图G 中结点v 的度（简称点度）)(v d G 是G 中与v 关联的边的数目。每个环在计度时算作两条边。
图G 中最大的点度和最小的点度分别记为G ?和G δ。在不致引起混淆的地方，)(v d G ，G ?和G δ分别简写成)(v d ，?和δ。
在图1-1-1.4中 3,6,4)(,6)(,6)(,5)(,3)(54321==?=====δv d v d v d v d v d 。 由图中各结点的度构成的序列称为该图一个度序列。例如图1-1-1.4的一个度序列是（3，5，6，6，4）。度序列在某些图论专题中也是重要的研究工具。
下面介绍图论中最基本的定理，它是欧拉1736年在解决“Konigsberg 七桥问题”时建立的第一个图论结果，很多重要结论都与它有关。
定理1-1-1.1 （图论基本定理—握手定理）对于任何（n ，m ）—图
（b ）
(c)
∑∈==V
v m v d E V G 2)(),
,(。即点度之和等于边数的两倍。
证明： 根据点度的定义，在计算点度时每条边对于它所关联的结点被计算了两次。因此，G 中点度的总和恰为边数m 的2倍。
推论 9—1.1.1 在任何图中，奇数度的结点数必是偶数。
证明 设V 1和V 2分别是图G 的奇度结点集和偶度结点集。由定理1-1-1.1应有∑∑∈∈=+2
1
2)()(V v V v m v d v d 。
上式左端第二项是偶数之和，从而第一项必然也是偶数，即1V 必须是偶数。 在有向图中，点度的概念稍有不同。
定义 1-1-1.3 有向图G 中，结点v 的入度)(v d -是与v 关联的入边的数目，出度)(v d +是与v 关联的出边的数目。
有向图的最大出度、最大入度、最小出度、最小入度分别记为
-+-+??δδ、、、。
例 在图1-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 。
定理 1-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 。图1-1-1.6是常用的几个完全图。显然，n
K 是（n -1）度正则图。
图9—1.6
类似地，可以定义有向完全图。每对结点u 和v 之间皆有边（u ,v ）和（v ,u ）联结的简单有向图称为有向完全图。每对结点u 和v 之间恰有一条边（u ,v ）（或（v ,u ））联结的简单有向图称为竞赛图。图1-1-1.7（a ）是三阶有向完全图，（b ）是4阶的竞赛图。
图1-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 。图1-1-1.8中（a ）和（b ）都是二部图，其中(a )图的黑点属于一部，其余结点属于另一部，(b )图是3,3K ，其二部分划是明显的。
图1-1-1.8
五、子图与补图 1．子图
定义 4-1-1.4 设),(11E V G =和),(22E V H =是两个图，若满足12V V ?且
K 1
K 2 K 3 K 4 K 5
（a ）
（b ）
（a ） （b ）
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 ，图1-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 。
图1-1-1.9
删边子图。设e 是图G 的一条边，从G 中删去边e 之后得到的图称为G 的删边子图，记为e G -。一般地，设{}t e e e T ,,,21 =是G=（V ，E ）的边集E 的子集，则G-T 就是从G 中删去T 中的全部边以后得到的图。图1-1-1.10是删边子图的例子。
图1-1-1.10
点诱导子图。设G=（V ，E ）是一个图，V S ?，则),()(E S S G '=是一个以S 为结点集，以{}E uv S v u uv E ∈∈=',,为边集的图，称为G 的点诱导子图。图1-1-1.11是点诱导子图的一个例子。
G-{e 1,e 2
}
G
G
G-v
图1-1-1.11
边诱导子图。设G=（V ，E ）是一个图，E T ?并且Φ≠T ，则G （T ）是一个以T 为边集，以T 中各边关联的全部结点为结点集的图，称为G 的边诱导子图。例如图1-1-1.11中点诱导子图{}),(21v v G 也可以看成是边诱导子图
{}),,(321e e e G 。
2．补图
定义1-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 -。图1-1-1.12是一个图及其补图的例子。
图 1-1-1.12
上面定义过的删点子图、删边子图、点诱导子图和边诱导子图，对于有向图同样适用。
六、图的同构
一个图的图形表示不一定是唯一的，但有很多表面上看来似乎不同的图却可
G
e e 3
2 v G({v 1,v 2})
v 1
v 2
v 3
4
5
6v 1
v 23 v 4
v 56
G
G
以有着极为相似图形表示，这些图之间的差别仅在于结点和边的名称的差异，而从邻接关系的意义上看，它们本质上都是一样的，可以把它们看成是同一个图的不同表现形式。这就是图的同构概念。
定义 1-1-1.6 设),(E V G =和),(E V G ''='是两个图，如果存在双射V V '→:?，使得E v u E uv '∈?∈)()(??，则称G 和G '同构，并记之为G G '?。
这个定义也适用于有向图，只须在边的表示法中作相应的代换就行了。 图1-1-1.13中两个图形代表的图是同构的。因为存在着双射?，使5,81()(3≠≤≤=+i i u v i i ?，这里下标是在mod8的意义下确定的）
，15)(u v =?。
图 4-1-1.13
一般说来，要判定两个图是否同构是非常困难的，尚无一个简单的方法可以通用。但在某些情况下可根据同构的必要条件有效地排除不同构的情况。根据定义，同构的图除了有相同的结点数和边数外，对应的结点度数也必须相同，不满足这些条件的图不可能同构。例如图1-1-1.14中的两个图不是同构的。因为如果两图同构，两个无环的4度结点必须对应。但左图的4度结点的邻接结点，其结点度都不小于3，而右图的4度结点却有一个2度的邻接结点，因此不可能建立起双射。
图 4-1-1.14
容易知道，图的同构关系是图集上的等价关系。凡是同构的图将不予区别，只须考虑等价类中的代表元。由于我们感兴趣的主要是图的结构性质，在大多数
v 2
3
425u 4
u 1
u 3
u 6
78
情况下，不再标出图的全部结点名称和边的名称。
1-1-1 习 题
1．设G 是一个（n ,m ）简单图，证明2
n 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 +∈-∈∑∑=。
6．设G 是(n ，m )－简单二部图，证明4
2
n m ≤。
7．证明完全图的点诱导子图也是完全图。
8．若G ?，称G 是自补图。确定一个图为自补图的最低条件。画出一个自补图来。
9．判定图1-1-1.15中两衅是否同构。说明理由。
图1-1-1.15
10．证明图1-1-1.16中二图是同构的。
图1-1-1.16
12．k 方图是一个其结点对应对k 维的0，1元素向量，两结点邻接当且仅当对应的两个向量仅有一个坐标不同的图。证明k 方图有2k 个结点，k ·2k -1条边，并且是二部图。
13．如果存在n 阶简单图G=（V ，E ）的结点集V 的一个分划{V 1，V 2，…V k }，
其中每个)1(k j V j ≤≤的基数是??????k n 或)1)((,k j V G k n j ≤≤??
?
???都是零图，而j V 中每
个结点都与j V V -中的全部结点邻接，则称这样的图为完全k 部图，特记为n T k ,。
证明212)1(),(+--+=t t n k C k C n T ε，这里??
????=k n t 。 （注：[r ]和{r }分别表示实数r 的整数部分和不小于r 的最小整数。） 14．设{}n x x x S ,,,21 =是画在平面上的一组点，两两之间的距离不小于1，证明其间距离正好是1的点对数目不超过3n 。
§1-1-2 图的道路与连通性 一、道路
在图或有向图中，常常要考虑从确定的结点出发，沿结点和边连续地移动而到达另一确定的结点的问题。从这种由结点和边（或有向边）的序列的构成方式中可以抽象出图的道路概念。
定义 1-1-2.1 图（或有向图）G （V ，E ）中的非空序列k k v e e v e v p ,,2110 =，称为G 的一条由结点k u v 到0的道路（或有向道路），其中k v v v ,,,10 是G 的结点，k e e ,,1 是G 的边（或有向边），并且对所有的k i ≤≤1，边i e 与结点1-i v 和i v 都关联（或i e 是由1-i v 指向i v 的有向边）。
0v 称为道路p 的起点，k v 称为p 的终点，其余结点称p 为内部结点。p 中边的数目k 称为该道路的长度。以u 为起点、v 为终点的道路有时也简记为〈u ,v 〉
－道路。
对于由单个结点构成的序列0v p =，看成是道路的特殊情形，称为零道路，其长度为0。
注意：对有向图而言，这里定义的道路，其中各有向边的方向都是一致的。 根据序列的构成情况，可以对道路进一步分类。
若k v v ≠0，即起点与终点不同，则称p 为开道路，否则称为闭道路。 若p 中的边（有向边）互不相同，则称p 为简单道路。闭的简单道路称为回路。
若p 中的结点互不相同，则称p 为基本道路。若p 中除了起点和终点相同外，别无相同的结点，则称p 为圈。
图1-1-2.1(a )和(b )分别给出了图和有向图的各种道路的例子。 道路：45221343111v e v e v e v e v e v 简单道路：452443111v e v e v e v e v 回路：122443111v e v e v e v e v 基本道路：3624431v e v e v e v 圈：122637431v e v e v e v e v
有向道路：351746351v e v e v e v e v 有向简单道路：2223351v e v e v e v 有向回路：351122233v e v e v e v e v 有向基本道路：11233v e v e v 有向圈：3517463v e v e v e v
图1-1-2.1
这里需要特别指出的是，在实际应用中，有向图的道路和回路有两种不同的表现形式，一种是有向道路和有向回路，即上面定义的情形；另一种是普通意义的道路和回路，即不考虑方向时对应基图的一种道路和回路。例如图1-1-2.1(b)中143322211v e v e v e v e v 不是有向回路，但却是回路。后面将会遇到这种情形。
说明：对于简单图或简单有向图，由于每条边用结点对就能唯一表示，因此
v 3
4
(a )
34e 2
6(b )
一条道路k k v e e v e v p 2110=仅用结点列k v v v v p 210=表示就行了。即使对于非简单图，有时也用结点序列表示一条道路。
利用基本道路和圈可以定义两种特殊的图。若一个图能以一条基本道路表示出来，则称之为道路图。N 阶的道路图记为P n 。同样可以定义圈图，n 阶的圈图记为C n 。图1-1-2.2是P 5和C 6的例子。
图1-1-2.2
道路问题是图论中的重要内容，常常要涉及到具体有某种特征的道路存在性问题。
定理 1-1-2.1 如果在n 阶图中，存在从结点u 到v 的道路，则必存在从u 到v 的长度不超过n -1的道路。
证明： 设k v v v p 100=是一条从u 到v 的道路，其中v v u v k ==,0。若
1->n k ，则必有结点i v 在0p 中至少出现两次，即0p 中存在子序列
)(1i j i i i v v v v =++ 。从0p 中去掉子序列j i i i v v v +++ 21，得到一个新的序列k j i i v v v v v p 1101++=，则1p 长度k k <1。
若11,1p n k -≤便是所求道路；若11->n k ，对1p 重复上述讨论，可构造出道路序列0p ，1p ，…，每个i p 的长度均小于1-i p 的长度)1(≥i 。由0p 的长度的有限性知道，必有i p 其长度小于n 。
定义 1-1-2.2 若图G 中结点u 和v 之间存在一条（u ,v ）－道路，则称u 和v 在G 中是连通的。
在有向图中，若存在（u ,v ）－有向道路，则称u 到v 是有向连通的，或称为u 可达于v 。
就连通而言，图和有向图是有很大区别的。容易看出，连通是图的结点集上的一个等价关系。但是可达性却不是有向图的结点集上的等价关系，因为它一般不满足对称性。有向图的连通性问题要复杂一些。
对应于连通关系，存在着图G 的结点集V 的一个分划{}k V V V ,,,21 使得G 中任何两个结点u 和v 连通当且仅当u 和v 属于同一个分块)1(k i V i ≤≤。这样，
P 5
点诱导子图G （V i ）中任何两个结点都是连通的，而当j i ≠时，G （V i ）的结点与G （V j ）的结点间绝不会连通，因此)1)((k i V G i ≤≤是G 的极大连通子图，特别称为G 的支。图G 的支数记之为)(G ω。
定义 1-1-2.3 只有一个支的图称为连通图，支数大于1的图称为非连通图。 图1-1-2.3 是一个支数为3的非连通图的例子。
图1-1-2.3
定义
1-1-2.4 设u 和v 是图
G 中的两个结点，若u 和v 是连通的u 和v 之间的最短道路之长称为u 和v 之间的距离，记之为),(v u d 。若u 和v 不是连通的，规定∞=),(v u d 。
容易证明，这里定义的距离满足欧几里德距离的三条公理，即 （1）0),(≥v u d （非负性）； （2）),(),(u v d v u d =（对称性）；
（3）),(),(),(w u d w v d v u d ≥+（三角不等式）
上面定义的距离也适用于有向图，但是在有向图中两结点间（有向）距离
),(v u d 一般不满足对称性，即使),(),(u v d v u d 和都有限，它们也可能不相等。
二、图的连通性
在实际问题中，除了考察一个图是否连通外，往往还要研究一个图连通的程度，作为某些系统的可靠性的一种度量。
定义 1-1-2.5 设),(E V G =是连通图，若存在V S ?，使1)(>-S G ω，则称S 是G 的一个点割集（简称割集）；若对任何S S ?'都有1)(='-S G ω，则称S 为G 的一个基本割集。特别地，当{}v 是G 的割集时，称v 是G 的割点。
显然，完全图K n 没有割集，它的连通
4
7
图1-1-2.4
性能是最好的。图1-1-2.4给出了割集的例子。
割点：52,v v 割集：{}{}{} ,,,,,,525432v v v v v v 基本割集：{}{}{}4352,,,v v v v
定理 1-1-2.2 在非平凡连通图G 中，结点v 为G 的割点的充要条件是存在结点u 和w ，使u 到w 的每一条道路皆以v 为内部结点。
证明： 设v 是非平凡连通图G 的一个割点，由定义1)(>-v G ω。设),(111E V G =和),(222E V G =是G-v 中的任意两支，
任取21,V V u ∈∈ω，因为u 和ω在G 中是连通的，但是在G-v 中不是连通的，因此在G 中所有的〈u,w 〉－道路都必须经过v 。
反过来，若G 中存在结点u 和w ，使所有〈u,w 〉－道路都以v 为内部结点，则u 和w 在G-v 中必然不再连通。因此，v 是G 的一个割点。
定义 1-1-2.6 设),(E V G =是连通图，若存在E E ?1，使1)(1>-E G ω，则称G E 为1的一个边割集；若对任何1E E ?'都有1)(='-E G ω，则称1E 为G 的一个基本边割集。特别地，若{}e 是G 的边割集，则称e 为G 的割边。
图1-1-2.4中仅有一条割边21v v 。{}75654535,,,v v v v v v v v 是边割集，而{}4535,v v v v 是它包含的一个基本边割集，{}7565,v v v v 也是一个基本边割集。
定理 1-1-2.3 在连通图G 中，边e 为割边的充要条件是e 不包含于G 的任何圈中。
证明：必要性，设e 为割边，若e 包含在某一圈中，删去e 后，图仍连通，这与e 为割边矛盾，所以e 不包含在任一圈中。
充分性，若边e 不包含在G 的任意圈中，则删去e 后，图不再连通，因此，e 是G 的割边。
割集和边割集的定义也可以扩充到包括非连通图的情形。非连通图的割集和边割集都是空集。
下面从数量观点去描述图的连通性。
定义 1-1-2.7 图G 的点连通度)(G k 是使由G 产生一个非连通子图，或一个结点的子图所需要删去的最少的结点的数目。
显然，对一个不以完全图为其生成子图的图G ，定义中的“需要删去的最少
的结点数目”，就是G 的结点最少的基本割集的基数。图1-1-2.4的点连通度
1)(=G k 。对于完全图有1)(-=n K k n
定义 1-1-2.8 图G 的边连通度)(G λ，是使由G 产生一个非连通图所需要删去的最少的边的数目。若G 只有一个结点，则0)(=G λ。
容易知道，)2(1)(,1)(≥=-=r P n K r n λλ。
若k G k ≥)(，称G 是k －连通的，若k G ≥)(λ，则称G 是k －边连通的。显然，所有非平凡的连通图都是4-1-连通的和4-1-边连通的。
定理 1-1-2.4 对于任何图G ，皆有)()()(G G G k δλ≤≤。
证明： 若G 是非连通图或单结点图，则0)()(=≤G G k λ，结论自然成立。 若G 是非平凡的连通图，则因为每个结点关联的边构成G 的一个边割集，因此)()(G G δλ≤。
下面只须证明)()(G G k λ≤。
设F 是G 的一个基数为)(G λ的基本边割集，则G-F 含有两个支1G 和2G 。F 在1G 中关联的结点数不超过)(G λ，在2G 中关联的结点数也不超过)(G λ。在图1-1-2.5中可
以看出，删去F 在任一支中关联的全部结点，也必然删去了F 自身。因此，⑴若G 中1G （或2G ）部份至少有一个结点不与F 中的边关联，则在1G （或2G ）部份删去那些与F 关联的全部结点后，则得到G 的不连通子图，因此)()(G G k λ≤。⑵ 若G 中1G 和2G 部份的每个结点都与F 中的边关联，则当1G （或2G ）的阶为1时，显然这时)()(G G k λ≤，当1G 和2G 的阶都不为1时，交替地从1G 和2G 中删去与F 关联的结点，使对F 中的每条边只删去了一个关联结点且1G 和2G 部份各至少剩下一个结点，这时也有)()(G G k λ≤。综上可知)()(G G k λ≤恒成立。
三、有向图的连通性
定义 1-1-2.9 设G=（V ，E ）是一个简单有向图，如果对G 中任何一对结点，至少从其中一结点到另一结点是可达的，则称G 是单向连通的；如果任何两个结点之间都是相互可达的，则称G 是强连通的；如果G
的基图是连通的，
图1-1-2.5
则称G 是弱连通的。
图1-1-2.6中(a)、(b)和(C)分别是强连通图、单向连通图和弱连通图的例子。
图 4-1-2.6
由定义可知，强连通图必是单向连通图，单向连通图必是弱连通图。但是这两个命题反过来并不成立。
定义 1-1-2.10 设G=（V ，E ）是一个简单有向图，称G 的极大强连通子图为G 的强分图；称G 的极大单向连通子图为G 的单向分图；称G 的极大弱连通子图为G 的弱分图。
图1-1-2.7中的简单有向图是一个弱分图，其点诱导子图{}()321,,v v v G 、{}()4v G 、{}()5v G 和
{}()6v G 都是强分图，{}()654,,v v v G 和{}()54321,,,,v v v v v G 都是单向分图。
强分图在计算机科学中有特殊的应用。例如在操作系统中，同时有多道程序
m p p ,,1 在运行，设在某一时刻这些程序拥有的资源（如CPU ，主存储器、输入输出设备、数据集、数据库、编译程序等）的集合为{}n r r r ,,,21 。一个程序在占有某项资源时可能对另一项资源提出要求，这样就存在着一个资源的动态分配问题。这个问题可以用一个有向图()
)()()(,t t t E V G =来表示。)(t V 是t 时刻各项资源的集合{}n r r r ,,,21 ，)(t E 的每条有向边
()j
i
r r ,，加有标记k
p
表示运行程序k p 在占有资
源i r 的情况下又要求资源j r 。图1-1-2.8是这样一个例子，其中程序1P 占有2r 时又要求1r ，2P 占有3r 时又要求2r 等等，资源分配就会出现冲突，只要各自都不释放已占有的资源，上述要求就
无法满足，即出现所谓“死锁”现象。“死锁”现象对应对于)(t G
中存在非平凡
(a ) (b ) (c
)
图1-1-2.7
v v
6
r 1 r 2
r 3
r 4
P 1
P 2
P 3 P 4
P 5 P 6
图1-1-2.8
的强分图。
定理 1-1-2.5 一个简单有向图是强连通的当且仅当G 中有一条包含每个结点的有向闭道路。
证明： 设G 是强连通的。如果G 中任何有向闭道路C 皆不包含结点v ，由强连通定义，v 必与C 中结点相互可达，故在C 中存在两个结点1u 和2u （可以相同），使1u 可达v ，v 可达2u ，如图1-1-2.9所示。这样就可以构造一条新的闭道路
21212u v u u w u u →→→→→→，它包含有v ，使假设矛盾。因此，G 是强连通图时必有一条包含所有结点的闭道路。
反过来，若G 中有一条包含所有结点的闭道路，则任何两结点沿着这条道路相互可达，因而G 必是强连通的。
定理 1-1-2.6 在简单有向图G=（V ，E ）中，每个结点位于且仅位于一个强分图中。
证明： 任取V v ∈，设)(v R 是G 中与v 相互可达的结点构成的集合。显然，
Φ≠)(v R ，并且点诱导子图))((v R G 是G 的一个强连通子图。这说明G 中每个结
点必位于一个强分图中。
若v 既位于强分图),(111E V G =中，又位于强分图),(222E V G =中，那么
)(21v R V V ??，必然导致21V V =即21G G =。
事实上，相互可达是结点集V 上的一个等价关系，它导致产生V 的一个分划{}k V V V ,,21 ，因此)(),(),(21k G G V G V G 都是G 的强分图，定理4-1-2.6正是反映了这一事实。下节将介绍一种寻找G 的全部强分图的方法。
1-1-2 习题
1．若u 和v 是图G 中仅有的两个奇数度结点，证明u 和v 必是连通的。 2．证明G 是二部图当且仅当G 的回路都是偶长回路。 3．设（n ，m ）－简单图G 满足)2)(1(2
1
-->n n m ，证明G 必是连通图。构造一个)2)(1(2
1
--=
n n m 的非连通简单图。
C v
图1-1-2.9
4．设G 是阶数不小于3的连通图，证明下面四条命题相互等阶： （1）G 无割边；（2）G 中任何两个结点位于同一回路中；（3）G 中任何一结点和任何一边都位于同一回路中；（4）G 中任何两边都在同一回路中。
5．设G=（V ，E ）是点度均为偶数的连通图，证明对任何
)(2
1
)(,v d v G V v ≤
-∈ω。 6．证明图中距离满足欧几里德距离的三条公理。
7．证明在非平凡连通图G 中，e 为割边的充要条件是它不包含于G 的任何圈中。
8．证明若理3度正则的简单图，则)()(G G k λ=。 9．证明恰有两个非割点的简单连通图必是)2(≥n P n
10．设G 是2≥δ的简单图，证明G 中必有长度至少为1+δ的圈。 11．连通图G=（V ，E ）的直径定义为),(,,),,(max v u d V v u v u d D ∈=是u 和v 之间的距离。证明：
（1）若G 的直径大于3，则G 的直径必小于3。 （2）设G 的阶为n ，则1-≤n D 。
（3）若G 是（n ，m ）简单图且D=2，△=n-2,则42-≥n m 。
12．在连通图G=（V ，E ）中，满足???
???∈∈V v v u d V u ),(max min 的结点称为G 的中心。试确定n P 和n C 各有多少个中心？
13．有向图的直径也可按11题方式定义。 求图1-1-2.10的直径，全部强分图和单向分图。 14．证明G 是单向连通图当且仅当存在一条包含G 中全部结点的有向道路。
§1-1-3 图的矩阵表示
一个图可以按定义描述出来，也可以用图形表示出来，还可以同二元关系一样，用矩阵来表示。图用矩阵表示有很多优点，既便于利用代表知识研究图的性质，构造算法，也便于计算机处理。
图的矩阵表示常用的有两种形式：邻接矩阵和关联矩阵。
邻接矩阵常用于研
图1-1-2.10
究图的各种道路的问题，关联矩阵常用于研究子图的问题。由于矩阵的行列有固定的顺序，因此在用矩阵表示图之前，须将图的结点和边加以编号（定序），以确定与矩阵元素的对应关系。
一、邻接矩阵 1．邻接矩阵的概念
定义 1-1-3.1 设G=（V ，E ）是一简单有向图，结点集为{}n v v v V ,,,21 =。构造矩阵n n ij a A ?=)(其中
()()?
???∈=,,,0,
,,1E v v E v v a j i j i ij 当当
则称A 为有向图G 的邻接矩阵。
这个定义也适用于无向图，只须把其中的有向表示换成无向表示就行了。这一节主要考虑有向图的矩阵表示问题。
例 图1-1-3.1中有向图的邻接矩阵是
?????????
?
??????????=
01
1
1
0000111010001000001054321
5
4321v v v v v v v v v v A 显然，当改变图的结点编号顺序时，可以得到图的不同的邻接矩阵，这相当于对一个矩阵进行相应行列的交换得到新的邻接矩阵。例如对图1-1-3.1的结点重新定序，使1v 与5v 对换，则得到新的邻接矩阵
?????????
?
??????????=
'00
1
1000001011001001101014325
1
4325
v v v v v v v v v v A 。 从线性代数的矩阵变换来看，A '是通过对A 分别左乘和右乘一个置换矩阵
v
34图1-1-3.1
图论基础
1、略 2、计算有向无圈图的根 输入一个有向无圈图DAG，计算和输出DAG的根r（即r到其他任何顶点都有一条路。若图中没有根，则输出“not found”）。 输入：顶点数n和边数e;以下为e行，每行为一条有向边的两个端点 输出：根r或者“not found” 算法分析 设 const mx=100;{顶点数的上限} var n,e,i,j,k,a,b:integer;{ 顶点数n、边数e} g:array[1..mx,1..mx]of boolean;{传递闭包} bn:boolean;{根存在标志} 1、输入信息，计算传递闭包 readln(n,e);{输入顶点数和边数} fillchar(g,sizeof(g),0);{ 有向无圈图初始化} for i:=1 to e do{输入信息，构造传递闭包的初始值} begin readln(a,b);g[a,b]:=true end; for k:=1 to n do{计算传递闭包} for i:=1 to n do for j:=1 to n do if g[i,j] or g[i,k] and g[k,j]then g[i,j]:=true; 2、计算DAG的根 然后枚举每一个顶点。根据传递闭包的信息，若当前顶点至其它所有顶点有路，则判定该顶点即为根。若没有一个顶点可作为DAG的根，则输出失败信息 for i:=1 to n do{枚举每一个可能的根} begin bn:=true;{设定I至其他所有顶点有路的标志} for j:=1 to n do{若I至任一个顶点无路，则返回bn为false} if (i<>j) and not g[i,j] then begin bn:=false; break end; if bn then break{若I至其他所有顶点有路，则输出根i} end; if bn then writeln(i) else writeln('not found'){若不存在根，则输出失败信息}
离散数学的基础知识点总结
离散数学的基础知识点总结 第一章命题逻辑 1.前键为真，后键为假才为假；＜—＞，相同为真，不同为假；2?主析取范式：极小项（m）之和；主合取范式：极大项（M）之积； 3.求极小项时，命题变元的肯定为1，否定为0,求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写; 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n个变元共有2n个极小项或极大项，这2n为（0~2n-1）刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法（=＞）:真值表法；分析法（假定前键为真推出后键为真，假定前键为假推出后键也为假） 10.命题逻辑的推理演算方法：P规则，T规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第二章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含T,存在量词用合取“； 3.既有存在又有全称量词时，先消存在量词，再消全称量词；
第四章集合 1.N，表示自然数集，1,2,3……，不包括0; 2.基：集合A中不同元素的个数，|A|; 3.幕集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)； 4.若集合A有n个元素，幕集P(A)有2°个元素，|P(A)|= 2|A|= 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 第五章关系 1.若集合A有m个元素，集合B有n个元素，则笛卡尔AXB的基数为mn , A到B上可以定义2mn种不同的关系； 2.若集合A有n个元素，则|A X\|= n2, A上有2n个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全圭寸闭环的性质：自反性，对称性，反对称性，传递性； 4.前域（domR）:所有元素x组成的集合；
数学建模入门基本知识
数学建模知识 ——之新手上路一、数学模型的定义 现在数学模型还没有一个统一的准确的定义，因为站在不同的角度可以有不同的定义。不过我们可以给出如下定义：“数学模型是关于部分现实世界和为一种特殊目的而作的一个抽象的、简化的结构。”具体来说，数学模型就是为了某种目的，用字母、数学及其它数学符号建立起来的等式或不等式以及图表、图像、框图等描述客观事物的特征及其内在联系的数学结构表达式。一般来说数学建模过程可用如下框图来表明： 数学是在实际应用的需求中产生的，要解决实际问题就必需建立数学模型，从此意义上讲数学建模和数学一样有古老历史。例如，欧几里德几何就是一个古老的数学模型，牛顿万有引力定律也是数学建模的一个光辉典范。今天，数学以空前的广度和深度向其它科学技术领域渗透，过去很少应用数学的领域现在迅速走向定量化，数量化，需建立大量的数学模型。特别是新技术、新工艺蓬勃兴起，计算机的普及和广泛应用，数学在许多高新技术上起着十分关键的作用。因此数学建模被时代赋予更为重要的意义。 二、建立数学模型的方法和步骤 1. 模型准备 要了解问题的实际背景，明确建模目的，搜集必需的各种信息，尽量弄清对象的特征。 2. 模型假设 根据对象的特征和建模目的，对问题进行必要的、合理的简化，用精确的语言作出假设，是建模至关重要的一步。如果对问题的所有因素一概考虑，无疑是一种有勇气但方法欠佳的行为，所以高超的建模者能充分发挥想象力、洞察力和判断力，善于辨别主次，而且为了使处理方法简单，应尽量使问题线性化、均匀化。 3. 模型构成 根据所作的假设分析对象的因果关系，利用对象的内在规律和适当的数学工具，构造各个量间的等式关系或其它数学结构。这时，我们便会进入一个广阔的应用数学天地，这里在高数、概率老人的膝下，有许多可爱的孩子们，他们是图论、排队论、线性规划、对策论等许多许多，真是泱泱大国，别有洞天。不过我们应当牢记，建立数学模型是为了让更多的人明了并能加以应用，因此工具愈简单愈有价值。 4. 模型求解 可以采用解方程、画图形、证明定理、逻辑运算、数值运算等各种传统的和近代的数学方法，特别是计算机技术。一道实际问题的解决往往需要纷繁的计算，许多时候还得将系统运行情况用计算机模拟出来，因此编程和熟悉数学软件包能力便举足轻重。 5. 模型分析
复杂网络基础2(M.Chang)
复杂网络基础理论 第二章网络拓扑结构与静态特征
第二章网络拓扑结构与静态特征 l2.1 引言 l2.2 网络的基本静态几何特征 l2.3 无向网络的静态特征 l2.4 有向网络的静态特征 l2.5 加权网络的静态特征 l2.6 网络的其他静态特征 l2.7 复杂网络分析软件 2
2.1 引言 与图论的研究有所不同，复杂网络的研究更侧重 于从各种实际网络的现象之上抽象出一般的网络几何 量，并用这些一般性质指导更多实际网络的研究，进 而通过讨论实际网络上的具体现象发展网络模型的一 般方法，最后讨论网络本身的形成机制。 统计物理学在模型研究、演化机制与结构稳定性 方面的丰富的研究经验是统计物理学在复杂网络研究 领域得到广泛应用的原因；而图论与社会网络分析提 供的网络静态几何量及其分析方法是复杂网络研究的 基础。 3
2.1 引言 静态特征指给定网络的微观量的统计分布或宏观 统计平均值。 在本章中我们将对网络的各种静态特征做一小结 。由于有向网络与加权网络有其特有的特征量，我们 将分开讨论无向、有向与加权网络。 4 返回目录
2.2 网络的基本静态几何特征 ￠2.2.1 平均距离 ￠2.2.2 集聚系数 ￠2.2.3 度分布 ￠2.2.4 实际网络的统计特征 5
2.2.1 平均距离 1.网络的直径与平均距离 网络中的两节点v i和v j之间经历边数最少的一条简 单路径（经历的边各不相同），称为测地线。 测地线的边数d ij称为两节点v i和v j之间的距离（或 叫测地线距离）。 1／d ij称为节点v i和v j之间的效率，记为εij。通常 效率用来度量节点间的信息传递速度。当v i和v j之间没 有路径连通时，d ij＝∞，而εij＝0，所以效率更适合度 量非全通网络。 网络的直径D定义为所有距离d ij中的最大值 6
图论应用案例
题目：最小生成树在城市交通建设中的应用 姓名： 学号： 指导老师： 专业：机械工程 2014年3月16
目录 摘要..................................................................................... 错误！未定义书签。 1 绪论 (1) 2 有关最小生成树的概念 (2) 3 prim算法介绍 (3) 4 系统设计及其应用 (5) 一、系统设计 (5) 二、最小生成树应用 (8) 5 总结 (11) 参考文献 (12) 附件： (13)
最小生成树在城市交通建设中的应用 摘要：连通图广泛应用于交通建设，求连通图的最小生成树是最主要的应用。比如要在n个城市间建立通信联络网，要考虑的是如何保证n点连通的前提下最节省经费，就应用到了最小生成树。 求图的最小生成树有两种算法，一种是Prim（普里姆）算法，另一种是Kruskal（克鲁斯卡尔）算法。 本文通过将城市各地点转换成连通图，再将连通图转换成邻接矩阵。在Microsoft Visual C++上，通过输入结点和权值，用普里姆算法获得权值最小边来得到最小生成树，从而在保证各个地点之间能连通的情况下节省所需费用。 本文从分析课题的题目背景、题目意义、题目要求等出发，分别从需求分析、总体设计、详细设计、测试等各个方面详细介绍了系统的设计与实现过程，最后对系统的完成情况进行了总结。 关键字：PRIM算法、最小生成树、邻接矩阵、交通建设
Abstract Connected graph is widely applied in traffic construction, connected graph of minimum spanning tree is the main application.Such as to establish a communication network between the n city, want to consider is how to ensure n points connected under the premise of the most save money, apply to the minimum spanning tree. O figure there are two kinds of minimum spanning tree algorithm, one kind is Prim (she) algorithm, the other is a Kruskal algorithm (Kruskal). In this article, through the city around point into a connected graph, then connected graph is transformed into adjacency matrix.On Microsoft Visual c + +, through the input nodes and the weights, gain weight minimum edge using she algorithm to get minimum spanning tree, which in the case of guarantee every location between connected to save costs. Based on the analysis topic subject background, significance, subject requirements, etc, from requirements analysis, general design, detailed design, testing, and other aspects detailed introduces the system design and implementation process, finally the completion of the system are summarized. Key words: PRIM algorithm, minimum spanning tree, adjacency matrix, traffic construction
图论总结(超强大)78408
1.图论Graph Theory 1.1.定义与术语Definition and Glossary 1.1.1.图与网络Graph and Network 1.1. 2.图的术语Glossary of Graph 1.1.3.路径与回路Path and Cycle 1.1.4.连通性Connectivity 1.1.5.图论中特殊的集合Sets in graph 1.1.6.匹配Matching 1.1.7.树Tree 1.1.8.组合优化Combinatorial optimization 1.2.图的表示Expressions of graph 1.2.1.邻接矩阵Adjacency matrix 1.2.2.关联矩阵Incidence matrix 1.2.3.邻接表Adjacency list 1.2.4.弧表Arc list 1.2.5.星形表示Star 1.3.图的遍历Traveling in graph 1.3.1.深度优先搜索Depth first search (DFS) 1.3.1.1.概念 1.3.1. 2.求无向连通图中的桥Finding bridges in undirected graph 1.3. 2.广度优先搜索Breadth first search (BFS) 1.4.拓扑排序Topological sort 1.5.路径与回路Paths and circuits 1.5.1.欧拉路径或回路Eulerian path 1.5.1.1.无向图 1.5.1. 2.有向图 1.5.1.3.混合图
1.5.1.4.无权图Unweighted 1.5.1.5.有权图Weighed —中国邮路问题The Chinese post problem 1.5. 2.Hamiltonian Cycle 哈氏路径与回路 1.5. 2.1.无权图Unweighted 1.5. 2.2.有权图Weighed —旅行商问题The travelling salesman problem 1.6.网络优化Network optimization 1.6.1.最小生成树Minimum spanning trees 1.6.1.1.基本算法Basic algorithms 1.6.1.1.1.Prim 1.6.1.1. 2.Kruskal 1.6.1.1.3.Sollin（Boruvka） 1.6.1. 2.扩展模型Extended models 1.6.1. 2.1.度限制生成树Minimum degree-bounded spanning trees 1.6.1. 2.2.k小生成树The k minimum spanning tree problem(k-MST) 1.6. 2.最短路Shortest paths 1.6. 2.1.单源最短路Single-source shortest paths 1.6. 2.1.1.基本算法Basic algorithms 1.6. 2.1.1.1.Dijkstra 1.6. 2.1.1.2.Bellman-Ford 1.6. 2.1.1.2.1.Shortest path faster algorithm(SPFA) 1.6. 2.1.2.应用Applications 1.6. 2.1.2.1.差分约束系统System of difference constraints 1.6. 2.1.2.2.有向无环图上的最短路Shortest paths in DAG 1.6. 2.2.所有顶点对间最短路All-pairs shortest paths 1.6. 2.2.1.基本算法Basic algorithms 1.6. 2.2.1.1.Floyd-Warshall 1.6. 2.2.1.2.Johnson
图论基础知识
图论基本知识 对于网络的研究，最早是从数学家开始的，其基本的理论就是图 论，它也是目前组合数学领域最活跃的分支。我们在复杂网络的研究中将要遇到的各种类型的网络，无向的、有向的、加权的……这些都可以用图论的语言和符号精确简洁地描述。图论不仅为物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。图论，尤其是随机图论已经与统计物理并驾齐驱地成为研究复杂网络的两大解析方法之一。考虑到物理学家对于图论这一领域比较陌生，我在此专辟一章介绍图论的基本知识，同时将在后面的章节中不加说明地使用本章定义过的符号。进一步研究所需要的更深入的图论知识，请参考相关文献[1-5]。 本章只给出非平凡的定理的证明，过于简单直观的定理的证明将 留给读者。个别定理涉及到非常深入的数学知识和繁复的证明，我们将列出相关参考文献并略去证明过程。对于图论知识比较熟悉的读者可以直接跳过此章，不影响整体阅读。 图的基本概念 图G 是指两个集合(V ，E)，其中集合E 是集合V×V 的一个子集。 集合V 称为图的顶点集，往往被用来代表实际系统中的个体，集合E 被称为图的边集，多用于表示实际系统中个体之间的关系或相互作用。若{,}x y E ，就称图G 中有一条从x 到y 的弧（有向边），记为x→
y ，其中顶点x 叫做弧的起点，顶点y 叫做弧的终点。根据定义，从任意顶点x 到y 至多只有一条弧，这是因为如果两个顶点有多种需要区分的关系或相互作用，我们总是乐意在多个图中分别表示，从而不至于因为这种复杂的关系而给解析分析带来困难。如果再假设图G 中不含自己到自己的弧，我们就称图G 为简单图，或者更精确地叫做有向简单图。以后如果没有特殊的说明，所有出现的图都是简单图。记G 中顶点数为()||G V ν=，边数为()||G E ε=，分别叫做图G 的阶和规模，显然有()()(()1)G G G ενν≤-。图2.1a 给出了一个计算机分级网络的示意图，及其表示为顶点集和边集的形式。 图2.1：网络拓扑结构示意图。图a 是10阶有向图，顶点集为 {1,2,3,4,5,6,7,8,9,10}，边集为{1→2,1→3,1→4,2→5,2→6,2→7,3→6,4→7,4→8,6→9,7→9,8→10}；图b 是6阶无向图，顶点集为{1,2,3,4,5,6}，边集为{13,14,15,23,24,26,36,56}。 从定义中可以看到，从任意顶点x 到y 不能连接两条或以上 边，本文所讨论的图，均符合上述要求，既均为不含多重边的图。如
图论在交叉学科中的应用
数学科学学院 课程名称图论导引 题目图论在交叉学科中的应用姓名闫二路 学号 A01014134 专业数学与应用数学 授课老师汪毅
图论在交叉学科中的应用 [摘要]利用图论知识可以解决一些交叉学科中的实际问题。对于更好地理解问题，思考问题从而求解问题具有现实意义。图论知识的应用是相当广泛的，它是数学的重要分支，使今年来较为活跃的数学分支，它是源于生活，高于生活。图论作为组合数学的一分支，与其他数学分支，如信息论，矩阵论都有着重要的联系。 [关键字] 树、即时码、hamilton圈、Hamilton路 1．即时码的树图构造法 即时码定义：在唯一可译变长码中，有一类码，它在译码时无须参考后续的码符号就能立即做出判断，译成对应的信源符号，则这类码称为即时码。 树的定义：一个图G若是无圈的且连通，则称图G是树。 为了联系树与即时码的关系我们引入关于判断树的一个定理； 定理1:图G是树当且仅当G的任何两个顶点都被唯一的路连接。 从上述定理1我们可以判断利用树构造的码为即时码，如下图构造的即时码：
从上面我们可以得到码字集合C1={000,001,010,011,100,101,110,111}，C2={00,01,02,10,11,12,20,210，211,212,220,221,222} 我们根据即时码的定义可得利用树构造的码都是即时码，我们也知道即时码一定是唯一可译码，因此树图能给我们带来比较方便的方法来构造即时码。 问题求解反思：我们从即时码的树图构造法中，我们得到:使用图论中的树我们能很容易得到信息论中即时码的一种构造方法，这里利用了交叉学科相互结合的思想，利用图我们能更好的理解一些实际问题，有利于我们的理解，从这个方面我们能得出图论在其他学科有着很重要的联系，有利于实际问题更好的解决。 2.Hamilton图的应用 Hamilton图的定义：一个含图G的每个顶点的圈称为是G的Hamilton 圈，这个含有Hamilton圈的图称为是一个Hamilton图。 Hamilton圈在现实中有着广泛的应用，当我们给出一个实际问题时，我们应该怎样Hamilton图来解决实际问题，这需要我们从联系实际
1040 【图论基础】求连通子图的个数 1041 【图论基础】求最小生成树(prim)
【图论基础】求连通子图的个数 Time Limit:10000MS Memory Limit:65536K Total Submit:42 Accepted:30 Description 求一个无向图中连通子图的个数。 Input 第一行一个数n，表示无向图的顶点的数量（n<=5000），接下来从第2行到第n+1行，每行有n个数（1表示相应点有直接通路，0表示无直接通路），形成一个n*n的矩阵，用以表示这个无向图。示例： Output 输出一个数，表示这个图含有连通子图的个数。 Sample Input 5 1 0 1 0 0 0 1 1 1 0 1 1 1 1 0 0 1 1 1 0 0 0 0 0 1 Sample Output 自己算吧！ Source
?var ? i,j,n,ans,x:longint; ? a:array[1..5000,0..5000] of longint; ? b:array[1..5000] of boolean; ?procedure dfs(x:longint); ?var i:longint; ?begin ? b[x]:=false; ? for i:=1 to a[x,0] do if b[a[x,i]] then ? dfs(a[x,i]); ?end; ? ?begin ? readln(n); ? for i:=1 to n do ? for j:=1 to n do begin ? read(x); ? if x=1 then begin ? inc(a[i,0]); a[i,a[i,0]]:=j; ? end; ? end; ? fillchar(b,sizeof(b),true); ? for i:=1 to n do if b[i] then begin ? inc(ans); ? dfs(i); ? end; ? writeln(ans); ?end.
离散数学第七章图的基本概念知识点总结docx
图论部分 第七章、图的基本概念 7.1 无向图及有向图 无向图与有向图 多重集合: 元素可以重复出现的集合 无序积: A&B={(x,y) | x∈A∧y∈B} 定义无向图G=
通常用G表示无向图, D表示有向图, 也常用G泛指 无向图和有向图, 用e k表示无向边或有向边. V(G), E(G), V(D), E(D): G和D的顶点集, 边集. n 阶图: n个顶点的图 有限图: V, E都是有穷集合的图 零图: E=? 平凡图: 1 阶零图 空图: V=? 顶点和边的关联与相邻：定义设e k=(v i,v j)是无向图G=
电子科技大学研究生图论总结
第一章：图论基本概念 1.定义 平凡图/非平凡图 简单图/复合图 空图 n 阶图 连通图/非连通图 完全图n K 12 n n n m K 偶图,m n K 完全偶图 ,m n m K mn K 正则图 图和补图，自补图 自补图判定方法 定点的度 d v 最小度 最大度 握手定理 2d v m 图的度序列与图序列，图序列判定方法（注意为简单图） 图的频序列 2.图运算 删点/删边 图并/图交/图差/图对称差 图联 积图/合成图111122,u adjv u v u adjv 或 超立方体 3.连通性 途径 迹 路 图G 不连通，其补图连通 一个图是偶图当且仅当它不包含奇圈 4.最短路算法（b t A T ） 5.矩阵描述 邻接矩阵及其性质，图的特征多项式 关联矩阵 6.极图？？ L 补图 完全L 部图 完全L 几乎等部图 托兰定理 第二章：树 1.定义 树：连通的无圈图 森林 树的中心和树的形心？ 入<=sqrt(2m(n-1)/n)
生成树 根树 出度 入度 树根 树叶 分支点 m 元根树 完全m 元根树 2.性质 每棵非平凡树至少有两片树叶 图G 是树当且仅当G 中任意两点都被唯一的路连接 T 是(n,m)树，则m = n – 1 具有k 个分支的森林有n-k 条边 每个n 阶连通图边数至少为n-1（树是连通图中边的下界） 每个连通图至少包含 一棵生成树 3.计算 生成树计数 递推计数法： G G e G e 关联矩阵计数法：去一点后，每个非奇异阵对应一棵生成树 最小生成树（边赋权） 避圈法 破圈法 完全m 元树： 11m i t 第三章：图的连通性 1. 割边、割点和块（性质使用反证法） 割边： w G e w G 边e 为割边当且仅当e 不在任何圈中 割点： w G v w G v 是无环连通图G 的一个顶点，v 是G 的割点当且仅当V(G-e)可以被划分为两个子 集，v 在两个子集内点互连的路上 块：没有割点的连通子图 G 顶点数>=3，G 是块当且仅当G 无环且任意两顶点位于同一圈上 v 是割点当且仅当v 至少属于G 的两个不同的块 2. 连通度 点割 k 顶点割 最小点割（最少用几个点把图割成两份） G 的连通度 G 连通图没顶点割时连通度 1G n ，非连通图 0G 边割 k 边割 最小边割（最少用几条边把图割成两份） G 的边连通度 G 递推到无圈，自环不算圈
八年级最短路径归纳小结
八年级数学最短路径问题 【问题概述】最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径．算法具体的形式包括： ①确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题． ②确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题． ③确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径． ④全局最短路径问题 - 求图中所有的最短路径． 【问题原型】“将军饮马”，“造桥选址”，“费马点”． 【涉及知识】“两点之间线段最短”，“垂线段最短”，“三角形三边关系”，“轴对称”，“平移”． 【出题背景】角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等． 【解题思路】找对称点实现“折”转“直”，近两年出现“三折线”转“直”等变式问题考查．
【精品练习】 1．如图所示，正方形ABCD 的面积为12，△ABE 是等边三角形，点E 在正方形ABCD 内，在对角线AC 上有 一点P ，使PD +PE 的和最小，则这个最小值为（ ） A ． B ． C ．3 D 2．如图，在边长为2的菱形ABCD 中，∠ABC ＝60°，若将△ACD 绕点A 旋转，当AC ′、AD ′分别与BC 、CD 交于点E 、F ，则△CEF 的周长的最小值为（ ） A ．2 B ．32 C ．32+ D ．4 3．四边形ABCD 中，∠B ＝∠D ＝90°，∠C ＝70°，在BC 、CD 上分别找一点M 、N ，使△AMN 的周长最小时， A D E P B C
∠AMN +∠ANM 的度数为（ ） A ．120° B ．130° C ．110° D ．140° 4．如图，在锐角△ABC 中，AB ＝42，∠BAC ＝45°，∠BAC 的平分线交BC 于点D ，M 、N 分别是AD 和AB 上的动点，则BM +MN 的最小值是 ． 5．如图，Rt △ABC 中，∠C ＝90°，∠B ＝30°，AB ＝6，点E 在AB 边上，点D 在BC 边上（不与点B 、C 重合）， 且ED ＝AE ，则线段AE 的取值范围是 ． 6．如图，∠AOB ＝30°，点M 、N 分别在边OA 、OB 上，且OM ＝1，ON ＝3，点P 、Q 分别在边OB 、OA 上，则MP ＋PQ ＋QN 的最小值是_________．（注“勾股定理”：直角三角形中两直角边的平方和等于斜边的平方，即Rt △ABC 中，∠C ＝90°，则有222AB BC AC =+） 7．如图，三角形△ABC 中，∠OAB ＝∠AOB ＝15°，点B 在x 轴的正半轴，坐标为B (36，0)． OC 平分∠AOB ，点M 在OC 的延长线上，点N 为边OA 上的点，则MA ＋MN 的最小值是______． 8．已知A （2，4）、B （4，2）．C 在y 轴上，D 在x 轴上，则四边形ABCD 的周长最小值为 ， D E A B C
图论类型各题总结-acm
hdu4318 Power transmission 最短路当数据很大的时候的解决办法一道题目的解题全过程记录 最短路解决大数据模拟链表 Power transmission Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 663 Accepted Submission(s): 231 Problem Description The project West-East power transmission is famous around the world. It transmits the electricity from western areas to east China. There are many nodes in the power system. Each node is connected with several other nodes in the system by cable. Power can be only transmitted between two connected nodes. For each node, it can’t send power to two or more other nodes at the same time. As we have all known, power will be loss during the transmission. Bob is the chief engineer of the project. He wants to build a transmission line which send power from one node to another node and minimize the power loss at the same time. Now he asks you to help him solve the problem. Input There are several test cases. For each test case, the first line contains an integer N (0 < N ≤ 50000) which represents the number of nodes in the power system. Then there will be N groups of data following. For the i-th(0 < i ≤ N) group, the first line is an integer ki (ki ≤ 50), which means the node i is connected with ki nodes. The rest of the i-th group data are divided into ki lines. Each line contains an integer ai (0 < ai ≤ N, ai ≠ i) and an integer bi (0 ≤ bi ≤ 100), which represents power can be transmitted from node i to ai and will loss bi% while transmitting. The last line of input data contains three integers separated by single spaces. The first one is s, the second is t (0 < s, t ≤ N), and the third is the total power M (0 < M ≤ 10^6) at node s. Output For each test case, output the minimum of loss power while transmitting from node s to node t. The result should be printed with two digits to the right of the decimal point. If power cannot be transmitted from node s to node t, output “IMPOSSIBLE!” in a line. Sample Input 4 2
离散数学(图论)课后总结
第八章图论 例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=
图论及其应用总结归纳第三章答案(电子科大)
精心整理 2019年－9月 习题三： ?证明：是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意 及, G 中的路 必含. 证明：充分性 : 是 的割边，故 至少含有两个连通分支，设 是其中一个连通分支的顶点 集，是其余分支的顶点集，对1,u V v ?∈?∈ 以在每一条 路上，中的 必含。 必要性：取12,u V v V ∈∈， 由假设中所有从而在中不存在从与到的路， 这表明不连通，所以e 是割边。 ?3.设G 是阶大于2（1） G 是块 （2） G （3） G 是块，任取的一点，一边，在 ，使得成为两条边，由此得到新图 ，显然 的块，由定理， 中u 与边都位于同一个 圈上。 ： 的点u ，边e ，若在上，则三个 不在 上，由定理，的两点在同一个闭路上， 在边插入一个点v ，由此得到新图，显然 的是阶数大于3的块，则两条边的三个不同点在 同一条路上。 ： 连通，若不是块，则中存在着割点，划分为不同的子集块,,, 无环，12,x v y v ∈∈， 点在每一条 的路上，则与已知矛盾，是块。
精心整理 2019年－9月 ?7.证明：若v 是简单图G 的一个割点，则v 不是补图的割点。 证明： 是单图 的割点，则 有两个连通分支。现任取 , 如果 不在的同一分支中，令是与处于不同分支的点，那么，与在 的补图中连通。若 在 的 同一分支中，则它们在 的补图中邻接。所以，若是的割点，则不是补图的割点。 ?12.对图3——20给出的图G1和G2，求其连通度和边连通度，给出相应的最小点割和最小边割。 解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）} ()25G κ= 最小点割{6,7,8,9,10} 2()5G λ= 最小边割{（2,7）…（1,6）} ?13.设H 是连通图G 解： 通常 . 整个图为，割点左边的图为的的子图， ，则 .
离散数学基本知识
离散数学基本知识 01 什么是“数据结构”？ 这里我就不说那些“官方的定义”，简单谈谈自己的理解吧。 数据结构是一种抽象的封装。 好像还是有点绕脑，不过没关系，我们继续往下看。 说简单点就是，把一堆基本的数据，按照某种顺序给揉成一坨。 相信大家都吃过饭吧？ 做一道菜需要放各种调料，如盐、味精，还有肉等，把它们混在一起就做成了一道菜。 口水鸡是我最喜欢的一道菜，这里我们就以口水鸡为例，来讲一讲什么是数据结构。下图是百度百科中口水鸡的做法。
好，下面我就用程序来表示一下，我写的是伪码，大家能懂就好哈。先来抽象一下“口水鸡”：
对，上述这个结构体就是一个自定义的数据结构，将很多种不同的东西融合在一起；而计算机中的数据结构，则是把一些基本的数据类型，如int、double等融合成一些复杂的数据结构，如map、队列。 抽象完口水鸡再来抽象“你”吧： 然后再来抽象一下“厨师”：
这里的抽象有点随意，不过大家理解就好，我们把一堆很基本的元素抽象成了3个数据结构，这三个元素就是所谓的数据结构。 而平时我们说的链表无非就是把一些基本元素和指针做了融合，树、图也是把指针和一些基本元素融合后再外加一些流程，如函数。 比如python的dict，dict的key，value就是两种相同或者不同的数据类型；dict还提供了一些函数，譬如get()，set()。dict就是一个典型的被封装的数据结构。 所以我说数据结构是一种抽象的封装，当然，数据结构并没有我们举的例子那样简单，但是原理是一样的。 我们平时写程序都是直接去调用这些数据结构，而没有去想它们的内部实现是怎样的。数据结构这门课就是要告诉我们常见的数据结构是如何实现的，比如Vector，map的实现。我们常常听到的譬如平衡二叉树，红黑树，大顶堆等词汇就是出自数据结构这门课。具体了解数据结构后，我们就可以知道队列的内部实现是什么样，词典的内部实现又是什么样。