电子科技大学-图论第二次作业-杨春

图论作业3一、填空题1. 完全图K2n共有个不同的完美匹配。

2. 超方体Q6的最小覆盖包含的点数为。

3. 图K m,n (m≤n)的最小覆盖包含的点数为。

4. 完全图K60能分解为个边不重的一因子之并。

5. 完全图K61能分解为个边不重的二因子之并。

6. 假设G是具有n个点、m条边、k个连通分支的无圈图，则G的荫度为。

7. 图G是由3个连通分支K1, K2, K4组成的平面图，则其共有个面。

8. 设图G与K5同胚，则至少从G中删掉条边才可能使其成为可平面图。

9. 设连通平面图G具有5个顶点，9条边，则其面数为。

10. 若图G是10阶极大平面图，则其面数等于。

11. 若图G是10阶极大外平面图，其内部面共有个。

二、不定项选择题1. 关于非平凡树T，下面说法错误的是( )(A) T至少包含一个完美匹配；(B) T至多包含一个完美匹配；(C) T的荫度大于1；(D) T是只有一个面的平面图；(E) T的对偶图是简单图。

2. 下列说法正确的是( )(A) 三正则的偶图存在完美匹配；(B) 无割边的三正则图一定存在完美匹配；(C) 有割边的三正则图一定没有完美匹配；(D) 有完美匹配的三正则图一定没有割边；(E) 三正则哈密尔顿图存在完美匹配。

3. 下列说法正确的是( )(A) 在偶图中，最大匹配包含的边数等于最小覆盖包含的点数；(B) 任一非平凡正则偶图包含完美匹配；(C) 任一非平凡正则偶图可以1-因子分解；(D) 偶度正则偶图可以2-因子分解；(E) 非平凡偶图的最大匹配是唯一的。

4. 下列说法中错误的是( )(A) 完全图K101包含1-因子；(B) 完全图K101包含2-因子；(C) 完全图K102包含1-因子；(D) 完全图K102包含2-因子；(E) 图G的一个完美匹配实际上就是它的一个1因子；(F) 图G的一个2-因子实际上就是它的一个哈密尔顿圈。

5. 下列说法正确的是( )(A) 方体Q n可以1-因子分解；(B) 非平凡树可以1-因子分解；(C) 无割边的3正则图可以1-因子分解；(D) 有割边的3正则图一定不可以1-因子分解；(E) 可1-因子分解的3正则图一定是哈密尔顿图。

习题四：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 图。

图论作业第一章4.证明:将图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 为非完全图，则∃ v ∈V(G),有d(v)< n-1 ⇒ ∑ d(v) < n(n-1) ⇒ 2m <n(n-1)⇒ m < n(n-1)/2=⎪⎪⎭⎫⎝⎛2n , 与已知矛盾！充分性 若G 为完全图，则 2m=∑ d(v) =n(n-1) ⇒ m= ⎪⎪⎭⎫⎝⎛2n 。

9. 证明:由于G 为k 正则偶图，所以，k | V 1 | =m = k | V 2 | ⇒ ∣V 1∣= ∣V 2 ∣。

12. 证明:δ≧2,在图G 中任取一点u ，则d(u)≧2.存在u1≠u 与u 相邻接。

由于d(u) ≧2，则存在u2≠u 与u1邻接，由于图是有限图，如此下去定会返回u ，由圈的定义可知图G 包含圈。

(a)v 2 3u 4u (b)17.证明：设u、v是G的任意两个顶点。

若u和v在G中不邻接，则在中他们邻接。

若u和v在G中邻接，他们属于G的同一分支。

在另一个分支中有一点w，在中u和v均与w邻接，即uwv是一条通路，故是连通图。

第二章2.证明：由题意可知如果一棵树恰有两个1度的顶点，则其他顶点的度必为2（如果树其他顶点至少有一个大于2，则该树度为1的顶点树必然大于2），连通的无圈图称为树，一棵树恰有两个1度的顶点而且其他顶点的度数为2，显然这样的树均是路。

16.对于（1）和（2）都可以用Kruskal算法。

具体用法是：对（1）有两种方法：<1>把Kruskal算法中的“小”字换为“大”字。

<2>重新规定图的权为：W’(e)=1/w(e) 当w(e)≠0M（充分大）当w(e)＝0这样就可直接用Kruskal算法。

图论及其应用第二次作业要求：1、交电子档给助教【助教给每个班设置邮箱，助教设置提交回复】；2、第7章授课结束前均可以提交；3、希望能够独立完成。

1．判断图4-43所示的四个图是否可以一笔画。

上面四个图都是连通图，看是否能一笔画成问题本质上看图是否存在欧拉迹；连通图有欧垃迹当且仅当G 最多有两个奇点。

