10年图论试题

图论习题课⼀、填空题1、对下列图，试填下表（是??类图的打〝√ 〞，否则打〝?〞）。

①②③2、若图G=中具有⼀条汉密尔顿回路，则对于结点集V 的每个⾮空⼦集S ，在 G 中删除S 中的所有结点得到的连通分⽀数为W ，则S 中结点数|S|与W 满⾜的关系式为。

3、设有向图D 为欧拉图，则图D 中每个结点的⼊度．4、数组{1，2，3，4，4}是⼀个能构成⽆向简单图的度数序列，此命题的真值是 .5、“3,3K 是欧拉图也是哈密顿图”这句话是_______。

(填对或错)6、极⼤可平⾯图的每⼀个⾯的次数都是_________．7、5阶完全图的边连通度是．8、图G是2-⾊的当且仅当G是．⼆、选择题1、下列⽆向图可能不是偶图的是( )(A) ⾮平凡的树(B)⽆奇圈的⾮平凡图(C) n(1)n ⽅体图(D) 平⾯图2、关于平⾯图，下列说法错误的是( )(A) 简单连通平⾯图中⾄少有⼀个度数不超过5的顶点；(B)极⼤外平⾯图的内部⾯是三⾓形，外部⾯也是三⾓形；(C) 存在⼀种⽅法，总可以把平⾯图的任意⼀个内部⾯转化为外部⾯；(D) 平⾯图的对偶图也是平⾯图。

3、已知图G的邻接矩阵为，则G有（）．A．5点，8边B．6点，7边C．6点，8边D．5点，7边4、设图G＝，则下列结论成⽴的是( )．A．deg(V)=2∣E∣B．deg(V)=∣E∣C．EvVv2)deg(=∑∈D．Vv=∑∈)deg(5、设完全图K n有n个结点(n≥2)，m条边，当（）时，K n中存在欧拉回路．A．m为奇数B．n为偶数C．n为奇数D．m为偶数6、设G是连通平⾯图，有v个结点，e条边，r个⾯，则r= ( )．A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋27、下列定义正确的是( )．A含平⾏边或环的图称为多重B不含平⾏边或环的图称为简单图C含平⾏边和环的图称为多重D不含平⾏边和环的图称为简单图8、以下结论正确是( )．A仅有⼀个孤⽴结点构成的图是零图B⽆向完全图Kn每个结点的度数是nC有n(n>1)个孤⽴结点构成的图是平凡图D图中的基本回路都是简单回路9、下列数组能构成简单图的是( )．(A) (0,1,2,3) (B) (2,3,3,3) (C) (3,3,3,3) (D) (4,2,3,3)10、n阶⽆向完全图Kn中的边数为（）．(A) 2)1(+nn(B) 2)1(-nn(C) n (D)n(n+1)11、以下命题正确的是( )．(A) n(n≥1)阶完全图Kn都是欧拉图(B) n(n≥1)阶完全图Kn都是哈密顿图(C) 连通且满⾜m=n－1的图(∣V∣=n,∣E∣=m)是树(D) n(n≥5)阶完全图Kn都是平⾯图12、下列结论不正确是( )．(A) ⽆向连通图G是欧拉图的充分必要条件是G不含奇数度结点(B) ⽆向连通图G有欧拉路的充分必要条件是G最多有两个奇数度结点(C) 有向连通图D是欧拉图的充分必要条件是D的每个结点的⼊度等于出度(D) 有向连通图D有有向欧拉路的充分必要条件是除两个结点外，每个结点的⼊度等于出度13、⽆向完全图K4是（）．（A）欧拉图（B）哈密顿图（C）树（D）平⾯图14、在如下各图中（）欧拉图。

《图论》练习题(2014)1、利用Dijkstra 算法求下图中顶点0v 到其它各顶点的距离，并写出到顶点8v 的最短路。

2、1、列出色数3为的三个图： 。

2、p 阶完全图的色数为： 。

3、p 阶树的邻接多项式为： 。

4、p 阶完全图的邻接多项式为： 。

5、如下图所示的图的邻接矩阵为 ，关联矩阵为 。

6、度序列为(2,2,2,2,2,2)的简单图是 。

7、是否存在度序列为(2,2,3,4,5,6)，(1,2,3,4,4,5)的简单图？若存在，给出一个图；若不存在，请说明理由。

8、画出如下图的所有生成子图。

9、设图G 如下图所示，求该图的生成树个数)(G 。

v 2v 6v 4v 610、已知图G （V 、E ），画出G －V 5，G －v 3v 4，G[{v 2，v 3，v 5}]，G[{v 3v 4，v 4，v 6，v 7v 8}]G ：11、已知图G 的邻接矩阵⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=2111102112011111A ，画出G ，并求出度序列。

12、证明：偶图G 的任意子图H 仍为偶图。

13、证明：设图G （V 、E ）的度序列为（p d d d ,,,21 ），边数为q ，则q i d pi 21==∑14、证明：在任何图中，奇顶点个数为偶数。

15、证明：整数序列（6，6，5，4，3，3，1）不可能为一个简单图的图序列。

16、证明顶点度数均为2的简单连通图是圈。

17、证明非平凡树T 的边连通度为'()1T κ=。

18、n 阶完全图n K 的连通度为()1T n κ=-。

19、设G 是一个p 阶图，且()()21,-≥∈∀p v d G V v ，则G 连通图。

20、若图G 是 不连通的，则其补图G C 是连通的。

21、证明：设G 是由1G 和2G 两个连通分支组成的图，则);();();(21x G P x G P x G P =。

v 1v 2v 3v 4v 5v 6v 8v 722、证明：设G 是由1G 和2G 两个连通分支组成的图，则)}(),(max{)(21G G G χχχ=。

图论与组合数学期末复习试题含答案组合数学部分第1章排列与组合例1：1)、求⼩于10000的含1的正整数的个数；2、)求⼩于10000的含0的正整数的个数；解：1)、⼩于10000的不含1的正整数可看做4位数,但0000除外.故有9×9×9×9－1＝6560个.含1的有：9999－6560=3439个2)、“含0”和“含1”不可直接套⽤。

