电子科技大学图论及其应用5班第4-5章作业

电子科技大学研究生试题《图论及其应用》(参考答案)考试时间：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 ）AC DA B CD6．下列图中，不是偶图的是（ 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 13图G由上面两式可得：n 1=n 2+2n 3+…+(k -1)n k七．证明：(8分) 设G 是具有二分类(X,Y)的偶图，证明(1)G 不含奇圈；（2）若|X |≠|Y |，则G 是非哈密尔顿图。

图和子图 图和简单图图 G = (V, E)V ---顶点集，ν---顶点数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 ⇔ VG)=V(H), E(G)=E(H)。

图G 同构于图F ⇔ V(G)与V(F), E(G)与E(F)之间 各 存在一一对应关系，且这二对应关系保持关联关系。

记为 G ≅F。

注 往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。

de f G = (V , E )yz w cG =(V , E )w cyz H =(V ’, E ’)’a ’c ’y ’e ’z ’F =(V ’’, E ’’)注 判定两个图是否同构是NP-hard 问题。

完全图(complete graph) Kn空图（empty g.） ⇔ E = ∅ 。

V’ ( ⊆ V) 为独立集 ⇔ V’中任二顶点都互不相邻。

电⼦科技⼤学《图论及其应⽤》复习总结--第四章欧拉图与哈密尔顿图第四章欧拉图与哈密尔顿图(⼀)、欧拉图及其性质(1)、问题背景---欧拉与哥尼斯堡七桥问题问题：对于图G，它在什么条件下满⾜从某点出发，经过每条边⼀次且仅⼀次，可以回到出发点？注：⼀笔画----中国古⽼的民间游戏（存在欧拉迹）要求：对于⼀个图G, 笔不离纸, ⼀笔画成.拓展：三笔画：在原图上添加三笔，可使其变为欧拉图。

定义1 对于连通图G，如果G中存在经过每条边的闭迹，则称G为欧拉图，简称G为E图。

欧拉闭迹⼜称为欧拉环游，或欧拉回路。

定理1 下列陈述对于⾮平凡连通图G是等价的：(1) G是欧拉图；(2) G的顶点度数为偶数；(3) G的边集合能划分为圈。

推论1 连通图G是欧拉图当且仅当G的顶点度数为偶。

推论2 连通⾮欧拉图G存在欧拉迹当且仅当G中只有两个顶点度数为奇数。

证明：若G和H是欧拉图，则G×H是欧拉图。

若G是⾮平凡的欧拉图，则G的每个块也是欧拉图。

(⼆)、Fleury算法(欧拉图中求出⼀条具体欧拉环游的⽅法)⽅法是尽可能避割边⾏⾛(三)、中国邮路问题（最优欧拉环游，管梅⾕）定理2 若W是包含图G的每条边⾄少⼀次的闭途径，则W具有最⼩权值当且仅当下列两个条件被满⾜：(1) G的每条边在W中最多重复⼀次；(2) 对于G的每个圈上的边来说，在W中重复的边的总权值不超过该圈⾮重复边总权值。

(四)、哈密尔顿图的概念定义1 ：如果经过图G的每个顶点恰好⼀次后能够回到出发点，称这样的图为哈密尔顿图，简称H图。

所经过的闭途径是G的⼀个⽣成圈，称为G的哈密尔顿圈。

定义2: 如果存在经过G的每个顶点恰好⼀次的路，称该路为G的哈密尔顿路，简称H路。

(五)、哈密尔顿图性质与判定1、性质定理【必要条件】；定理1 (必要条件) 若G为H图，则对V(G)的任⼀⾮空顶点⼦集S，有：w(G−S)≤|S|注：不等式为G是H图的必要条件，即不等式不满⾜时，可断定对应图是⾮H、图。

《图论及其应用》大作业指导老师郝荣霞知行1503 徐鹏宇 152912002.1.9证明：若G是森林且恰有2k个奇点，则在G中有k条边不重的路P1,P2......P K,使得E(G)=E(P1) E(P2) ...... E(P K)。

证明：对奇点数k使用数学归纳法。

①当k=1时，G是森林，且有且只有2个奇点⇒G只能为一颗树，且G的所有奇度顶点为两个1度顶点⇒G是一条路⇒满足题设②假设当k=t时，结论成立。

接下来考虑k=t + 1时的情况。

在G中一个分支中取两个叶子点u与v，令P是连接该两个顶点的唯一路。

由于P上除u，v以外的点均被P经过两次，即G-P后除u，v以外的点奇偶性不变。

⇒则G–P是有2t个奇度顶点的森林⇒由归纳假设知，G–P可以分解为t条边不重合的路之并，即E(G-P)=E(P1) E(P2) ...... E(P t)。

⇒则G可分解为t+1条边不重合的路之并，即E(G)=E(P1) E(P2) ...... E(P t) E(P)。