（a ）不可以 有4个奇点（b ）可以 一个奇点（c ）可以 两个奇点（d ）可以 没有奇点2.（1）画一个有欧拉闭迹和哈密尔顿圈的图；（2）画一个有欧拉闭迹但没有哈密尔顿圈的图；(3) 画一个有哈密尔顿圈但没有欧拉闭迹的图；（4）画一个既没有欧拉闭迹也没有哈密尔顿圈的图。

3. 设n 阶无向简单图G 有m 条边。

证明：若m ≥⎪⎪⎭⎫ ⎝⎛-21n +2，则G 是哈密尔顿图。

(b) (c) (d ) 图4-43证明：G 是H 图。

若不然，因为G 是无向简单图，则n ≥3，由定理1：若G 是n ≥3的非单图，则G 度弱于C m,n 。

于是有：2,1()()(2)(1)(1)21111(1)(2)(1)(21) 1.222m n E G E C m n m n m m n n n m m m n m ⎡⎤≤=+---+-⎣⎦--⎛⎫⎛⎫=+-------≤+ ⎪ ⎪⎝⎭⎝⎭ 这与条件矛盾！所以G 是H 图。

4. 在图4-45中，哪些图是哈密尔顿图？哪些图中有哈密尔顿路？(a)非哈密尔顿图，没有哈密尔顿路(b)哈密尔顿图 （abcdejhfiga)(c)哈密尔顿图 （kjdhbagciefk)(d)非哈密尔顿图 有哈密尔顿路（hjaidebcgf)(e)不是哈密尔顿图，因为有割点a ，有哈密尔顿路（jaibcedkgfh ）5. 证明：若G 没有奇点，则存在边不重的圈C 1, C 2,…, C m ，使得，E (G ) = E (C 1)∪E (C 2)∪…∪E (C m )。

证明：将G 中孤立点除去后的图记为G 1，则G 1也没有奇点，且δ（G 1)，则G 1含圈C 1，在去掉()11G E C -的孤立点后，得图G 2，显然G 2仍无奇度点，且δ（G 2）≥ 2，从而G 2含圈C 1，如此重复下去，直到圈C m ，且G m －E (C m )全为孤立点为止，于是得到E (G ) = E (C 1)∪E (C 2)∪…∪E (C m )。

图论第二次作业一、第四章4.3（1）画一个有Euler 闭迹和Hamilton 圈的图； （2）画一个有Euler 闭迹但没有Hamilton 圈的图； （3）画一个有Hamilton 圈但没有Euler 闭迹的图； （4）画一个既没有Euler 闭迹也没有Hamilton 圈的图； 解：（1）一个有Euler 闭迹和Hamilton 圈的图形如下：（2）一个有Euler 闭迹但没有Hamilton 圈的图形如下：（3）一个有Hamilton 圈但没有Euler 闭迹的图形如下：（4）一个既没有Euler 闭迹也没有Hamilton 圈的图形如下：4.7证明：若G 没有奇点，则存在边不重的圈C 1,C 1,....,C m ,使得E(G)=E(C 1) E(C 2) ..... E(C m )。

证明：将G 中孤立点除去后的图记为G 1,则G 1也没有奇点，且δ(G 1)≥2，则G 1含圈C 1，在去掉G 1-E(C 1)的孤立点后，得图G 2，显然G 2仍无奇度点，且(G 2)≥2，从而G 2含圈C 2，如此重复下去，直到圈C m ，且G m -E(C m )全为孤立点为止，于是得到E(G) E(C 1) E(C 2) ... E(C m )。

4.10证明：若（1）G 不是二连通图，或者（2）G 是具有二分类(X,Y)的偶图，这里|X|≠|Y|， 则G 是非Hamilton 图。

证明：（1）因为G 不是二连通图，则G 不连通或者存在割点V ，有w(GV)2，由相关定理得：若G 是Hamilton 图，则对于V(G)的任意非空顶点集S ，有：w(GS)S ，则该定理得逆否命题也成立，所以可得：若G 不是二连通图，则G 是非Hamilton 图。

（2）因为G 是具有二分类(X,Y)的偶图，又因为|X|≠|Y|，在这里假设|X|≠|Y|，则有w(G-X)=Y>X ，也就是说：对于V(G)的非空顶点集S ，有：w(G-S)>S 成立，则可以得出G 是非Hamilton 图。

电子行业图论25电子科大杨春引言电子行业是指以电子技术为核心的一类产业，包括电子元器件制造、电子设备制造、电子信息服务等。

其中，电子科大（University of Electronic Science and Technology of China，简称电子科大）是中国著名的电子工科高校之一。

本文将介绍电子行业图论，并聚焦于电子科大杨春教授的研究成果。

电子行业图论简介图论是数学中的一个分支，研究的是图的性质和图的应用。

在电子行业中，图论被广泛应用在网络通信、电路设计等方面。

图是由顶点（节点）和边（连接线）构成的数据结构。

顶点表示对象，边表示对象之间的关系。

在电子行业中，顶点可以表示电子元器件、电子设备、节点等，边可以表示电子元器件之间的连接关系、电子设备之间的通信路径，以及节点之间的数据传输等。