0019含1但不含0。

在组合的习题中有许多类似的隐含的规定，要特别留神。

不含0的1位数有19个，2位数有29个，3位数有39个，4位数有49个不含0⼩于10000的正整数有()()73801919999954321=--=+++个含0⼩于10000的正整数9999－7380=2619个。

例2：从[1,300]中取3个不同的数，使这3个数的和能被3整除，有多少种⽅案？解：将[1,300]分成3类：A={i|i ≡1(mod 3)}={1,4,7,…,298},B={i|i ≡2(mod 3)}={2,5,8,…,299},C={i|i ≡0(mod 3)}={3,6,9,…,300}.要满⾜条件，有四种解法：1)、3个数同属于A;2)、3个数同属于B ；3)、3个数同属于C;4)、A,B,C 各取⼀数；故共有3C(100,3)+1003=485100+1000000=1485100。

例3：（Cayley 定理：过n 个有标志顶点的数的数⽬等于2-n n ）1）、写出右图所对应的序列；2）、写出序列22314所对应的序列；解：1）、按照叶⼦节点从⼩到⼤的顺序依次去掉节点（包含与此叶⼦节点相连接的线），⽽与这个去掉的叶⼦节点相邻的另外⼀个内点值则记⼊序列。

如上图所⽰，先去掉最⼩的叶⼦节点②，与其相邻的内点为⑤，然后去掉叶⼦节点③，与其相邻的内点为①，直到只剩下两个节点相邻为⽌，则最终序列为51155.。

2）、⾸先依据给定序列写出（序列长度+2）个递增序列，即1234567，再将给出序列按从⼩到⼤顺序依次排列并插⼊递增序列得到：112223344567。

