下载文档原格式
电子科技大学研究生试题《图论及其应用》(参考答案)考试时间：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 是非哈密尔顿图。
图论基本知识点梳理第一部分(基本概念)1.G连通的充分必要条件是(G) = 1 o或若|V(G) |=2k，且对—v V(G)，有d(v) _ k，则G是连通图。
4•图G为二分图当且仅当G中无奇圈。
5•在仅两个奇次顶点的图中，此二奇次顶点连通。
6•设G为简单图，若、；(G) _ 2，则G中有圈。
7.设G为简单图，若「.(G) 一3，则G中有偶圈。
具体地，(1)单星妖怪中有偶圈。
⑵在k -正则图G中，若k _3，则G中有偶圈。
8•简单图G与其补图G c不能都不连通。
29•在."■：的三角剖分中，正常三角形为奇数个。
10•以下等价(1) G是树(无圈连通图)° (2) G中任两顶点间恰有一条轨。
⑶G 无圈，=■…1。
(4) G是连通图，；-、•-1 ° (5) G是连通图，且对G的任意边e, G -e不连通。
(树每边皆割边)(6) G无圈，且对任一不在E(G)的边e, G e恰含一个圈。
11. 若G连通，则；(G) (G)-1。
G的生成树是G最小的连通生成子图。
12. G是连通图的充分必要条件是G有生成树。
13. > - 2的树T至少有两个叶。
14. 完全图K n的生成树个数・(K n)二n n°。
15. 图G可平面嵌入的充分必要条件是G可以球面嵌入。
(染地球上各国等价于染地图上各国)16. (Euler公式) G是连通平面图，贝X - ；「- 2.17. 证明：若G是、-3的连通平面图，则；乞3 -6。
18. 证明：平面图G的最小顶点次数5。
19 -3平面图G是极大平面图的充要条件是G的平面嵌入的每个面皆三角形。
' -3平面图G是极大平面图的充要条件是；=3二-6。
20 G是平面图当且仅当G中不含与K5和K3,3同胚的子图。
21 M是图G的最大匹配当且仅当G中无M的可增广轨。
22婚配定理：设G是具有二分类(X,Y)的偶图，存在把X中顶点皆许配的匹配的充要条件是-s X,|N(S)|」S|,其中N(S)是S中每个顶点的邻点组成的所谓S的邻集推论：k -正则二分图有完美匹配，k .0。
第八章图论例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=<V,E,W>, 集合Si V Si’=V-Si , 令|V|=nSi={u|从u0到u的最短路已求出}Si’={u’|从u0到u’的最短路未求出}Dijkstra算法:(求从u0到各点u的最短路长)第一步. 置初值: d(u0,u0)=0 d(u0,v)=∞(其中v≠u0)i=0 S0={u0} S0’=V-S0 ,第二步.若i=n-1 则停. 否则转第三步第三步. 对每个u’∈Si’计算d(u0,u’)=min{d(u0,u’), d(u0,ui)+c(ui,u’)} ui ∈Si计算min{d(u0,u’)}u’∈S i’并用ui+1记下达到该最小值的那个结点u’置Si+1 =Si∪{ui+1} i=i+1 Si’=V-Si , 转第二步.例3、求最短路解：例.求右图中从v1到v6的最短路1.置初值: u0=v1d(u0,u0)=0d(u0,v2)=d(u0,v3)=d(u0,v4)=d(u0,v5)=d(u0,v6)=∞2.3. i=0 S0={v1} S0’={v2,v3,v4,v5,v6}d(u0,v2)=min{d(u0,v2), d(u0,u0)+c(u0,v2)}=min{∞,0+3}=3d(u0,v3)=min{d(u0,v3),d(u0,u0)+c(u0,v3)}=min{∞,0+∞}=∞d(u0,v4)=min{d(u0,v4), d(u0,u0)+c(u0,v4)}=min{∞,0+5}=5d(u0,v5)=min{d(u0,v5),d(u0,u0)+c(u0,v5)}=min{∞,0+∞}=∞d(u0,v6)=min{d(u0,v6),d(u0,u0)+c(u0,v6)}=min{∞,0+∞}=∞min{3,∞,5, ∞,∞}=3ui+1 =u1=v2 , 实际已求出d(u0,v2)=3, 路是u0v2i=1 S1={v1, v2}S1’={v3,v4,v5,v6}u1=v2d(u0,u1)=3d(u0,v3)=min{d(u0,v3),d(u0,u1)+c(u1,v3)}=min{∞,3+6}=9d(u0,v4)=min{d(u0,v4), d(u0,u1)+c(u1,v4)}=min{5,3+1}=4d(u0,v5)=min{d(u0,v5),d(u0,u1)+c(u1,v5)}=min{∞,3+∞}=∞d(u0,v6)=min{d(u0,v6),d(u0,u1)+c(u1,v6)}=min{∞,3+∞}=∞min{9,4,∞,∞}=4ui+1 =u2=v4 , 实际已求出d(u0,v4)=4, 路是u0v2v4i=2 S2={v1, v2 ,v4}S2’={v3,v5,v6}u2=v4d(u0,u2)=4d(u0,v3)=min{d(u0,v3), d(u0,u2)+c(u2,v3)}=min{9 ,4+3}=7d(u0,v5)=min{d(u0,v5), d(u0,u2)+c(u2,v5)}=min{∞,4+1}=5d(u0,v6)=min{d(u0,v6), d(u0,u2)+c(u2,v6)}=min{∞,4+∞}=∞min{7,5,∞}=5ui+1 =u3=v5 , 实际已求出d(u0,v5)=5, 路是u0v2v4 v5i=3 S3={v1, v2 ,v4 ,v5}S3’={v3,v6}u3=v5d(u0,u3)=5d(u0,v3)=min{d(u0,v3),d(u0,u3)+c(u3,v3)}=min{7 ,5+3}=7d(u0,v6)=min{d(u0,v6),d(u0,u3)+c(u3,v6)}=min{∞,5+6}=11 min{7,11}=7ui+1 =u4=v3 , 实际已求出d(u0,v3)=7, 路是u0v2v4 v3i=4 S3={v1, v2 ,v4 ,v5, v3} S3’={v6} u4=v3 d(u0,u4)=7 d(u0,v6)=min{d(u0,v6),d(u0,u4)+c(u4,v6)}=min{11,7+3}=10min{10}=10ui+1 =u5=v6 , 实际已求出d(u0,v6)=10, 路是u0v2v4 v3 v6i=5 (n-1) 时算法停止.例4、求关键路径。
图论及其应用总复习第1章图的基本概念•§1.1 图论发展史•§1.2 图的定义•§1.3 顶点的度•§1.4 子图与图的运算•§1.5一些特殊的图•§1.6 图的矩阵表示•§1.7 有向图1、图的定义图--图G=<V(G)，E(G)，ψ)>是有序三元组，其中V(G)是一个非空有限集合，E(G)与是V(G)不相交的有限集合，ψ)使E(G)中每一个元素对应于V(G)中的一个无序元素对.顶点--V(G)中的元素称为G的顶点，p(G)=|V(G)|称为G的点数.边--E(G)中的元素称为G的边，q(G)=|E(G)|称为G的边数.环--两个端点重合为一个顶点的边。
重边（平行边)--关联于同一对顶点的若干条边。
关联--如果ψ)e =uv ，则称边e 连接顶点u 和v ，u 和v 是e 的端点，u (或v )与e 关联。
相邻--点的相邻：两点间有边边的相邻：两条边有公共端点简单图--不含环和重边的图.有限图--一个图的顶点集和边集都是有限集的图.平凡图--只有一个顶点所构成的图称为平凡图.2、图的同构3、顶点的度最大度Δ(G)=max{d(v)|v∈V}最小度δ(G)=min{d(v)|v∈V}孤立顶点--度为0的顶点。
k-正则图--如果一个图中每个顶点的度是某一个固定整数k，则称该图是k-正则图。
握手定理顶点的度序列4、子图完全图--若图G 中的每一对不同顶点之间恰有一条边连接，则称图G 为完全图，记作K ;.4K 5K 3K 2K 1K 5、特殊图二分图−−G=(V>,V@;E)通常写出G=(X,Y;E),即它的点集可以分解为两个(非空)子集X和Y，使得每条边的一个端点在X中，另一个端点在Y中。
完全二分图--是指具有二分类（X,Y）的简单二部图，其中X 的每个顶点与Y的每个顶点相连，若|X|=p，|Y|=q，则这样的偶图记为K p,q.关联矩阵设图G=(V,E),V=v>,v@,⋯,v;,E=e>,e@,⋯,e G，则称B(G)=(b JK);×G为G的关联矩阵，其中b JK=0v J与e K不关联1v J与e K关联1次2v J与e K关联2次(即e K是以v J为端点的环)6、矩阵表示邻接矩阵设图G=(V,E),V=v>,v@,⋯,v;,用a JK表示G中顶点v J与v K之间的边数，则称M(G)=(a JK);×;为G的邻接矩阵。
图论总结（超强⼤）1.图论Graph Theory1.1.定义与术语Definition and Glossary1.1.1.图与⽹络Graph and Network1.1.2.图的术语Glossary of Graph1.1.3.路径与回路Path and Cycle1.1.4.连通性Connectivity1.1.5.图论中特殊的集合Sets in graph1.1.6.匹配Matching1.1.7.树Tree1.1.8.组合优化Combinatorial optimization1.2.图的表⽰Expressions of graph1.2.1.邻接矩阵Adjacency matrix1.2.2.关联矩阵Incidence matrix1.2.3.邻接表Adjacency list1.2.4.弧表Arc list1.2.5.星形表⽰Star1.3.图的遍历Traveling in graph1.3.1.深度优先搜索Depth first search (DFS)1.3.1.1.概念1.3.1.2.求⽆向连通图中的桥Finding bridges in undirected graph1.3.2.⼴度优先搜索Breadth first search (BFS)1.4.拓扑排序Topological sort1.5.路径与回路Paths and circuits1.5.1.欧拉路径或回路Eulerian path1.5.1.1.⽆向图1.5.1.2.有向图1.5.1.3.混合图1.5.1.4.⽆权图Unweighted2.Hamiltonian Cycle 哈⽒路径与回路1.5.2.1.⽆权图Unweighted1.5.2.2.有权图Weighed —旅⾏商问题The travelling salesman problem1.6.⽹络优化Network optimization1.6.1.最⼩⽣成树Minimum spanning trees1.6.1.1.基本算法Basic algorithms1.6.1.1.1.Prim1.6.1.1.2.Kruskal1.6.1.1.3.Sollin（Boruvka）1.6.1.2.扩展模型Extended models1.6.1.2.1.度限制⽣成树Minimum degree-bounded spanning trees1.6.1.2.2.k⼩⽣成树The k minimum spanning tree problem(k-MST)1.6.2.最短路Shortest paths1.6.2.1.单源最短路Single-source shortest paths1.6.2.1.1.基本算法Basic algorithms1.6.2.1.1.1. ..................................................................................................... D ijkstra1.6.2.1.1.2. .......................................................................................... B ellman-Ford1.6.2.1.1.2.1.....................................Shortest path faster algorithm(SPFA)1.6.2.1.2.应⽤Applications1.6.2.1.2.1. ........................... 差分约束系统System of difference constraints2.1.2.2. .......................... 有向⽆环图上的最短路Shortest paths in DAG1.6.2.2.所有顶点对间最短路All-pairs shortest paths1.6.2.2.1.基本算法Basic algorithms1.6.2.2.1.1. ....................................................................................... F loyd-Warshall1.6.2.2.1.2. .................................................................................................... Johnson 1.6.3.⽹络流Flow network1.6.3.1.最⼤流Maximum flow1.6.3.1.1.基本算法Basic algorithms1.6.3.1.1.1. ........................................................................ Ford-Fulkerson method 1.6.3.1.1.1.1.......................................................... E dmonds-Karp algorithm1.6.3.1.1.1.1.1. ................................................... M inimum length path1.6.3.1.1.1.1.2. ........................................... Maximum capability path1.6.3.1.1.2. ............................................... 预流推进算法Preflow push method1.6.3.1.1.2.1.................................................................................. P ush-relabel1.6.3.1.1.2.2........................................................................... Relabel-to-front1.6.3.1.1.3. .......................................................................................... Dinic method1.6.3.1.2.扩展模型Extended models1.6.3.1.2.1. ............................................................................... 有上下界的流问题1.6.3.2.最⼩费⽤流Minimum cost flow1.6.3.2.1.找最⼩费⽤路Finding minimum cost path1.6.3.2.2.找负权圈Finding negative circle2.3.⽹络单纯形Network simplex algorithm1.6.4.匹配Matching1.6.4.1.⼆分图Bipartite Graph1.6.4.1.1.⽆权图-匈⽛利算法Unweighted - Hopcroft and Karp algorithm1.6.4.1.2.带权图-KM算法Weighted –Kuhn-Munkres(KM) algorithm1.6.4.2.⼀般图General Graph1.6.4.2.1.⽆权图-带花树算法Unweighted - Blossom (Edmonds)1.图论Graph Theory1.1. 定义与术语Definition and Glossary1.1.1.图与⽹络Graph and Network⼆元组(),V E称为图(graph)。
)2214(题后两个算法不作要求题，除第图的基本概念<1.>若G 是简单图，证明：()()2V G E G ⎛⎫≤ ⎪⎝⎭。
证明：()()1()()()1v Gd v V G d v V G V G ∈≤-∴≤-∑（当且仅当G 是完全图时取等号） 又11()()()()122v G E G d v V G V G ∈=≤-∑ ()()2V G E G ⎛⎫∴≤ ⎪⎝⎭。
<2.>设G 是(,)p q 简单图，且12p q -⎛⎫>⎪⎝⎭。
求证G 为连通图。
证明：反证法，假设G 为非连通图。
设G 有两个连通分支1G 和2G ，且112212()1,()1,V G p V G p p p p =≥=≥+= 则1212()()22p p E G E G q ⎛⎫⎛⎫+=≤+⎪ ⎪⎝⎭⎝⎭而1211221(1)(1)(1)(2)222222p p p p p p p p p -⎛⎫⎛⎫⎛⎫----+-=+-⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭2222221212121222()2()222p p p p p p p p p p +-+-+-+++-==12(1)(1)0p p =--≤（因为121,1p p ≥≥），矛盾。
<3.>超图H 是有序二元组((),())V H E H ，其中()V H 是顶点非空有限集合，()E H 是()V H 的非空子集簇，且()()i i E E H E V H ∈=。
其中，()E H 中的元素i E 称为超图的边，没有相同边的超图称为简单超图。
证明：若H 是简单超图，则21υε≤-，其中,υε分别是H 的顶点数和边数。
证明：()V H υ=，有一条边的子集个数为1υ⎛⎫ ⎪⎝⎭，有i 条边的子集个数为,1,,.i n i υ⎛⎫= ⎪⎝⎭又02,211i i υυυυυυυ=⎛⎫⎛⎫⎛⎫=∴++=- ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭∑ 。
<4.>若G 是二部图，则2()()4V G E G ≤。
图论及应用习题答案图论及应用习题答案图论是数学中的一个分支，研究的是图的性质和图之间的关系。
图论在现实生活中有着广泛的应用，涵盖了许多领域，如计算机科学、通信网络、社交网络等。
本文将为读者提供一些关于图论及应用的习题答案，帮助读者更好地理解和应用图论知识。
1. 图的基本概念题目：下面哪个不是图的基本概念？A. 顶点B. 边C. 路径D. 线段答案：D. 线段。
图的基本概念包括顶点、边和路径。
线段是指两个点之间的连线，而在图论中，我们使用边来表示两个顶点之间的关系。
2. 图的表示方法题目：以下哪个不是图的表示方法？A. 邻接矩阵B. 邻接表C. 边列表D. 二叉树答案：D. 二叉树。
图的表示方法包括邻接矩阵、邻接表和边列表。
二叉树是一种特殊的树结构，与图的表示方法无关。
3. 图的遍历算法题目：以下哪个不是图的遍历算法？A. 深度优先搜索B. 广度优先搜索C. 迪杰斯特拉算法D. 克鲁斯卡尔算法答案：D. 克鲁斯卡尔算法。
图的遍历算法包括深度优先搜索和广度优先搜索，用于遍历图中的所有顶点。
迪杰斯特拉算法是用于求解最短路径的算法，与图的遍历算法有所不同。
4. 最小生成树题目：以下哪个算法不是用于求解最小生成树？A. 克鲁斯卡尔算法B. 普里姆算法C. 弗洛伊德算法D. 公交车换乘算法答案：D. 公交车换乘算法。
最小生成树是指包含图中所有顶点的一棵树，使得树的边的权重之和最小。
克鲁斯卡尔算法和普里姆算法是常用的求解最小生成树的算法，而弗洛伊德算法是用于求解最短路径的算法，与最小生成树问题有所不同。
5. 图的应用题目：以下哪个不是图的应用？A. 社交网络分析B. 路径规划C. 图像处理D. 数字逻辑电路设计答案：D. 数字逻辑电路设计。
图的应用广泛存在于社交网络分析、路径规划和图像处理等领域。
数字逻辑电路设计虽然也涉及到图的概念，但与图的应用有所不同。
总结：图论是一门重要的数学分支，具有广泛的应用价值。
通过本文提供的习题答案，读者可以更好地理解和应用图论知识。