图论通过研究图的性质和算法，为电子行业提供了很多解决方案。

例如，在网络通信中，图论可以用于路由算法的设计，以在复杂网络中寻找最短路径或者负载均衡；在电路设计中，图论可以用于布线算法的优化，以提高电子装置的性能和可靠性。

电子科大杨春教授的研究成果杨春教授是电子科大的杰出学者，他在电子行业图论方面的研究取得了很多重要成果。

以下将介绍杨春教授的两个主要研究成果。

成果一：基于图论的网络通信优化算法杨春教授在网络通信方面的研究中，提出了一种基于图论的优化算法，用于解决复杂网络中的路由问题。

该算法通过构建网络拓扑图，并基于图的特性，设计出高效的路由方案，可以同时考虑网络的负载均衡和数据传输的可靠性。

杨教授的算法在实际网络中进行了验证，取得了较好的效果，优化了网络通信的性能。

成果二：图论在电路设计中的应用杨春教授的另一个研究方向是图论在电路设计中的应用。

他提出了一种基于图论的布线算法，用于解决大规模电路的布线问题。

该算法通过将电路抽象为图，利用图的性质和算法进行布线优化，可以降低电路的时延、功耗等指标。

杨教授的算法在实际电路中得到了验证，对提高电子设备的工作效率和可靠性有重要意义。

习题四：3.（1）画一个有Euler 闭迹和Hamilton圈的图；（2）画一个有Euler闭迹但没有Hamilton圈的图；（3）画一个有Hamilton圈但没有Euler闭迹的图；（4）画一个即没有Hamilton圈也没有Euler闭迹的图；解：找到的图如下：(1)一个有Euler 闭迹和Hamilton圈的图；(2)一个有Euler闭迹但没有Hamilton圈的图；(3) 一个有Hamilton圈但没有Euler闭迹的图;(4)一个即没有Hamilton圈也没有Euler闭迹的图.)+2,则G是Hamilton图。

4.设n阶无向简单图G有m条边，证明:若m≥(n−12证明: G是H图。

若不然，因为G是无向简单图，则n≥3,由定理1：若G是n≥3的非单图，则G 度弱于某个C m,n.于是有：2,1()()(2)(1)(1)2111(1)(2)(1)(21)221 1.2m n E G E C m n m n m m m n m m m n m n ⎡⎤≤=+---+-⎣⎦-⎛⎫=+------- ⎪⎝⎭-⎛⎫≤+ ⎪⎝⎭这与条件矛盾！所以G 是H 图。

8.证明：若G 有2k ≥0个奇点，则存在k 条边不重的迹Q 1,Q 2…Q k ,使得E (G )=E (Q 1)∪E (Q 2)∪E (Q 3)∪⋯∪E(Q k ).证明：不失一般性，只就G 是连通图进行证明。

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

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

在v i 与v i+k 间连新边e i 得图G*（1≦i ≦k).则G*是欧拉图，因此，由Fleury 算法得欧拉环游C.在C 中删去e i （1≦i ≦k).得k 条边不重的迹Q i （1≦i ≦k):12()()()()k E G E Q E Q E Q =U UL U10.证明：若：（1）G 不是二连通图，或者（2）G 是具有二分类(X,Y )的偶图，这里|X |≠|Y |,则G 是非Hamilton 图。

刻画图的连通性的一种新参数张保如;杨春【期刊名称】《内江师范学院学报》【年(卷),期】2011(026)012【摘要】The concept of Nth side edge-toughness is proposed on the basis of edge-toughness, and a new parameter to depict the connectivity of graphs, the coupling degree, is defined, with some of its properties presented. Through the comparison of the parameters like the connectivity, toughness and creativity hy examples, the accuracy of the coupling degree is proved in depicting connectivity of some graphs.%在边坚韧度的基础上提出n次边坚韧度的概念，并定义了描述图的连通性的新参数——联结度，指出了联结度的部分性质，通过举例与已有的连通度、坚韧度、核度等参数的对比，说明了联结度在描述某些图的连通性时的进一步的准确性．【总页数】4页(P23-25,32)【作者】张保如;杨春【作者单位】电子科技大学数学科学学院,四川成都611731;电子科技大学数学科学学院,四川成都611731【正文语种】中文【中图分类】O157.6【相关文献】1.计算通信网络整体概率连通性的一种新算法 [J], 陈育斌;李建东;陈家模;郭梯云2.一种新的音频系统参数管理方式及参数渐变算法 [J], 汪静姝; 吕盼稂; 孙立婷; 竺长安3.一种新的音频系统参数管理方式及参数渐变算法 [J], 汪静姝; 吕盼稂; 孙立婷; 竺长安4.三次Bézier曲线另一种带三参数的新扩展及其应用 [J], 王成伟;张卷美5.介绍一种新的刻图修正液 [J], 钟盘度因版权原因，仅展示原文概要，查看原文内容请购买。