图论复习题（二）图论复习题一、选择题1．设图G ＝<V , E >，v ∈V ，则下列结论成立的是 ( C ) ． A ．deg(v )=2∣E ∣ B ． deg(v )=∣E ∣ C ．E v Vv 2)deg(=∑∈ [PPT 23] D ．Ev Vv =∑∈)deg(定理1 图G=（V ，E ）中，所有点的次之和为边数的两倍 2．设无向图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100100110则G 的边数为( B )．A ．6B ．5C ．4D ．33、 设完全图K n 有n 个结点(n ≥2)，m 条边，当（ C ）时，K n 中存在欧拉回路．A ．m 为奇数B ．n 为偶数C ．n 为奇数D ．m 为偶数解释：K n 每个结点的度都为n －1，所以若存在欧拉回路则n －1必为偶数。

n 必为奇数。

4．欧拉回路是（ B ）A. 路径B. 简单回路[PPT 40]C. 既是基本回路也是简单回路D.既非基本回路也非简单回路5．哈密尔顿回路是（ C ）A. 路径B. 简单回路C. 既是基本回路也是简单回路D.既非基本回路也非简单回路[PPT 40]：哈密尔顿回路要求走遍所有的点，即是基本回路的点不重复，也可以是简单回路的边不重复。

6．设G 是简单有向图，可达矩阵P(G)刻划下列关系中的是（ C ） A 、点与边 B 、边与点 C 、点与点 D 、边与边7．下列哪一种图不一定是树（C ）。

A.无简单回路的连通图B. 有n 个顶点n-1条边的连通图C. 每对顶点间都有通路的图D. 连通但删去一条边便不连通的图8．在有n 个结点的连通图中，其边数（B ）A.最多有n-1条B.至少有n-1条C.最多有n 条D.至少有n 条9．下列图为树的是（C ）。

A 、>><><><=<},,,,,{},,,,{1d c b a a a d c b a GB 、>><><><=<},,,,,{},,,,{2d c d b b a d c b a GC 、>><><><=<},,,,,{},,,,{3a c d a b a d c b a GD 、>><><><=<},,,,,{},,,,{4d d c a b a d c b a G 10、下面的图7-22是（C ）。

离散数学图论部分经典试题及答案离散数学图论部分综合练习⼀、单项选择题1．设图G 的邻接矩阵为0101010010000011100100110则G 的边数为( )．A ．6B ．5C ．4D ．32．已知图G 的邻接矩阵为，则G 有（）．A ．5点，8边B ．6点，7边C ．6点，8边D ．5点，7边3．设图G ＝，则下列结论成⽴的是 ( )．A ．deg(V )=2∣E ∣B ．deg(V )=∣E ∣C ．E v Vv 2)deg(=∑∈ D ．E v Vv =∑∈)deg(4．图G 如图⼀所⽰，以下说法正确的是 ( ) ． A ．{(a , d )}是割边 B ．{(a , d )}是边割集 C ．{(d , e )}是边割集 D ．{(a, d ) ,(a, c )}是边割集5．如图⼆所⽰，以下说法正确的是 ( )． A ．e 是割点 B ．{a, e }是点割集 C ．{b , e }是点割集 D ．{d }是点割集6．如图三所⽰，以下说法正确的是 ( ) ．A ．{(a, e )}是割边B ．{(a, e )}是边割集C ．{(a, e ) ,(b, c )}是边割集D ．{(d , e )}是边割集οοοοοca b edο f图⼀图⼆图三7．设有向图（a ）、（b ）、（c ）与（d ）如图四所⽰，则下列结论成⽴的是 ( )．图四A ．（a ）是强连通的B ．（b ）是强连通的C ．（c ）是强连通的D ．（d ）是强连通的应该填写：D8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（）时，K n 中存在欧拉回路．A ．m 为奇数B ．n 为偶数C ．n 为奇数D ．m 为偶数 9．设G 是连通平⾯图，有v 个结点，e 条边，r 个⾯，则r = ( )．A ．e －v ＋2B ．v ＋e －2C ．e －v －2D ．e ＋v ＋2 10．⽆向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中⾄多有两个奇数度结点C ．G 连通且所有结点的度数全为偶数 D ．G 连通且⾄多有两个奇数度结点11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的⼀棵⽣成树．A ．1m n -+B ．m n -C ．1m n ++D ．1n m -+ 12．⽆向简单图G 是棵树，当且仅当( )．A ．G 连通且边数⽐结点数少1B ．G 连通且结点数⽐边数少1C ．G 的边数⽐结点数少1D ．G 中没有回路．⼆、填空题1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是． 2．设给定图G (如图四所⽰)，则图G 的点割οοοοc a b f集是．3．若图G=中具有⼀条汉密尔顿回路，则对于结点集V 的每个⾮空⼦集S ，在G 中删除S 中的所有结点得到的连通分⽀数为W ，则S 中结点数|S|与W 满⾜的关系式为．4．⽆向图G 存在欧拉回路，当且仅当G 连通且．5．设有向图D 为欧拉图，则图D 中每个结点的⼊度．应该填写：等于出度6．设完全图K n 有n 个结点(n 2)，m 条边，当时，K n 中存在欧拉回路．7．设G 是连通平⾯图，v , e , r 分别表⽰G 的结点数，边数和⾯数，则v ，e 和r 满⾜的关系式．8．设连通平⾯图G 的结点数为5，边数为6，则⾯数为． 9．结点数v 与边数e 满⾜关系的⽆向连通图就是树．10．设图G 是有6个结点的连通图，结点的总度数为18，则可从G 中删去条边后使之变成树．11．已知⼀棵⽆向树T 中有8个结点，4度，3度，2度的分⽀点各⼀个，T 的树叶数为．12．设G ＝是有6个结点，8条边的连通图，则从G 中删去条边，可以确定图G 的⼀棵⽣成树．13．给定⼀个序列集合{000，001，01，10，0}，若去掉其中的元素，则该序列集合构成前缀码．三、判断说明题1．如图六所⽰的图G 存在⼀条欧拉回路．2．给定两个图G 1，G 2（如图七所⽰）：（1）试判断它们是否为欧拉图、汉密尔顿图？并说明理由．（2）若是欧拉图，请写出⼀条欧拉回路．v 123图六图七3．判别图G (如图⼋所⽰)是不是平⾯图，并说明理由．4．设G 是⼀个有6个结点14条边的连通图，则G 为平⾯图．四、计算题1．设图G =，其中V ={a 1, a 2, a 3, a 4, a 5},E ={，，，，}（1）试给出G 的图形表⽰；（2）求G 的邻接矩阵；（3）判断图G 是强连通图、单侧连通图还是弱连通图？2．设图G =，V ={ v 1，v 2，v 3，v 4，v 5}，E ={ (v 1, v 2)，(v 1, v 3)，(v 2, v 3)，(v 2, v 4)，(v 3, v 4)，(v 3, v 5)，(v 4, v 5) }，试（1）画出G 的图形表⽰；（2）写出其邻接矩阵；（2）求出每个结点的度数；（4）画出图G 的补图的图形． 3．设G =，V ={ v 1，v 2，v 3，v 4，v 5}，E ={ (v 1,v 3)，(v 2,v 3)，(v 2,v 4)，(v 3,v 4)，(v 3,v 5)，(v 4,v 5) }，试（1）给出G 的图形表⽰；（2）写出其邻接矩阵；（3）求出每个结点的度数；（4）画出其补图的图形． 4．图G =，其中V ={ a , b , c , d , e }，E ={ (a , b ), (a , c ), (a , e ), (b , d ), (b , e ), (c , e ), (c , d ), (d , e ) }，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G 的图形；（2）写出G 的邻接矩阵；（3）求出G 权最⼩的⽣成树及其权值．5.⽤Dijkstra 算法求右图中A 点到其它各点的最短路径。

图论试题及答案解析图片一、选择题1. 图论中，图的基本元素是什么？A. 点和线B. 点和面C. 线和面D. 点和边答案：A2. 在无向图中，如果两个顶点之间存在一条边，则称这两个顶点是：A. 相邻的B. 相连的C. 相等的D. 相异的答案：A3. 在有向图中，如果从顶点A到顶点B有一条有向边，则称顶点A是顶点B的：A. 父顶点B. 子顶点C. 邻接顶点D. 非邻接顶点答案：B4. 一个图的度是指：A. 图中顶点的总数B. 图中边的总数C. 一个顶点的边数D. 图的连通性答案：C5. 一个图是连通的，当且仅当：A. 图中任意两个顶点都是相邻的B. 图中任意两个顶点都可以通过边相连C. 图中任意两个顶点都可以通过路径相连D. 图中任意两个顶点都可以通过子顶点相连答案：C二、填空题1. 在图论中，一个顶点的度数是该顶点的________。

答案：边数2. 如果一个图的任意两个顶点都可以通过边相连，则称该图为________。

答案：完全图3. 一个图中，如果存在一个顶点到其他所有顶点都有边相连，则称该顶点为________。

答案：中心顶点4. 图论中，最短路径问题是指在图中找到两个顶点之间的________。

答案：最短路径5. 如果一个图的任意两个顶点都可以通过有向路径相连，则称该图为________。

答案：强连通图三、简答题1. 请简述图论中的欧拉路径和哈密顿路径的定义。

答案：欧拉路径是指在图中经过每条边恰好一次的路径，而哈密顿路径是指在图中经过每个顶点恰好一次的路径。

2. 什么是图的着色问题？答案：图的着色问题是指将图中的顶点用不同的颜色进行标记，使得相邻的两个顶点颜色不同。

四、计算题1. 给定一个无向图G，顶点集为{A, B, C, D, E}，边集为{AB, BC, CD, DE, EA}，请画出该图，并计算其最小生成树的权重。

答案：首先画出图G的示意图，然后使用克鲁斯卡尔算法或普里姆算法计算最小生成树的权重。

【关键字】精品思考练习第一章1 对任意图，证明。

证：，故。

2 在一次聚会有个人参加，其中任意6个人中必有3个人互相认识或有3个人互不认识。

举例说明，将6个人改成5个人，结论不一定成立。

证：构图如下：图的顶点代表这6个人，两个顶点相邻当且仅当对应的两个人互相认识。

则对于图中任意一个点或。

不妨设及它的3个邻点为。

若中有任意两个点，不妨设为，相邻，则对应的3个人互相认识；否则，中任意两个点不邻，即它们对应的3个人互不认识。

若这5个人构成的图是5圈时，就没有3个人互相认识或有3个人互不认识。

3 给定图画出下列几个子图:(a) ；(b);(c)解：(a)(b)(c)第二章1 设是一个简单图，。

证明：中存在长度至少是的路。

证：选取的一条最长路，则的所有邻点都在中，所以，即中存在长度至少是的路。

2 证明：阶简单图中每一对不相邻的顶点度数之和至少是，则是连通图。

证：假设不连通，令、是的连通分支，对，有，与题设矛盾。

故连通。

3 设是连通图的一个回路，，证明仍连通。

证：，中存在路，1、若，则是中的路；2、若，则是中的途径，从而中存在路。

故连通。

4 图的一条边称为是割边，若。

证明的一条边是割边当且仅当不含在的任何回路上。

证：不妨设连通，否则只要考虑中含的连通分支即可。

必要性：假设在的某一回路上，则由习题2.13有连通，，与是割边矛盾。

故不在回路中。

充分性：假设不是割边，则仍连通，存在路，则就是含的一个回路，与不在回路中矛盾。

故是割边。

5证明：若是连通图，则。

证：若是连通图，则。

第三章1 证明：简单图是树当且仅当中存在一个顶点到中其余每个顶点有且只有一条路。

证：必要性：由定理充分性：首先可见连通。

否则，设有两个连通分支、，且，则到中的顶点没有路，与题设矛盾。

其次，中无回路。

否则，若有回路。

由于连通，到上的点有路，且设与的第一个交点为，则到上除外其余点都至少有两条路，又与题设矛盾。

故是树。

2 设图有个连通分支，。

证明含有回路。

1 设图G有12条边，G中有1度结点2个，2度结点2个，4度结点3个，其余结点度数不超过3．求G中至少有多少个结点？2 设有向简单图G的度数序列为(2,2,3,3）, 入度序列为(0,0,2,3),求G得出度序列 .3 设D是n阶有向简单完全图,则图D的边数为 .4设G是n阶无向简单完全图K n，则图G的边数为 .5 仅有一个孤立结点组成的图称为( )(A)零图(B)平凡图(C)补图(D)子图6设n阶图G中有m条边，每个结点的度数不是k的是k+1，若G中有N k个k度顶点，N k+1个k+1度顶点，则N k = .7设图G如右图.已知路径(1) P1=(v1e5 v5e7 v2e2 v3 )(2) P2=(v5e6 v2e2 v3e3 v4e8 v2e7 v5)(3) P3=(v2e7 v5e6 v2)(4) P4=(v1e1 v2e2 v3e3 v4e8 v2e6 v5)判断路径类型，并求其长度.81）判断下图G1中的路径类型, 并求其长度. P1=(v3e5v4e7v1e4v3e3v2e1v1e4v3)P2=(v3e3v2e2v2e1v1e4v3)P3=(v3e3v2e1v1e4v3).2）判断下图G2中的路径类型, 并求其长度. P1=(v1e1v2e6v5e7v3e2v2e6v5e8v4)P2=(v1e5v5e7v3e2v2e6v5e8v4)P3=(v1e1v2e6v5e7v3e3v4).v1e1e5v2e65e7e4 e2e8v3 4e3v e v1 设图G 有12条边，G 中有1度结点2个，2度结点2个，4度结点3个，其余结点度数不超过3．求G 中至少有多少个结点？ 至少9个2 设有向简单图G 的度数序列为(2,2,3,3）, 入度序列为(0,0,2,3),求G 得出度序列 （2,2,5,6） .3 设D 是n 阶有向简单完全图,则图D 的边数为 )1(−n n .4 设G 是n 阶无向简单完全图K n ，则图G 的边数为 m =n (n -1)/2 .5 仅有一个孤立结点组成的图称为( B ) (A) 零图 (B)平凡图 (C)补图 (D)子图6设n 阶图G 中有m 条边，每个结点的度数不是k 的是k+1，若G 中有N k 个k 度顶点，N k+1个k+1度顶点，则N k = N k =(k+1)n-2m . 7设图G 如右图.已知路径 (1) P 1=(v 1e 5 v 5e 7 v 2e 2 v 3 ) (2) P 2=(v 5e 6 v 2e 2 v 3e 3 v 4e 8 v 2e 7 v 5) (3) P 3=(v 2e 7 v 5e 6 v 2)(4) P 4=(v 1e 1 v 2e 2 v 3e 3 v 4e 8 v 2e 6 v 5)判断路径类型，并求其长度. (1) 初级通路；3 (2) 简单回路；5 (3) 初级回路；2 (4) 简单通路. 5 81）判断下图G1中的路径类型, 并求其长度. P 1=(v 3e 5v 4e 7v 1e 4v 3e 3v 2e 1v 1e 4v 3) P 2=(v 3e 3v 2e 2v 2e 1v 1e 4v 3) P 3=(v 3e 3v 2e 1v 1e 4v 3).2）判断下图G2中的路径类型, 并求其长度. P 1=(v 1e 1v 2e 6v 5e 7v 3e 2v 2e 6v 5e 8v 4) P 2=(v 1e 5v 5e 7v 3e 2v 2e 6v 5e 8v 4) P 3=(v 1e 1v 2e 6v 5e 7v 3e 3v 4).解：在图G 1中，v 3e 5v 4e 7v 1e 4v 3e 3v 2e 1v 1e 4v 3是一条长度为6的回路，但既不是简单回路，也不是初级回路； v 3e 3v 2e 2v 2e 1v 1e 4v 3是一条长度为4的简单回路，但不是初级回路； v 3e 3v 2e 1v 1e 4v 3是一条长度为3的初级回路。

图论练习题一、基本题1、设G是由5个顶点构成的完全图，则从G中删去（A）边可以得到树。

A．6 B．5 C．8 D．42、下面哪几种图不一定是树（A）。

A．无回路的连通图B．有n个结点，n-1条边的连通图C．对每对结点间都有通路的图D．连通但删去任意一条边则不连通的图3、5阶无向完全图的边数为（B）。

A．5 B．10 C．15 D．204、设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是（）A．n/2 B．n(n+1) C．nk-2m D．n(k+1)-2m5、设G=<V，E>为有向图，V={a,b,c,d,e,f}，E={<a,b>,<b,c>,<a,d>,<d,e>,<f,e>}是（B）。

A．强连通图B．单向连通图C．弱连通图D．不连通图6、在有n个结点的连通图中，其边数（B）A．最多有n-1条B．至少有n-1条C．最多有n条D．至少有n条7、设无向简单图的顶点个数为n，则该图最多有（C）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．n28、要连通具有n个顶点的有向图，至少需要（A ）条边。

A．n-l B．n C．n+l D．2n9、n个结点的完全有向图含有边的数目（B）。

A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）10、在一个无向图中，所有顶点的度数之和等于所有边数（B）倍。

A．1/2 B．2 C．1 D．411、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）倍。

A．1/2 B．2 C．1 D．412、连通图G是一棵树，当且仅当G中（B）A．有些边不是割边B．所有边都是割边C．无割边集D．每条边都不是割边13、4个顶点的完全图G，其生成树个数是（）。

A．4 B．8 C．16 D．64二、应用题题1、判断下图是否能一笔画出，并说明理由。

图论考试试题图论考试试题在计算机科学领域中，图论是一门重要的学科。

它研究的是图的性质和图上的算法。

图由节点和边组成，节点表示对象，边表示对象之间的关系。

图论可以应用于网络分析、社交网络、路径规划等领域。

图论的考试试题可以帮助学生加深对图论的理解和应用能力。

一、基本概念题1. 什么是图？答：图是由节点和边组成的数据结构。

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

2. 图的分类有哪些？答：图可以分为有向图和无向图。

有向图的边有方向，无向图的边没有方向。

另外，图还可以分为加权图和非加权图。

加权图的边具有权重，非加权图的边没有权重。

3. 什么是路径？答：路径是图中连接两个节点的边的序列。

4. 什么是连通图？答：连通图是指图中的任意两个节点之间都存在路径。

二、算法题1. 广度优先搜索算法（BFS）是如何工作的？答：广度优先搜索算法从起始节点开始，逐层遍历图中的节点。

它首先访问起始节点的所有邻居节点，然后依次访问邻居节点的邻居节点，直到遍历完所有可达节点。

2. 深度优先搜索算法（DFS）是如何工作的？答：深度优先搜索算法从起始节点开始，沿着一条路径一直向下访问直到无法继续为止，然后回溯到上一个节点，选择另一条路径继续访问，直到遍历完所有可达节点。

3. 如何判断一个图是否是二分图？答：二分图是指可以将图中的节点分为两个独立的集合，使得同一集合中的节点之间没有边相连。

判断一个图是否是二分图可以使用染色法。

从任意一个节点开始，将其染成红色，然后将其邻居节点染成蓝色，再将邻居节点的邻居节点染成红色，以此类推。

如果在染色过程中发现相邻节点颜色相同，则该图不是二分图。

三、应用题1. 在社交网络中，如何找到两个人之间的最短路径？答：可以使用广度优先搜索算法来找到两个人之间的最短路径。

从一个人开始，逐层遍历其朋友圈中的人，直到找到目标人。

在遍历过程中，可以记录路径，最后得到最短路径。

2. 在电信网络中，如何找到两个城市之间的最短路径？答：可以使用迪杰斯特拉算法来找到两个城市之间的最短路径。

图论试题及答案解析图片一、选择题1. 在图论中，一个图的顶点数为n，那么这个图最多有多少条边？A. nB. n(n-1)/2C. n^2D. 2n答案：B解析：在一个无向图中，每个顶点最多与其他n-1个顶点相连，因此最多有n(n-1)/2条边。

2. 什么是连通图？A. 至少有一个环的图B. 任意两个顶点都可以通过路径相连的图C. 没有孤立顶点的图D. 所有顶点度数都大于0的图答案：B解析：连通图是指图中任意两个顶点都可以通过路径相连的图。

3. 在图论中，什么是哈密顿路径？A. 经过图中所有顶点的路径B. 经过图中所有边的路径C. 经过图中所有顶点的回路D. 经过图中所有边的回路答案：A解析：哈密顿路径是指经过图中所有顶点的路径。

4. 什么是二分图？A. 图的顶点可以被分成两个不相交的集合，使得同一集合内的顶点不相邻B. 图的顶点可以被分成两个不相交的集合，使得同一集合内的顶点相邻C. 图的边可以被分成两个不相交的集合，使得同一集合内的边不相邻D. 图的边可以被分成两个不相交的集合，使得同一集合内的边相邻答案：A解析：二分图是指图的顶点可以被分成两个不相交的集合，使得同一集合内的顶点不相邻。

5. 在图论中，什么是最小生成树？A. 包含图中所有顶点的最小边数的生成树B. 包含图中所有顶点的最小权重的生成树C. 包含图中所有边的最小权重的生成树D. 包含图中所有边的最小边数的生成树答案：B解析：最小生成树是指包含图中所有顶点的最小权重的生成树。

二、填空题1. 在无向图中，如果一个顶点的度数为n，则该顶点至少有______条边。

答案：n解析：一个顶点的度数是指与该顶点相连的边的数量。

2. 如果一个图是连通的，那么该图至少有______个连通分量。

答案：1解析：连通图的定义是图中任意两个顶点都可以通过路径相连，因此至少有一个连通分量。

3. 在图论中，一个图的色数是指给图的顶点着色，使得相邻顶点颜色不同，所需的最小颜色数。

一、历年全国数学建模试题及解法赛题解法93A 非线性交调的频率设计拟合、规划93B 足球队排名图论、层次分析、整数规划94A 逢山开路图论、插值、动态规划94B 锁具装箱问题图论、组合数学95A 飞行管理问题非线性规划、线性规划95B 天车与冶炼炉的作业调度动态规划、排队论、图论96A 最优捕鱼策略微分方程、优化96B 节水洗衣机非线性规划97A 零件的参数设计非线性规划97B 截断切割的最优排列随机模拟、图论98A 一类投资组合问题多目标优化、非线性规划98B 灾情巡视的最灾情巡视的最佳佳路线图论、组合优化99A 自动化车动化车床床管理随机优化、计随机优化、计算算机模拟99B 钻井布局0-1规划、图论00A DNA 序列分类模式识别式识别、、Fisher 判别判别、、人工神经网络00B 钢管订购和运输组合优化、组合优化、运输运输运输问题问题01A 血管三维重建曲线拟合、线拟合、曲面重建曲面重建01B 工交车调度问题多目标规划02A 车灯线光源光源的优化的优化非线性规划02B 彩票彩票问题问题问题 单目标目标决决策 03A SARS 的传播传播 微分方程、微分方程、差差分方程分方程03B 露天矿生产矿生产的车的车的车辆安辆安辆安排排 整数规划、整数规划、运输运输运输问题问题问题 04A 奥运会临时超市网点奥运会临时超市网点设计设计设计 统计分析、数计分析、数据处据处据处理、优化理、优化理、优化 04B 电力市场电力市场的的输电阻塞输电阻塞管理管理管理 数据拟合、优化拟合、优化 05A 长江长江水水质的评价和预测评价和预测 预测评价预测评价、数、数、数据处据处据处理理 05B DVD 在线租赁租赁 随机规划、整数规划随机规划、整数规划二、赛题发展的特点1.对选手对选手的计的计的计算算机能力提出了更高能力提出了更高的的要求：要求：赛题的解赛题的解赛题的解决依赖决依赖决依赖计计算机，题目的数题目的数据较据较据较多多，手工，手工计计算不能完成，如03B ，某些，某些问题问题问题需要需要需要使用使用使用计计算机软件，01A 。

数学竞赛图论试题及答案一、选择题（每题5分，共20分）1. 在一个无向图中，如果有5个顶点，每个顶点至少与另外两个顶点相连，那么这个图至少有多少条边？A. 5B. 6C. 7D. 82. 一个图是二分图当且仅当它没有奇环。

这个说法是正确的吗？A. 是B. 否3. 给定一个有n个顶点的完全图，求出该图的边数。

A. n(n-1)/2B. n(n+1)/2C. n^2D. 2n4. 在一个图中，如果存在一条从顶点u到顶点v的简单路径，则称u 可达v。

如果图中任意两个顶点都是相互可达的，那么这个图是：A. 连通图B. 强连通图C. 有向无环图D. 欧拉图二、填空题（每空5分，共30分）5. 一个图的度序列是指图中所有顶点的度按照______排列的序列。

6. 如果一个图的边数等于顶点数的两倍，那么这个图一定是______。

7. 在图论中，一个图的最小生成树是指连接所有顶点的______的树。

8. 一个图的着色数是指对图中的顶点进行着色，使得任何两个相邻的顶点颜色都不同，使用的最小颜色数。

三、简答题（每题25分，共50分）9. 描述什么是图的平面性，并给出判断一个图是否为平面图的方法。

10. 解释什么是图的哈密顿回路，并给出一个例子。

答案一、选择题1. C（根据边数的最小值公式，边数至少为顶点数减一的两倍）2. B（二分图没有奇环，但不是所有没有奇环的图都是二分图）3. A（完全图的边数公式）4. A（连通图的定义）二、填空题5. 非增6. 完全二部图7. 边数最少8. 最小三、简答题9. 图的平面性指的是图可以画在平面上，使得图中的边除了端点外不相交。

判断一个图是否为平面图的方法有库拉托夫斯基定理，即如果一个图包含一个子图同构于K5（完全五顶点图）或K3,3（完全二部图），则该图是非平面的。

10. 哈密顿回路是一条通过图中每个顶点恰好一次的闭合回路。

例如，一个正方形的四个顶点可以形成一个哈密顿回路，因为可以按照顺时针或逆时针方向依次访问每个顶点一次。