图论讲义15
定理10.8 (Kuratowski定理)：一个图G是平面图当且仅当G中不包含同态于K5或K3,3的子图。
证明：在10.3节，我们已证明了K5和K3,3不是平面图，再由定理10.4可知，当一个图G包含同态于K5或K3,3的子图，则G不是平面图。从而定理的必要性得证。
现在我们来证明定理的充分性。我们对G的边数归纳证明。当G 只有m=1条边时，显然G是平面图。现在我们假设当G的边数m< N(N≥2)时，G是平面图。现在设G有m=N条边。我们证明：如果G不包含同态于K5和K3,3的子图，但G不是平面图，则导出矛盾。设G不是平面图，则有以下几个结论：
(a)G必须是连通的；
(b)G不包含割点；
(c)如果G中任一边(x, y)被删除，则所得到的图G′中存在包含x和y
的圈。
我们来证明结论(c)。注意到G′是连通的，这因为G不包含割点。如果G′中不存在包含x和y的圈，那么从x到y的每条路径都经过一个公共点z。换句话说，z是G′的一个割点。那么G′可以在z处分解成两个连通分支G1′包含x和z和G2′包含y和z。我们在G1′中加入边xz，得G1"，在G2′中加入边yz的G2"。这时G1"和G2"都不包含同态于K5和K3,3的子图。这是因为G1′是G的子图不可能包含同态于K5或K3,3的子图，假如G1"中包含这样的子图，则该子图必然经过边xz，而在G中可找到一条从z到y的路径P再加上边yx代替xz，从而G中存在同
态于K5或K3,3的子图，这与假设矛盾。同理可证对G2"结论成立。
由归纳假设，G1"和G2"是平面图。根据定理10.5，我们可以找到G1"的平面嵌入，使得xz在外部面上，也可以找到G2"的平面嵌入，使得yz 在外部面上，令G1"和G2"在z处相交，并用xy边取代xz和yz边，则可以得到G的一个平面嵌入，这与G不是平面图的假设矛盾。从而证明了G′不包含割点。即G′是一个块。再由定理3.2，x和y包含在G′
的一个圈C中，事实上，C可能是包含x和y的若干个圈中的一个。因为G′不包含同态于K5或K3,3的子图，并且G′比G少一条边，由归纳假设，G′是平面图。设G′是G′的平面嵌入。我们选择C为包含x和y且把G′的尽可能多的面包围在其内部的圈。G′的在C的内部的桥称为内部桥，而G′在C外部的桥称为外部桥。我们给C赋予一个顺时针的方向。如果p和q是C上两个顶点，那么S[p,q]表示C上从p到q 顺时针方向的路径的顶点集。S]p,q[=S p,q?{p,q}。注意到，C的任意一个外桥在S[x,y]或S[y, x]上不可能有两个接触点，否则我们可以找到一个圈C′包含x和y且比C包围更多的面到其内部。
G是由平面图G′加上一条边x,y构造起来。考虑到对C的外桥和内桥的要求以及G不是平面图的假设，C一定有一个外桥E和一个内桥I。对于外桥E，E只能有两个接触点i和j，使得
i∈S]x,y并且 j∈S y,x[
I在C上可以有任意多个接触点，但I至少有两个接触点满足：a∈S]x,y并且 b∈S y,x[
否则(x,y)就可以加入到C的内部，从而得到G的平面嵌入，矛盾。
我们同时要求内桥还有接触点
c∈S]i,j和 d∈S j,i[
以使内桥I和外桥E不相容，这样，内桥就不能嵌入到C的外部面上去。
这样，我们就有以下几种情形(见图10.10)
在所有这些情形中，G中都有同态于K5或K3,3的子图，从而得到矛盾。
定理10.9：图G是平面图当且仅当G中既没有可以收缩成K5的子图，也没有可以收缩成K3,3的子图。
§10.5 平面图判定算法
*首先根据平面图的一些明显的充分条件和必要条件，我们可以对算法做一些简化。
(a) 如果G是不连通的，只要测试每个分支是否平面图；
(b) 如果G有割点，那么G是平面图当且仅当G的每个块是平面图；
(c) 删去环不影响图G的平面性；
(d) 把2度点压缩成一条边不影响平面性；
(e) 删去多重边不影响平面性；
(f) 如果E<9或V<5，则该图肯定是平面图；
(g) 如果E>3V?6，那么由推论10.7.2，该图肯定不是平面图。
°G允许的：设H是G的子图H的平面嵌入。如果存在G的一个平面嵌入G，使得H?G，那么H就称为是G允许的。
°例子：(见图10.11) (a)是原图G；(b)中实线图是G允许的。(c)中实线图是G不允许的。
°平面图判定算法：
1.找出G中一个圈C；
2.i←1；
3.G1←C; G1←C；
4.f←2；
5.EMBEDDABLE←true；
6.while f≠E?n+2 and EMBEDDABLE do
begin
7.找G中和G i相关的一个桥B；
8.对每个B找F(B,G i)；
9.if 对某个B, F B,G i=?then
begin
10.EMBEDDABLE←false；
11.输出信息：“G是非平面图”；
end；
12.if EMBEDDABLE then
begin
13.if 对某个B, F B,G i=1then F←F(B,G i)
else 设B是任意一个桥，F是F∈F B,G i的面；
14.找B中连接B在G i上两个接触点的一条路P i；
15.G i+1←G i+P i；
16.通过在G i的面F中画路P i得到G i+1的一个平面嵌入G i+1；
17.i←i+1；
18.f←f+1；
19.if f=E?n+2then 输出信息：“G是平面图”
end；
end；
*其中：F B,G i是桥B可嵌入G i中的面的集合。
°例子：(见图10.12)
§10.6 平面图的着色
°地图：连通无割边平面图的平面嵌入及其所有面称为平面地图或地图。地图的面称为"国家"。若两个国家的边界至少有一条公共边，则称这两个国家是相邻的。
°面着色：对地图G的每个国家涂上一种颜色，使相邻的国家涂不同的颜色，称为对G的一种正常面着色，若能用k种颜色给G进行正常面着色，就称G是k面可着色的。若G是k面可着色的，但不是(k?1)面可着色的，就称G的面色数为k，记作χ?G=k。
定理10.10：地图G是k面可着色的当且仅当它的对偶图G?是k可着色的。
证明：必要性。给G一种k面着色。由于G连通，由(10.1)式可知υG?=?(G)，即G的每个面中含G?的一个顶点。设v i?位于G的面R i内，将G?的顶点v i?着R i的颜色，易知，若v i?与v j?相邻，则由于R i与R j的颜色不同，所以v i?与v j?的颜色也不同，因而G?是k可着色的。类似地可证充分性。?
°四色猜想(1852年)：
任何一个地图可用四种颜色分别对每一个国家着一种颜色，使得有公共边界的任意两个国家着不同的颜色。
定理10.11：每个平面图都是5顶点可着色的。
证明：用反证法。假设定理不成立。则存在一个6临界平面图G。由于临界图是简单图，由推论10.7.3，推得δ≤5。另一方面由定理9.1知，δ≥5。所以δ=5。设v是G中一个5度顶点，并且设(V1,V2, V3,V4,V5)是G?v的一个正常5顶点着色；因为G是6临界的，这样的着色一定存在。由于G本身不是5顶点可着色的，v必须和染有这五种颜色中每一种颜色的顶点相邻。所以我们可以假定v的邻点沿着v顺时针方向是v1,v2,v3,v4,v5,这里v i∈V i,1≤i≤5。
用G ij表示由V i∪V j导出的子图G[V i∪V j]，于是v i和v j必属于G ij的同一个分支。因为不然的话，考察G ij的一个包含v i的分支。在这个分支中交换颜色i和j，得G?v的一个新的正常5顶点着色，其中只有四种颜色(除i外)分配给v的邻点，然而已经证明，这种情形不能发生，
所以v i和v j必属于G ij的同一个分支。设P ij是G ij中的(v i,v j)路，并将圈vv1P13v3v记为C(见图10.13)。由于C分隔v2和v4(在图10.13中，v2∈int C,而v4∈ext C)，从Jordan曲线定理推得，路P24必然和C相遇于某一点。因为G是平面嵌入，这个点必然是顶点，但这是不可能的。因为P24的顶点有颜色2和4，而C的顶点不具有这两种颜色。矛盾。?
定理10.12：下面3个断言是等价的：
(i)每个平面图都是4顶点可着色的；
(ii)每个平面嵌入都是4面可着色的；
(iii)每个简单2边连通3正则平面图都是3边可着色的。
证明：我们按照i?ii?iii?(i)的顺序来证明。
i?(ii)这是由定理10.10充分性推出的。
ii?(iii)假设(ii)成立。设G是简单2边连通3正则平面图，G是G 的平面嵌入，根据(ii)，G有一个正常的4面着色，由于用怎样的符号来表达颜色是无关紧要的，所以这里我们可以在整数模2的域中用向量c0=0,0,c1=1,0,c2=0,1,c3=(1,1)表示这四种颜色。把某边所分割的面的颜色之和作为颜色分配给该边，可以得到G的一个3边着色(见图10.14)。若c i,c j和c k是分配给顶点v关联的三个面的三种
颜色，则c i+c j,c j+c k以及c k+c i是分配给与v关联的三条边的颜色。由于G是2边连通的，所以每条边分隔两个不同的面，并且在这个方
案中，没有边分配到颜色c0。同样明显的是，与一个给定的顶点关联的三条边分配到不同的颜色。于是，我们获得一个G的，因而也是G 的正常3边着色。
iii?(i)假设(iii)成立，而(i)不成立。则存在一个5临界的平面图G。设G是G的一个平面嵌入。则(由习题)G是一个简单极大平面图H的生成子图。H的对偶图H?是一个2边连通3正则的简单平面图(由习题)。根据(iii)，H?有一个正常3边着色(E1,E2,E3)。对于i≠j，设H ij?
表示由E i∪E j导出的H?的子图。由于H?的每个顶点和E i的一条边以及E j的一条边关联，H ij?是不相交的圈的并图。因而(由习题)是2面可着色的，于是H?的每个面是H12?的一个面与H23?的一个面的交集。给定H12?和H23?的一个正常2面着色后，把分配给交集为f的那两个面的一对颜色分配给面f，得到H?的一个4面着色。由于H?=H12?∪H23?，容易验证H?的这个4面着色是正常的。由于H是G的母图，所以有5=χG≤χH=χ?(H?)≤4，这个矛盾说明了(i)确实是成立的。?
作业14：
1.证明：平图G是2面可着色的当且仅当G是Euler图。
2.利用Kuratowski定理证明：Petersen图是非平面图。
3.利用平面图判定算法找出下图(图10.14)的一个平面嵌入。
1
10 4
7
图10.14
答案(电子科大版)图论及其应用第一章
习题一： ● 。 证明:作映射f : v i ? u i (i=1,2….10) 容易证明，对?v i v j ∈E ((a)),有f (v i v j,),=,u i,u j,∈,E,((b)) (1≤ i ≤ 10, 1≤j ≤ 10 ) 由图的同构定义知，图(a)与(b)是同构的。 ● 5.证明：四个顶点的非同构简单图有11个。 证明：设四个顶点中边的个数为m ，则有： m=0: m=1 ： m=2： m=3： m=4： (a) v 23 4 (b)
m=5： m=6： 因为四个顶点的简单图最多就是具有6条边，上面所列出的情形是在不同边的条件下的不同构的情形，则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。 ● 11.证明：序列（7,6,5,4,3,3,2）和（6,6,5,4,3,3,1） 不是图序列。 证明：由于7个顶点的简单图的最大度不会超过6，因此序列（7,6,5,4,3,3,2）不是图序列； （6,6,5,4,3,3,1）是图序列 1 1 12312(1,1,,1,,,)d d n d d d d d π++=---是图序列 （5,4,3,2,2,0）是图序列，然而（5,4,3,2,2,0）不是图序列，所以（6,6,5,4,3,3,1）不是图序列。 ● 12.证明：若 ，则包含圈。 证明：下面仅对连通图的下的条件下进行证明，不连通的情形可以通过分成若干 个连通的情形来证明。设 , 对于中的路 若与邻接，则构成一个闭路。若是一条路，由于，因 此，对于，存在与之邻接，则构成一个圈。 ● 17.证明：若G 不连通，则连通。 证明：对于任意的 ,若与属于G 的连通分支，显然与在中连通；
电子科技大学研究生试题《图论及其应用》(参考答案)
电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：120分钟 一．填空题(每题3分，共18分) 1．4个顶点的不同构的简单图共有__11___个； 2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于3。则G 中顶点数至少有__9___个； 3．设n 阶无向图是由k(k ?2)棵树构成的森林，则图G 的边数m= _n-k____; 4．下图G 是否是平面图？答__是___; 是否可1-因子分解？答__是_. 5．下图G 的点色数=)(G χ______, 边色数=')(G χ__5____。 图G 二．单项选择(每题3分，共21分) 1．下面给出的序列中，是某简单图的度序列的是( A ) (A) (11123); (B) (233445); (C) (23445); (D) (1333). 2．已知图G 如图所示，则它的同构图是（ D ） 3． 下列图中，是欧拉图的是（ D ） 4． 下列图中，不是哈密尔顿图的是（B ） 5． 下列图中，是可平面图的图的是（B ） A C D A B C D
6．下列图中，不是偶图的是（ B ） 7．下列图中，存在完美匹配的图是（B ） 三．作图(6分) 1．画出一个有欧拉闭迹和哈密尔顿圈的图； 2．画出一个有欧拉闭迹但没有哈密尔顿圈的图； 3．画出一个没有欧拉闭迹但有哈密尔顿圈的图； 解： 四．(10分)求下图的最小生成树，并求其最小生成树的权值之和。 解：由克鲁斯克尔算法的其一最小生成树如下图： 权和为：20. 五．(8分)求下图G 的色多项式P k (G). 解：用公式 (G P k -G 的色多项式： )3)(3)()(45-++=k k k G P k 。 六．(10分) 22，n 3个顶点的度数为3，…，n k 个顶点的度数为k ，而其余顶点的度数为1，求1度顶点的个数。 解：设该树有n 1个1度顶点，树的边数为m. 一方面：2m=n 1+2n 2+…+kn k 另一方面：m= n 1+n 2+…+n k -1 v v 1 3 图G
08-图论-离散数学讲义-海南大学(共十一讲)
08-图论-离散数学讲义-海南大学(共十一讲)
8.图论Topics in Graph Theory §8.1 图Graphs G=
v i 起点弧尾， v j 终点弧头 TD(v i ):顶点的度degree: 以v i 为端点的边的数目。 OD(vi): 出度, 以v i 为起点的边的数目。 ID(v i ): 入度，以v i 为终点的边的数目。 TD(v i )= OD(vi)+ ID(v i ) OD=ID, TD=2|E|，E| =1/2*TD TD OD ID 为整个图的总度,出度,入度数。 路径path ： v i ······v j ， 以v i 为起点v j 为终点的顶点序列，相邻顶点相邻。 路径的长length : 路径上边的数目， 简单路径simple path :点都不重复的路径， 回路circuit : 首尾相接的路径， 简单回路simple circuit : 除起点和终点以外都不重复的路径， v i v j 连通connected : 有路径 v i ······v j 相连。 连通图: 任意两点都连通的图。 例 左图a,c,d,g 是简单路径 右图a,d,b,c,e 是简单路径。 f,e,a,d,b,a,f 是简单回路。 f,e,d,c,e,f 不是简单回路。 b f g d c e a f d c a e b
图论及其应用答案电子科大
图论及其应用答案电子科 大 Newly compiled on November 23, 2020
习题三： ● 证明：e 是连通图G 的割边当且仅当V(G)可划分为两 个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u ，v ）必含e . 证明：充分性: e 是G 的割边，故G ?e 至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G 中的u,v 不连通， 而在G 中u 与v 连通，所以e 在每一条(u,v)路上，G 中的(u,v)必含e 。 必要性：取12,u V v V ∈∈，由假设G 中所有(u,v)路均含有边e ，从而在G ?e 中不存在从 u 与到v 的路，这表明G 不连通，所以e 是割边。 ● 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 （1）→（2）： G 是块，任取G 的一点u ，一边e ，在e 边插入一点v ，使得e 成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G 中的u,v 位于同一个圈上，于是G 1中u 与边e 都位于同一个圈上。 （2）→（3）： G 无环，且任意一点和任意一条边都位于同一个圈上，任取G 的点u ，边e ，若u 在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u 不在e 上，由定理，e 的两点在同一个闭路上，在e 边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。
图论及其应用答案电子科大
图论及其应用答案电子科 大 This model paper was revised by the Standardization Office on December 10, 2020
习题三： 证明：e是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u，v）必含e . 证明：充分性: e是G的割边，故G ?e至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G中的u ,v不连通， 而在G中u与v连通，所以e在每一条(u ,v )路上，G中的(u ,v )必含e。 必要性：取12,u V v V ∈∈，由假设G中所有(u ,v )路均含有边e，从而在G ?e中不存在从 u与到v的路，这表明G不连通，所以e 是割边。 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 （1）→（2）： G是块，任取G的一点u，一边e，在e边插入一点v，使得e成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G中的u,v 位于同一个圈上，于是G 1中u 与边e都位于同一个圈上。 （2）→（3）： G无环，且任意一点和任意一条边都位于同一个圈上，任取G的点u ，边e ，若u在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u不在e上，由定理，e的两点在同一个闭路上，在e边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。 （3）→（1）： G连通，若G不是块，则G中存在着割点u，划分为不同的子集块V 1, V 2, V 1, V 2无环，12,x v y v ∈∈，点u在每一条(x ,y )的路上，则与已知矛盾，G是块。 7.证明：若v 是简单图G 的一个割点，则v 不是补图G ?的割点。 证明：v是单图G的割点，则G ?v有两个连通分支。现任取x ,y ∈V (G ?v ), 如果x ,y 不在G ?v的同一分支中，令u是与x ,y处于不同分支的点，那么，x ,与y在G ?v的补图中连通。若x ,y在G ?v的同一分支中，则它们在G ?v的补图中邻接。所以，若v是G 的割点，则v不是补图的割点。 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给出相应的最小点割和最小边割。 解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）}
图论及其应用第三章答案电子科大
习题三： ● 证明：e 是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u ，v ）必含e . 证明：充分性: e 是G 的割边，故G ?e 至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G 中的u,v 不连通，而在G 中u 与v 连 通，所以e 在每一条(u,v)路上，G 中的(u,v)必含e 。 必要性：取12,u V v V ∈∈，由假设G 中所有(u,v)路均含有边e ，从而在G ?e 中不存在从u 与到v 的 路，这表明G 不连通，所以e 是割边。 ● 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 （1）→（2）： G 是块，任取G 的一点u ，一边e ，在e 边插入一点v ，使得e 成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G 中的u,v 位于同一个圈上，于是G 1中u 与边e 都位于同一个圈上。 （2）→（3）： G 无环，且任意一点和任意一条边都位于同一个圈上，任取G 的点u ，边e ，若u 在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u 不在e 上，由定理，e 的两点在同一个闭路上，在e 边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。 （3）→（1）： G 连通，若G 不是块，则G 中存在着割点u ，划分为不同的子集块V 1, V 2, V 1, V 2无环， 12,x v y v ∈∈，点u 在每一条(x,y)的路上，则与已知矛盾，G 是块。 ● 7.证明：若v 是简单图G 的一个割点，则v 不是补图G ?的割点。 证明：v 是单图G 的割点，则G ?v 有两个连通分支。现任取x,y ∈V(G ?v), 如果x,y 不在G ?v 的同一分支中，令u 是与x,y 处于不同分支的点，那么，x,与y 在G ?v 的补图中连通。若x,y 在G ?v 的同一分支中，则它们在G ?v 的补图中邻接。所以，若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 的子图，举例说明：有可能k(H)> k(G). 解： 通常k (H ) 第二章 图的连通性 在第一章中已经定义连通图是任二顶点间都有路相连的图。对于连通图，其连通的程度也有高有低。例如，下列三个图都是连通图。对于图G 1，删除一条边或一个顶点便可使其变得不连通；而对于图G 2，至少需要删除两条边才能使其不连通，也可以删除一个顶点使其不连通；对于图G 3，要破坏其连通性，则至少需要删除三条边或三个顶点。 本章主要讨论如何通过图的顶点集、边集和不交的路集合的结构性质来获知图的连通性程度。通过研究割边和割点来刻画1连通图的特性；定义连通度和边连通度来度量连通图连通程度的高低；通过不交路结构和元素的共圈性质来反映图的2连通和k 连通性。 §2.1 割点和割边 定义2.1.1 设)(G V v ∈，如果)()(G w v G w >?，则称v 为G 的一个割点。 （注：该定义与某些著作中的定义有所不同，主要是在环边的顶点是否算作割点上有区别）。 例如，下图中u , v 两点是其割点。 定理2.1.1 如果点v 是简单图G 的一个割点，则边集E (G)可划分为两个非空子集1E 和2E ，使得][1E G 和][2E G 恰好有一个公共顶点v 。 证明留作习题。 推论2.1.1 对连通图G ，顶点v 是G 的割点当且仅当v G ?不连通。 定理2.1.2 设v 是树T 的顶点，则v 是T 的割点当且仅当1)(>v d 。 证明：必要性：设v 是T 的割点，下面用反证法证明1)(>v d 。 若0)(=v d ，则1K T ?，显然v 不是割点。 若1)(=v d ，则v T ?是有1)(??v T ν条边的无圈图，故是树。从而)(1)(T w v T w ==?。因此v 不是割点。 以上均与条件矛盾。 充分性：设1)(>v d ，则v 至少有两个邻点u ,w 。路uvw 是T 中一条),(w u 路。因T 是树，uvw 是T 中唯一的),(w u 路，从而)(1)(T w v T w =>?。故v 是割点。证毕。 第八讲图论中的匹配与逻辑推理问题 先看一个例题.中、日、韩三个足球队进行比赛，已知A不是第一名，B不是韩国队，也不是第二名，第一名不是日本队，中国队第二.问A、B、C各代表哪国队？各是第几名？ 一般解这类题都归于逻辑推理类问题. 我们先来降低难度.先只要求你判断出中、日、韩各是第几名（不必判断A、B、C）.可以把中、日、韩各用一个点代表，列于上一行.第一、二、三名各用一个点代表，列于下一行，记为： V1=｛中，日，韩｝，V2=｛第1名，第2名，第3名｝. V1中的点与V2中某一个点有肯定关系的，就画一条实线，如和②.否定关系的两点之间画一条虚线，如不是②；不是①.把已知条件不加任何推理地表现于图上.虚线2条，实线1条，共3条线. 现在，有两个明显的事实；第一，V1中每点有且只有一条实线与V2中相应点配对，V2中每点有且只有一条实线与V1中相应点配对.V1内部点之间不会有线相联结，V2内部点之间也不会有线相联结.第二，从V1（或V2）中某一个点，例如说a点如发出了一条实线向着V2（或V1）中某一个点，例如说x点，那么a点与V2（或V1）中其他点之间必然只能用虚线联结.（这是逻辑推理中的排它性） 由此，我们很容易将中、日、韩的名次判出. 这样的问题，抽象起来可归属于图论中称之为“二分图的匹配”问题. 图论的名词术语太多，这里不作详细定义，只是描述性介绍一下，大家以前在“一笔画”等讲中已初步接触.所谓二分图，就是顶点集合可以划分成两个部分，V=V1＋V2，如V1有p个点，记为V1=｛v1，v2…，v p｝，V2有q个点，记为V2=｛v p+1，v p+2…，v p+q｝，而V1中任意一点，不会 图和子图 图 图 G = (V, E)， 其中 V = {νv v v ,......,,21} V ---顶点集， ν---顶点数 E = {e e e 12,,......,ε} 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 为简单图，则 εν≤?? ?? ?2 。 1.1.2 n ( ≥ 4 )个人中，若每4人中一定有一人认识其他3人，则一定有一 人认识其他n-1人。 同构 在下图中， 图G 恒等于图H , 记为 G = H ? V （G)=V(H), E(G)=E(H)。 图G 同构于图F ? V(G)与V(F), E(G)与E(F)之间各存在一一对应关系，且这二对应关系保持关联关系。 记为 G ?F 。 注 往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。 d e f G = (V, E) y z w c G =(V , E ) w c y z H =(V ?, E ?) ?a ? c ? y ? e ?z ? F=(V ??, E ??) 图论及其应用 学时：40 学分：2 课程属性：专业选修课开课单位：理学院 先修课程：高等代数后续课程：无 一、课程的性质 《图论及其应用》是数学与应用数学专业的专业选修课程。 二、教学目的 通过教学，使学生掌握图论及其算法的基本理论和基本技巧，初步掌握图论及其算法的基本应用手段、基本算法设计及编程，并能用所学理论解决一些应用问题。 三、教学内容 1.图的基本概念 2.图的连通性 3.树的基本性质及其应用 4.Euler Graphs and Hamilton Graphs with Applications 5.平面图性质 6.匹配，求最大匹配算法及应用 7.图的染色及应用 8.极图理论 四、学时分配 章课程内容学时 1 图的基本概念 4 2 图的连通性 6 3 树的基本性质及其应用 6 4 Euler Graphs and Hamilton Graphs with Applications 4 5 平面图性质 6 6 匹配，求最大匹配算法及应用 6 7 图的染色及应用 4 8 极图理论 4 合计40 五、教学方式 本课程采用多媒体课堂讲授，结合实际范例深入浅出讲解讨论。 六、考核方式 本课程考核采用平时与期末考核相结合的办法，特别注重平时的考核，作业采用简单练习、论文等形式，期末考试采用简单考题或论文形式。 七、教材及教学参考书 参考教材： [1] J.A.Bondy and U.S.R.Murty. Graph Theory with Applications, The Macmillan Press LTD,1976. [2] 蒋长浩．图论与网络流．北京：中国林业出版社，2000． 参考书目： [1] Bela Bollobas．Modern Graph Theory（现代图论，影印版）．北京：科学出版社，2001． [2] 殷剑宏、吴开亚．图论及其算法．合肥：中国科学技术大学出版社，2003． [3] 谢金星、邢文训．网络优化．北京：清华大学出版社．2000． [4] 程理民、吴江、张玉林．运筹学模型与方法教程．北京：清华大学出版社，2000． [5] 三味工作室．SPSS V10.0 for Windows 实用基础教程．北京：北京希望电子出版社2001． [６] 孙魁明、张海彤．Mathematica工具软件大全．北京：中国铁道出版社，1994． [７] 楼顺天、于卫、闫华梁．MATLAB程序设计语言．西安：西安电子科技大学出版社，1997．八、教学基本内容及要求 第一章图的基本概念 1．教学基本要求 掌握的图的基本概念、特殊图概念，了解最短路问题。 2．教学具体内容 图的基本概念，路和圈，最短路问题。 第三章 匹配理论 §3.1 匹配与最大匹配 定义3.1.1 设G 是一个图, )(G E M ?，满足:对i e ?,M e j ∈，i e 与j e 在G 中不相邻，则称M 是G 的一个匹配。对匹配M 中每条边uv e =，其两端点 u 和 v 称为被匹配M 所匹配，而 u 和 v 都称为是M 饱和的(saturated vertex )。 注:每个顶点要么未被M 饱和, 要么仅被M 中一条边饱和。 定义3.1.2 设M 是G 的一个匹配, 若G 中无匹配M ′, 使得||||M M >′, 则称M 是G 的一个最大匹配；如果G 中每个点都是M 饱和的, 则称M 是G 的完美匹配(Perfect matching ). 显然, 完美匹配必是最大匹配。 例如，在下图G 1中，边集{e 1}、{e 1,e 2}、{e 1,e 2,e 3}都构成匹配，{e 1,e 2,e 3}是G 1的一个最大匹配。在 G 2中，边集{e 1,e 2,e 3,e 4}是一个完美匹配，也是一个最大匹配。 定义3.1.3 设M 是G 的一个匹配, G 的M 交错路是指其边M 和M G E \)(中交替出现的路。如果G 的一条M 交错路(alternating path)的起点和终点都是M 非饱和的，则称其为一条M 可扩展路或M 增广路(augmenting path)。 定理 3.1.1(Berge,1957) 图G 的匹配M 是最大匹配的充要条件是G 中不存在M 可扩展路。 证明:必要性:设M 是G 的一个最大匹配。如果G 中存在一个M 可扩展路P ,则将P 上所有不属于M 的边构成集合M ′。显然M ′也是G 的一个匹配且比M 多一条边。这与M 是最大匹配相矛盾。 充分性:设G 中不存在M 可扩展路。若匹配M 不是最大匹配，则存在另一匹配M ′,使 ||||M M >′. 令 ][M M G H ′⊕=，(M M M M M M ′?′=′⊕∩∪称为对称差)。 则H 中每个顶点的度非1即2(这是因为一个顶点最多只与M 的一条边及M ′的一条边相关联)。故H 的每个连通分支要么是M 的边与M ′的边交替出现的一个偶长度圈，要么是M 的边与M ′的边交替出现的一条路。 由于||||M M >′，H 的边中M ′的边多于M 的边，故必有H 的某个连通分支是一条路，且始于M ′的边又终止于M ′的边。这条路是一条M 可扩展路。这与条件矛盾。 证毕。 习题三： ● 证明：是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意及, G 中的路必含. 证明：充分性: 是的割边，故至少含有两个连通分支，设是其中一个连通分支的顶点集，是其余分支的顶点集，对12,u V v V ?∈?∈，因为中的不连通，而在中与连通，所以在每一条路上，中的必含。 必要性：取12,u V v V ∈∈，由假设中所有路均含有边，从而在中不存在从与到的路，这表明不连通，所以e 是割边。 ● 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 ： 是块，任取的一点，一边，在边插入一点，使得成为两条边，由此得到新图，显然的是阶数大于3的块，由定理，中的u,v 位于同一个圈上，于是 中u 与边都位于同一个 圈上。 ： 无环，且任意一点和任意一条边都位于同一个圈上，任取的点u ，边e ，若在上，则三个不同点位于同一个闭路，即位于同一条路，如不在上，由定理，的两点在同一个闭路上，在边插入一个点v ，由此得到新图，显然的是阶数大于3的块，则两条边的三个不同点在同一条路上。 ： 连通，若不是块，则中存在着割点，划分为不同的子集块,,,无环，12,x v y v ∈∈，点在每一条的路上，则与已知矛盾，是块。 ● 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 的子图，举例说明：有可能k(H)> k(G). 解： 通常. 整个图为，割点左边的图为的的子图， ，则. e H 数学竞赛：图论讲义 大连市第二十四中学 邰海峰 重要的概念与定理 完全图 每两个顶点之间均有边相连的简单图称为完全图,有n 个顶点的完全图(n 阶完全图)记为n K . 顶点的度 图G 中与顶点v 相关联的边数(环按2条边计算)称为顶点v 的度(或次数),记为()d v .()G δ与()G ?分别表示图G 的顶点的最小度与最大度.度为奇数的顶点称为奇顶点,度为偶数的顶点称为偶顶点. 树 没有圈的连通图称为树,用T 表示,其中度为1的顶点称为树叶(或悬挂点).n 阶树常表示为n T . k 部图 若图G 的顶点集V 可以分解为k 个两两不相交的非空子集的并,即 1,()k i i j i V V V V i j == =?≠ 并且同一子集i V (1,2,,)i k =内任何两个顶点没有边相连,则称这样的图为k 部图,记作12(,,,;)k G V V V E =. 2部图又叫做偶图,记为(,;)G X Y E =. 完全k 部图 在一个k 部图12(,,,;)k G V V V E =中,i i V m =(1,2,,)i k =,若对任意 ,,(,,1,2,,)i i j j v V v V i j i j k ∈∈≠=均有边连接i v 和j v ,则称图G 为完全k 部图,记为12,,,k m m m K . 欧拉迹 包含图中所有边的迹称为欧拉迹.起点与终点重合的欧拉迹称为闭欧拉迹. 欧拉图 包含欧拉迹的图为欧拉图. 欧拉图必是连通图. 哈密顿链(圈) 经过图上各顶点一次并且仅仅一次的链(圈)称为哈密顿链(圈).包含哈密顿圈的图称为哈密顿图. 平面图 若一个图G 可画在平面上,即可作一个与G 同构的图G ',使G '的顶点与边在同一平面内,且任意两边仅在端点相交,则图G 称为平面图. 一个平面图的顶点和边把一个平面分成若干个互相隔开的区域,称为平面图的一个面,在所有边的外面的面称为外部面,其余的称为内部面. 竞赛图 有向完全简单图称为竞赛图.有n 个顶点的竞赛图记作n K . 有向路 在有向图(,)D V U =中,一个由不同的弧组成的序列12,,,n u u u ,其中i u 的起点为i v ,终点为1(1,2,,)i v i n +=,称这个序列为从1v 到1n v +的有向路(简称路),n 为这个路的长,1v 为 习题一(yangchun)： 4.证明下面两图同构。 证明:作映射f : v i ? u i (i=1,2….10) 容易证明，对?v i v j ∈ E ((a)),有f (v i v j,),=,u i,u j,∈,E,((b)) (1≤ i ≤ 10, 1≤j ≤ 10 ) 由图的同构定义知，图(a)与(b)是同构的。 5.证明：四个顶点的非同构简单图有11个。 证明：设四个顶点中边的个数为m ，则有： m=0: m=1 ： m=2： m=3： m=4： (a) v 23 4 (b) m=5： m=6： 因为四个顶点的简单图最多就是具有6条边，上面所列出的情形是在不同边的条件下的不同构的情形，则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。 11.证明：序列（7,6,5,4,3,3,2）和（6,6,5,4,3,3,1）不是图序列。 证明：由于7个顶点的简单图的最大度不会超过6，因此序列（7,6,5,4,3,3,2）不是图序列； （6,6,5,4,3,3,1）是图序列 1 1 12312(1,1,,1,,,)d d n d d d d d π++=--- 是图序列 （5,4,3,2,2,0）是图序列，然而（5,4,3,2,2,0）不是图序列，所以（6,6,5,4,3,3,1）不是图序列。 ● 12.证明：若 ，则包含圈。 证明：下面仅对连通图的下的条件下进行证明，不连通的情形可以通过分成若干 个连通的情形来证明。设 , 对于中的路 若与邻接，则构成一个闭路。若是一条路，由于，因 此，对于，存在与之邻接，则构成一个圈。 ● 17.证明：若G 不连通，则连通。 证明：对于任意的 ,若与属于G 的连通分支，显然与在中连通； 第八章独立集和团 §8.1 独立集 °独立集：设S是V的一个子集，若S中任意两个顶点在G中均不相邻，则称S为G的一个独立集。 °最大独立集：G的一个独立集S称为G的最大独立集，是说：G不包含适合S′>S的独立集S′。 °例子：(见图8.1) °覆盖：G的一个覆盖是指V的子集K，使得G的每条边都至少有一个端点属于K。 °例子：在图8.1中，两个独立集都是覆盖的补集。 定理8.1：设S?V，则S是G的独立集当且仅当V\S是G的覆盖。证：按定义，S是G的独立集当且仅当G中每条边的两个端点都不同时属于S，即当且仅当G的每条边至少有一个端点属于V\S，亦即当且仅当V\S是G的覆盖。? °独立数：G的最大独立集的顶点数称为G的独立数，记为α(G)。°覆盖数：G的最小覆盖的顶点数称为G的覆盖数，记为β(G)。 推论8.1：α+β=υ。 证：设S是G的一个最大独立集，K是G的一个最小覆盖。由定理8.1，V\K是独立集，而V\S是覆盖。因此 υ?β=V\K≤α (8.1) υ?α=V\S≥β (8.2) 结合8.1式和(8.2)式，即得α+β=υ。? °边覆盖：G的一个边覆盖是指E的一个子集L，使得G的每个顶点都是L中某条边的端点。 °边独立集：即对集。 *注意：边覆盖并不总是存在的，G有边覆盖，当且仅当δ>0。 °边独立数和边覆盖数：最大对集的边数称为边独立数，记作α′G;最小边覆盖的边数称为边覆盖数，记作β′(G)。 *注意：对集的补集不一定是边覆盖，边覆盖的补集也不一定是对集。定理8.2 (Gallai)：若δ>0,则α′+β′=υ。 证：设M是G的一个最大对集，U是M非饱和顶点集。由于δ>0且M是最大对集，所以存在|U|条边的一个集E′，它的每条边都和U 的每个顶点相关联。显然，M∪E′是G的边覆盖，因而 β′≤M∪E′=α′+υ?2α′=υ?α′ 即α′+β′≤υ (8.3) 再设L是G的一个最小边覆盖，置H=G[L]，并且设M是H的一个最大对集。用U记H中的M非饱和顶点集。由于M是最大对集，所以H[U]没有连杆，从而 L?M=L\M≥U=υ?2|M| 又因为H是G的子图，所以M也是G的对集，从而 α′+β′≥M+L≥υ (8.4) 综合(8.3)式和(8.4)式，即得α′+β′=υ。? 图论的发展及其在生活中的应用 数学与应用数学张佳丽 指导教师刘秀丽 摘要主要介绍了图论的起源与发展及其生活中的若干应用，如：渡河问题、旅游推销员问题、最小生成树问题、四色问题、安排问题、中国邮递员问题。同时也涉及到了几种在图论中应用比较广泛的方法，如：最邻近法、求最小生成树的方法、求最优路线的方法等。 关键词图论生活问题应用 Graph Theory Development and the Application in Life Mathematics and applied mathematics Zhang Jiali Tutor Liu Xiuli Abstract This paper mainly introduces the origin and development of graph theory and its several applications in our life, such as: crossing river problem, traveling salesman problem, minimum spanning tree problem, four color problem，arrangement problem，Chinese postman problem．It also researches several methods that are more widely applied in graph theory, for example: the method of most neighboring, the method of solving the minimum spanning tree，the method of the best route，and so on． Key words graph theory life problem application 引言 图论是一门古老的学科，是数学中有广泛应用的一个分支，与其他的数学分支，如群论、矩阵论、概率论、拓扑学、数分析等有着密切的联系．图论中以图为研究对象，图形中我们用点表示对象，两点之间的连线表示对象之间的某种特定的关系．事实上，任何一个包含了二元关系的系统都可以用图论来模拟．而且,图论能把纷杂的信息变的有序、直观、清晰．由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点间连接与否尤为重要，而图形的位置、大小、形状及连接线的曲直长短则无关紧要．图论在自然科学、社会科学等各个领域都有广泛的应用．随着科学的发展，以及生产管理、军事、交通运输等方面提出了大量实际的需要，图论的理论及其应用研究得到飞速发展。从20世纪50年代以后，由于计算机的迅速发展，有力地推动了图论的发展，加速了图论向各个学科的渗透，尤其是网络理论的建立，图论与线性规划、动态规划等优化理论和方法互相渗透。同时，计算机的发展使图论成为数学领域中发展最快的分支 第一章习题 1. 对任何简单图G ，(1) 证明：(1) ()2 G υυε?≤；(2) (1) ()2 G υυε?= 当且仅当G K ν?。 2. 证明：(1) ,()m n K mn ε=；(2) 若G 是完全二部图，则2 ()4 G υε≤ 。 3. 图G 有21条边，12个3度顶点，其余顶点的度均为2，求图G 的阶数。 4. 证明：任何简单图必有至少两个顶点具有相等的度。 5. 设G 是简单图，求G 的所有不同的生成子图的个数（包括G 本身和空图）。 6. 证明：任何图中，奇度顶点的个数总是偶数（包括0）。并由此证明：在任一次聚会上握过奇数 次手的人必为偶数个。 7. 证明或反证：如果u 和v 是图G 中仅有的具有奇数度的顶点，则G 包含一条u , v 路。 8. 证明：若4υ≥且1+=νε，则存在)(G V v ∈使得3)(≥v d 。由此证明： n 个球队比赛（4n ≥）， 已赛完n +1场，则必定有一个球队已参加过至少3场比赛。 9. 在一个运动联盟中，将所有运动队组织成两个赛区，每个赛区有13个队，能否恰当安排比赛使 得每个队在其所在赛区中进行9场比赛而与另一个赛区中的运动队进行4场比赛？ 10. 在平面上有n 个点12{,,,}n S x x x =???，其中任两个点之间的距离至少是1。证明在这n 个点中， 距离为1 的点对数不超过3n 。 11. 某次会议有n 人参加，其中有些人互相认识，但每两个互相认识的人，都没有共同的熟人，每 两个互不认识的人都恰好有两个共同的熟人。证明每一个参加者都有同样数目的熟人。 12. 在一个化学实验室里，有n 个药箱，其中每两个不同的药箱恰有一种相同的化学品，而且每种 化学品恰好在两个药箱中出现，问：（1）每个药箱有几种化学品？（2）这n 个药箱中共有几种不同的化学品？ 13. 在一次舞会中，A 、B 两国留学生各(2)n n >人，A 国每个学生都与B 国一些(不是所有)学生跳 过舞，B 国每个学生至少与A 国一个学生跳过舞。证明一定可以找到A 国两个学生12,a a 及B 国两个学生12,b b ，使得1a 和12,b a 和2b 跳过舞，而1a 和22,b a 和1b 没有跳过舞。 14. 证明：2ε δυ ≤ ≤Δ，（其中 2ε υ 称为顶点平均度）。 15. 令G 是至少有两个顶点的图。证明或反证：(1) 删除一个度为()G Δ的顶点不会增加顶点的平均 度；(2) 删除一个度为()G δ的顶点不会减小顶点的平均度。 16. 令G 是一个顶点平均度为2a ε υ = 的无圈图。(1) 证明：G x ?的顶点平均度至少为a 当且仅当 ()2 a d x ≤ 。(2) 利用(1)的结果给出一个算法来证明：如果0a >，则G 有一个最小度大于2a 的 子图。 定理10.8 (Kuratowski定理)：一个图G是平面图当且仅当G中不包含同态于K5或K3,3的子图。 证明：在10.3节，我们已证明了K5和K3,3不是平面图，再由定理10.4可知，当一个图G包含同态于K5或K3,3的子图，则G不是平面图。从而定理的必要性得证。 现在我们来证明定理的充分性。我们对G的边数归纳证明。当G 只有m=1条边时，显然G是平面图。现在我们假设当G的边数m< N(N≥2)时，G是平面图。现在设G有m=N条边。我们证明：如果G不包含同态于K5和K3,3的子图，但G不是平面图，则导出矛盾。设G不是平面图，则有以下几个结论： (a)G必须是连通的； (b)G不包含割点； (c)如果G中任一边(x, y)被删除，则所得到的图G′中存在包含x和y 的圈。 我们来证明结论(c)。注意到G′是连通的，这因为G不包含割点。如果G′中不存在包含x和y的圈，那么从x到y的每条路径都经过一个公共点z。换句话说，z是G′的一个割点。那么G′可以在z处分解成两个连通分支G1′包含x和z和G2′包含y和z。我们在G1′中加入边xz，得G1"，在G2′中加入边yz的G2"。这时G1"和G2"都不包含同态于K5和K3,3的子图。这是因为G1′是G的子图不可能包含同态于K5或K3,3的子图，假如G1"中包含这样的子图，则该子图必然经过边xz，而在G中可找到一条从z到y的路径P再加上边yx代替xz，从而G中存在同 态于K5或K3,3的子图，这与假设矛盾。同理可证对G2"结论成立。 由归纳假设，G1"和G2"是平面图。根据定理10.5，我们可以找到G1"的平面嵌入，使得xz在外部面上，也可以找到G2"的平面嵌入，使得yz 在外部面上，令G1"和G2"在z处相交，并用xy边取代xz和yz边，则可以得到G的一个平面嵌入，这与G不是平面图的假设矛盾。从而证明了G′不包含割点。即G′是一个块。再由定理3.2，x和y包含在G′ 的一个圈C中，事实上，C可能是包含x和y的若干个圈中的一个。因为G′不包含同态于K5或K3,3的子图，并且G′比G少一条边，由归纳假设，G′是平面图。设G′是G′的平面嵌入。我们选择C为包含x和y且把G′的尽可能多的面包围在其内部的圈。G′的在C的内部的桥称为内部桥，而G′在C外部的桥称为外部桥。我们给C赋予一个顺时针的方向。如果p和q是C上两个顶点，那么S[p,q]表示C上从p到q 顺时针方向的路径的顶点集。S]p,q[=S p,q?{p,q}。注意到，C的任意一个外桥在S[x,y]或S[y, x]上不可能有两个接触点，否则我们可以找到一个圈C′包含x和y且比C包围更多的面到其内部。 G是由平面图G′加上一条边x,y构造起来。考虑到对C的外桥和内桥的要求以及G不是平面图的假设，C一定有一个外桥E和一个内桥I。对于外桥E，E只能有两个接触点i和j，使得 i∈S]x,y并且 j∈S y,x[ I在C上可以有任意多个接触点，但I至少有两个接触点满足：a∈S]x,y并且 b∈S y,x[ 否则(x,y)就可以加入到C的内部，从而得到G的平面嵌入，矛盾。 学号：201321010808 姓名：马涛 习题1 4．证明图1-28中的两图是同构的 证明 将图1-28的两图顶点标号为如下的(a)与(b)图 作映射f : f(v i )→u i (1≤ i ≤ 10) 容易证明，对?v i v j ∈E((a)),有f(v i v j )=u i u j ∈E((b)) (1≤ i ≤ 10, 1≤j ≤ 10 ) 由图的同构定义知，图1-27的两个图是同构的。 6．设G 是具有m 条边的n 阶简单图。证明：m =???? ??2n 当且仅当G 是完全图。 证明 必要性 若G 为非完全图，则? v ∈V(G),有d(v)< n-1 ? ∑ d(v) < n(n-1) ? 2m 证明 由于G 为k 正则偶图，所以，k | V 1 | =m = k | V 2 | ? ∣V 1∣= ∣V 2 ∣。 12.证明：若δ≥2，则G 包含圈。 证明 只就连通图证明即可。设V(G)=｛v 1,v 2,…,v n ｝,对于G 中的路v 1v 2…v k ,若v k 与v 1邻接，则构成一个圈。若v i1v i2…v in 是一条路，由于δ≥ 2，因此，对v in ，存在点v ik 与之邻接，则v ik ?v in v ik 构成一个圈 。 17.证明：若G 不连通，则G 连通。 证明 对)(,_G V v u ∈?,若u 与v 属于G 的不同连通分支，显然u 与v 在_ G 中连通；若u 与v 属于g 的同一连通分支，设w 为G 的另一个连通分支中的一个顶点，则u 与w ，v 与w 分别在_ G 中连通，因此，u 与v 在_ G 中连通。 习题2 证明：每棵恰有两个1度顶点的树均是路。 证明：设树T 为任意一个恰有两个1度顶点的树，则T 是连通的，且无圈，令V 1 、V 2 为度为1的顶点，由于其他的顶点度数均为0或者2，且T 中无圈，则从V 1到V 2 有且只有一条连通路。所以，每棵恰有两个1度顶点的树均是路。得证。 证明：正整数序列),...,,(21n d d d 是一棵树的度序列当且仅当)1(21-=∑=n d n i i 。 证明：设正整数序列),...,,(21n d d d 是一棵树T 的度序列，则满足E d n i i 21 =∑=，E 为T 的边数，又有边数和顶点的关系1+=E n ，所以)1(21 -=?∑=n d n i i 证明：若e 是n K 的边，则3)2()(--=-n n n n e K τ。 若e 为Kn 的一条边，由Kn 中的边的对称性以及每棵生成树的边数为n-1，Kn 的所有生成树的总边数为：2)1(--n n n ，所以，每条边所对应的生成树的棵数 为： 32 2)1(2 1 )1(--=--n n n n n n n ，所以，K n - e 对应的生成树的棵数为： 332)2(2)(----=-=-n n n n n n n n e K τ Kruskal 算法能否用来求：图论讲义第2章-连通性
第八讲 图论中的匹配与逻辑推理问题
图论及其应用
图论及其应用(精)
图论讲义第3章-匹配问题
图论及其应用 答案电子科大
数学竞赛：图论讲义
图论及其应用第一章答案(电子科大版)
图论讲义12 (1)
图论的发展及其在现实生活中的几个应用
中科院研究生院图论讲义习题1
图论讲义15
图论及其应用1-3章习题答案(电子科大) (1)