⇒即证。

2.4.4证明：若e 是K n 的边，则τ（K n -e ）=（n-2）n n-3证明：由定理2.9：τ（K n ）=n n-2由于τ（K n -e ）=τ（K n ）-τ（含有e 的生成树棵树）现在需要求含有e 的生成树棵树，τ（含有e 的生成树棵树）=)1(21n 1-n 2-n n n ）（=2n n-3τ（K n -e ）=τ（K n ）-τ（含有e 的生成树棵树）=（n-2）n n-33.2.4证明：不是块的连通图至少有两个块，其中每个恰有一个割点。

证明：设G 为不是块的连通图，由于G 连通且不是块⇒G 有割点①当G 只有1个割点v 时，延割点分开，G1，G2内无割点，且连通，由块的定义知⇒G1,G2是块，且分别含一个割点v 。

②当G 含有2个及2个以上割点时，取相距距离最远的两个割点u 和v ，此时分G 为三部分G1,G2,G3。

第一章：图论基本概念 1.定义平凡图/非平凡图 简单图/复合图 空图 n 阶图 连通图/非连通图完全图n K12n 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 Gv 是无环连通图G 的一个顶点，v 是G 的割点当且仅当V(G-e)可以被划分为两个子集，v 在两个子集内点互连的路上 块：没有割点的连通子图 G 顶点数>=3，G 是块当且仅当G 无环且任意两顶点位于同一圈上v 是割点当且仅当v 至少属于G 的两个不同的块2. 连通度点割 k 顶点割 最小点割（最少用几个点把图割成两份） G 的连通度 G连通图没顶点割时连通度 1G n ，非连通图 0G边割 k 边割 最小边割（最少用几条边把图割成两份） G 的边连通度 G递推到无圈，自环不算圈性质： 任意图G 有 G G GG 是(n,m)连通图， 2m G nG 是(n,m)单图，若 2n G，则G 必定连通 G 是(n,m)单图，对应k n ，若 22n k G，则G 是k 连通G 是(n,m)单图，若 2n G，则 G G敏格尔定理： G 中分离不相邻x,y 的最小点数等于独立的x,y 路最大数目G 中分离x,y 的最小边数等于边不重x,y 路最大数目第四章 E 图与H 图 一、 E 图（走完所有边） 1. 定义，性质与判定E 图（欧拉环游）与E 迹，走完所有边回到出发点与不回到出发点E 图性质与判定：E 图 G 的顶点度数为偶数度 G 的边集合能划分为圈 E 迹性质与判定：E 迹 G 中只有两个顶点度为奇数 2. 求解路径算法 找欧拉环游：都是偶数度点：Fleury 算法（避割边行走）两奇数点欧拉环游：奇数点补充最短路后得到欧拉环游多奇数点欧拉环游：补充偶数度并不断交换 （中国邮路问题算法） 二、 H 图（走完所有点） 1. 定义与性质H 图（H 圈）与H 路：走完所有点回到出发点与不回到出发点 G 图是H 图 w G S S 2. H 图判定3n 的单图G ，如果 2nGG 是H 图3n 的单图G ，任意不相邻u,v 有 d u d v n G 是H 图图G 的闭包是H 图 G 是H 图 度序列判定法：123n d d d d ，3n ，若对任意的2nm，有m d m 或n m d n m ，则G 是H 图123n d d d d ，3n ，若对任意的2nm，有m d m 且n m d n m ，则G 是非H 图 2. 极大非哈密尔顿图定义：如果图G 的度大于等于其他非H 图，则称G 为极大非H 图（非H 图的度上限）,m n C 图： ,2m n m m n m C K K K,m n C 图是非H 图G 是非H 图 G 度弱于某个,m n C 图（证） N 阶单图G 度优于所有,m n C 图 G 为H 图 彼得森图是超H 图4. TSP 问题（边赋权近似最优H 圈求解）最优H 图下界：去点求最小生成树，选最小关联边12e e ， 11w T w e w e第五章 图的匹配与因子分解 1.边匹配定义： 匹配 饱和点/非饱和点 最大匹配/完美匹配 M 交错路/M 可扩路 贝尔热定理：G 的匹配M 是最大匹配，当且仅当G 不包含M 可扩路（反证） 2.偶图匹配Hall 定理（偶图匹配存在性定理，完美匹配）： N S S 推论：k 正则偶图G 存在完美匹配（证） 匹配算法： 匈牙利算法最优匹配算法3.点覆盖边匹配数等于点覆盖数时匹配为最大匹配覆盖为最小覆盖 哥尼定理：偶图中最大匹配边数等于最小覆盖点数（用） 4.托特定理一般图G 有完美匹配当且仅当 G S S推论：没有割边的3正则图存在完美匹配（充分条件）（证） 5.因子分解因子分解，n 度正则因子 一因子分解：2n K 可一因子分解具有H 圈的三正则图可一因子分解 若三正则图有割边，则它不能一因子分解 二因子分解： G 的一个H 圈肯定是一个二因子，但二因子不一定是H 圈（二因子可以不连通）21n K 可2因子分解2n K 可分解为一个1因子和n-1个2因子之和。

习题四：3. (1)画一个有Euler闭迹和Hamilton圈的图；(2) 画一个有Euler闭迹但没有Hamilton圈的图；(3) 画一个有Hamilton圈但没有Euler闭迹的图；(4) 画一个即没有Hamilton圈也没有Euler闭迹的图;解：找到的图如下：(1)一个有Euler闭迹和Hamilton圈的图；(2)—个有Euler闭迹但没有Hamilton圈的图;⑶一个有Hamilton圈但没有Euler闭迹的图;(4)一个即没有Hamilton圈也没有Euler闭迹的图.4. 设n阶无向简单图G有m条边，证明：若2 ) * ',则G是血加此"图。

证明：G是H图。

若不然，因为G是无向简单图，则n芝3,由定理％若G是n芝3的非单图，则G、一 ...C …度弱丁某个阵".于是有：- - 1 2 E(G)| E(C m,n ) - m (n 2m)(n m 1) m(m 1)1.这与条件矛盾！所以G 是H 图若G 有个奇点，则存在k 条边不重的迹Q1・Q 矿心，使得 E(G) = E(Q 】)U E(Q J U E(Q 3) U …U E(Q k ) 证明：不失一般性，只就 G 是连通图进行证明。

设 G=(n, m)是连通图。

令 虬 V 2,…,v,V k+1,…,v 是G 的所有奇度点。

在V i与v i+k 问连新边e i 得图G* (1三隹k). 则G*是欧拉图，因此，由Fleury 算法得欧拉环游C 在C 中删去e i (1m M k).得 k 条边不重的迹Qi (1 MiMk):E(G) E(Q1^E(Q2^^E(Qk)10. 证明：若：(1) G 不是二连通图，或者(2) G 是具有二分类|(X,Y)的偶图，这里|X” |Y|则G 是非Hamilton 图。

证明：(1) G|不是二连通图，则G 不连通或者存在割点v ,俨任-v) >2 ,由丁课本 上的相关定理：若G 是Hamilton 图，则对丁*勇)的任意非空顶点集S,有： w(G- S) <|S|,则该定理的逆否命题也成立，所以可以得出：若不是二连通图， 则G 是非Hamilton 图(2)因为是具有二分类(XI)的偶图，乂因为|X|丰1丫1,在这里假设|X| < |Y|,则有 w(G-X) = |Y|>|X|，也就是说：对北(G)|的非空顶点集S,有：w(G-S)>||S|成 立，则可以得出则G 是非Hamilton 图。

习题43： 1）、画一个有Euler闭迹和Hamilton圈的图。

2）、画一个有Euler闭迹但没有Hamilton圈的图。

3）、画一个有Hamilton圈但没有Euler闭迹的图4）、画一个既没有Hamilton圈也没有Euler闭迹的图7、证明：将G中的孤立点去掉后的图为G1，则G1也是没有奇度点的，且G1的最小度大于等于2.则G1存在一个圈S1，在G1 –S1中去除孤立的点，得到一个新的图G2，显然G2也没有奇度的点，且G2的最小度大于等于2.这样G2中也存在一个圈S2，这样一直下去，指导Gm中有圈Sm，且Gm-Sm都是孤立的点。

这样E(G) = E(G1)并E(G2)…..并E(Gm).命题得证。

10、证明：1）、如果G不是而连通的图，那么G存在割点v或则G是不连通的，G-v的连通分支数大于等于2.由定理：若G是H图，则对于V的每个飞空真子集S，均有G-S的连通分支数小于等于S的顶点数，知，G是非H图。

2）、G 是2部图，且|X|<|Y|,则有G-X的连通分支数等于|Y|>|X|由上边的定理知，G是非H图。

12、证明：假设G中新加入的一点，为V,它和G中的每一个顶点均相连，这样得到新的图G^,这样G^的度序列为(d1+1,d2+1……,dv+1,V)。

因为不存在正整数m<(v+1)/2,使其满足dm<m和dv-m+1<v-m,即不存在m<(v+1)/2,满足dm+1<=m和dv-m+1<v-m+1 = (v+1) –m。

由定理知，G^中含有Hamilton圈C，这样G^-C就是G的H路，命题得证。

习题51、1）、证明：每个k方体都有完美匹配(k>=2)。

假设K方体的顶点坐标为：(x1,x2…,xk)，取(x1,x2,….,xk-1,0)和(x1,x2,…,xk-1,1)两个顶点之间的边的全体集合为M，这样M,中的边均不相邻，所以M是一个匹配，且|M| = 2^(k-1)。