图论试卷A卷-14数本

离散数学图论部分综合练习一、单项选择题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 ＝<V , E >，则下列结论成立的是 ( )．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 )}是边割集ο ο ο ο οcab edο f图一图二C．{(a, e) ,(b, c)}是边割集D．{(d, e)}是边割集图三7．设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是( )．图四A．（a）是强连通的B．（b）是强连通的C．（c）是强连通的D．（d）是强连通的应该填写：D8．设完全图Kn 有n个结点(n≥2)，m条边，当（）时，Kn中存在欧拉回路．A．m为奇数B．n为偶数C．n为奇数D．m 为偶数9．设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v ＋210．无向图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连通且边数比结点数少1 B．G连通且结点数比边数少1C ．G 的边数比结点数少1D ．G 中没有回路．二、填空题1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 集是 ．3．若图G=<V , E>中具有一条汉密尔顿回路， 则对于结点集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 ＝<V , E >是有6个结点，8条边的连通图，则从G 中删去 条边，可以确定图G 的一棵生成树．13．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素 ，则该序列集合构成前缀码．三、判断说明题1．如图六所示的图G 存在一条欧拉回路．ο οο ο οca b e dο f 图四2．给定两个图G 1，G 2（如图七所示）：（1）试判断它们是否为欧拉图、汉密尔顿图？并说明理由． （2）若是欧拉图，请写出一条欧拉回路．图七3．判别图G (如图八所示)是不是平面图， 并说明理由．4．设G 是一个有6个结点14条边的连 通图，则G 为平面图．四、计算题1．设图G =<V ，E >，其中V ={a 1, a 2, a 3, a 4, a 5},E ={<a 1, a 2>，<a 2, a 4>，<a 3, a 1>，<a 4, a 5>，<a 5, a 2>}（1）试给出G 的图形表示； （2）求G 的邻接矩阵；（3）判断图G 是强连通图、单侧连通图还是弱连通图？ 2．设图G =<V ，E >，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 ，E >，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) }，试v 1v 2v 3v 4v 5v 6v 1v 2v 3v 5 d bae f ghn图六οοο ο οv 5v 1 v 2 v 4v 6 ο v 3图八（1）给出G的图形表示；（2）写出其邻接矩阵；（3）求出每个结点的度数；（4）画出其补图的图形．4．图G=<V, E>，其中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点到其它各点的最短路径。

离散数学图论单元测验题一、单项选择题(本大题共10小题，每小题2分，共20分)1、在图G ＝<V ,E >中，结点总度数与边数的关系是( )(A) deg(v i )=2∣E ∣ (B) deg(v i )=∣E ∣ (C)∑∈=V v E v 2)deg( (D) ∑∈=Vv E v )deg(2、设D 是n 个结点的无向简单完全图，则图D 的边数为( )(A) n (n －1) (B) n (n +1) (C) n (n －1)/2 (D) n (n +1)/23、 设G ＝<V ,E >为无向简单图，∣V ∣=n ，∆(G )为G 的最大度数，则有(A) ∆(G )<n (B)∆(G )≤n (C) ∆(G )>n (D) ∆(G )≥n4、图G 与G '的结点和边分别存在一一对应关系，是G ≌G '(同构)的( )(A) 充分条件 (B) 必要条件 (C)充分必要条件 (D)既非充分也非必要条件5、设},,,{d c b a V =，则与V 能构成强连通图的边集合是( )(A) },,,,,,,,,{><><><><><=c d b c d b a b d a E(B) },,,,,,,,,{><><><><><=c d d b c b a b d a E(C) },,,,,,,,,{><><><><><=c d a d c b a b c a E6、有向图的邻接矩阵中，行元素之和是对应结点的( )，列元素之和是对应结点的() (A)度数 (B) 出度 (C)最大度数 (D) 入度7、设图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100000100则G 的边数为( )．A ．5B ．6C ．3D ．48、设m E n V E V G ==>=<,,,为连通平面图且有r 个面，则r ＝( )(A) m －n +2 (B) n －m －2 (C) n +m -2 (D) m +n +29、在5个结点的二元完全树中，若有4条边，则有 ( )片树叶。

《图论》课程考试试卷（A）适用专业：信计本科生考试日期：2011年6月考试时间：120分钟；考试方式：闭卷；总分100分一、填空题. （6小题，每小题3分，共18分）1 树中所有度大于1的顶点都是。

2 称为欧拉图。

3 若G是连通的(),p q图，则它的一棵生成树有条边。

4 求一个连通图的生成树的两种方法：和。

5 使图G为n-着色的n最小数值称为G的。

6 如果M中任意两条边在G中均不邻接，则称M是G的一个。

二解答题（5小题，共38分）1 假设A，B……G是7个哨所,监视着11条路段(如下图所示),为节省人力,问至少需要在几个哨所派人站岗,就可以监视全部路段,写出具体的一个可行方案?（6分）2 试作出下列二图作的并，交与环和。

（8分）3写出下图的关联集，并由此求出图的全部断集。

（10分）4 写出下图的完全关联矩阵。

（8分）5 画出下图的对偶图(在原图上用另一种颜色的笔画出来)。

（6分）三 应用题 （3小题，共34分）6 如下图，现准备在g f e d c b a ,,,,,,七个居民点设置一银行，各点之间距离由图给出，则银行设在哪个点可使最大服务距离最小？若要设置两个银行，则设在哪两个点？（12分）7 在通信中，0、1、2、…、7出现的频率如下：0：30％，1：20％，2：15％，3：10％，4：10％，5：5％，6：5％，7：5％ 求传输它们的最佳前缀码。

（12分）8 求下述网络的最大流。

（10分）四 证明题 （1小题，每小题10分，共10分）9、若图(,)G V E =不是哈密顿图(3)V ≥，证明至少有一个顶点的度适合deg()2v V <。

计算机04级代数系统及图论试题（A ）答案一、证明：（1） 由表1可得<{e,a},*>的运算表如下：（酌情给1~5分）由表可知，幺元为e ，a 的逆元为a ，显然运算满足封闭性、结合律，故<{e,a},*>是一个群。

（酌情给1~5分）（2） 设{e,a}=M ，则M 的所有左陪集有bM={a,b}，cM={b,c}，dM={c,e} （酌情给1~5分）若<G ,*>是群，则应满足 |M|⎢|G|，但|M|=2，|G|=5，故<G ,*>不是群。

（酌情给1~5分）二、证明：必要性设f 是入射。

因为f(e)=e ’，所以e ∈Ker(f)。

若另有a ∈G ，使得f(a)=e ’，则f(a)=f(e)，由于f 是入射，故必有a=e ，因此Ker(f)={e}。

（酌情给1~5分）充分性设Ker(f)={e}。

对于a,b ∈G 1，如果f(a)=f(b)，则有f(b*a -1)=f(b)∆f(a -1)=f(a)∆f(a -1)= f(a*a -1)=f(e)=e ’,故b*a -1∈Ker(f)，所以b*a -1=e ，因此有（b*a -1）*a=e*a ，即b=a ，所以f 是入射。

（酌情给1~5分） 三、(a)不是格，(b),(c),(d)都是格；（酌情给1~4分）其中(b)是有界格、分配格；(c)是有界格、分配格、有补格；(d)是有界格、有补格。

（酌情给1~6分） 四、证：设a 是L 中的任意一个元素，如果21,a a 都是a 的补元，则有)()()()()()()()(2112212221211211a a a a a a a a a a a a a a a a a a a a ∧=∧∨∧=∨∧=∧=∧∨∧=∨∧=故有21a a =。

（酌情给1~10分）其它正确的证明方法。

（酌情给1~10分） 五、解：G 与G 的并为完全图K n ，因为n 为奇数，所以K n 中每个顶点的度为n-1，为偶数。

重庆邮电大学08-09学年度第一学期《图论及其应用》研究生考试试题（A ）（时间120分钟）1、设>=<ϕ,,E V G 是任意图，其中12{,,,}n V x x x =，12{,,,},m E e e e =则n 阶方阵)(ij a A =称为G 的邻接矩阵。

其中ij a 为 。

2、图>=<E V V G ,,21是二分图的充要条件是： 。

3、n K (n ≥3)中从任意指定一个顶点出发,有（ ）个不同的圈。

A.n ！ B.（n-1）！ C.（n-2）！ D.（n-3）！ 4、设T 是顶点数至少为5的树,则()x T =( ) A.2 B.3 C.4 D.5 5、带权为1,2,3,4,5,6的最优二叉树的权为 ( )。

A.48 B.49 C.50 D.51 6、若G 为长度是奇数的圈，则()x G =( ). 7、以0，1为构成元素，写出一个三阶格雷码。

8、设连通图G 具有欧拉回路的充要条件是 。

9、写出所有的正凸多面体： 。

10、设G 是任意平面图，则()G δ应满足的条件 。

二、(6分)画出4阶3条边的所有非同构的无向简单图。

三、(6分)证明：若无向图G 中恰有两个奇度顶点，则这两个奇度顶点必然连通。

————密———————————— —封————————————线————————————————————————————年级：专业： 班级：姓名：学号：—————————————————————————————————————————————————————————————四、(10分)已知完全二分图5,5K ,其中112345{,,,,}V x x x x x =，212345{,,,,}V y y y y y =,且5,5K 的权矩阵为A ，求5,5K 的最优匹配，并求出权和。

3554122022244100110012133A ⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦五、(10分)用普林算法求下图1的一棵最小生成树.六、(10’)画一个四阶五条边的欧拉图，并做出该图的对偶图.七、(10分)通过布尔变量的运算，求下图3的全部极小支配集。

东北大学考试试卷（A卷）2010—2011 学年第 2 学期课程名称：图论与代数结构┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄总分一二三四五六七八九学院班级学号姓名……………○……………密……………○……………封……………○…………线………………得分一．(15分) 填空1.设A={2, 4, 6, 8}，A上的二元运算*定义为：a*b=max{a, b}，则在独异点<A,*>中，单位元是 2 ，零元是8 。

2.设a是12阶群的生成元，则a2是 6 阶元素，a5是12 阶元素。

3.设〈G, *〉是一个群，G中的幂等元是 e 。

若G={a,b,c}，a*x=b，则x=a-1*b ；设a是幺元，则b*c= a 。

4.小于5个元素的格都是有补分配（布尔）格。

5.有n个结点的树，其结点度数之和是2(n-1)。

6.一个无向图有生成树的充分必要条件是该图是连通图__。

7.n阶无向完全图Kn 的边数是n(n-1)/2 ，每个结点的度数是n-1 。

若Kn为欧拉图，则n的取值为奇数。

8.具有6 个顶点，12条边的连通简单平面图中，每个面都是由 3 条边围成。

9.无向树T有8片树叶，2个3度分支结点，其余的分支结点都是4度顶点，则 2 个4度分支结点。

得分二． (26分)判断题4.（6分）判断下列集合和运算能否构成半群、独异点和群。

如果不能，简单说明理由。

（1）a是正整数，G={a n|n∈Z，Z为整数集}, 运算是普通乘法。

是半群、独异点和群。

（2分）（2）Q+是正有理数集，运算为普通加法。

（2分）是半群，不是独异点和群。

满足封闭、结合，但没有幺元。

（3）设Z为整数集，∀ x,y∈Z, 运算x*y=x+y-2。

是半群、群和独异点。

（2分）1.（6分）设V1=<Z,+>, V2=<Z, •>，其中Z为整数集合，+和•分别代表普通加法和乘法。

判断下述集合S能否构成V1和V2的子半群和子独异点。

哈尔滨工业大学（威海）继续教育学院年春季学期集合与图论本科试题考试形式：开卷答题时间：90 分钟本卷面成绩站课程成绩100 %（所有答案必须写在答题纸上、标清题号）一、填空题(每空2分，计20分)1. 集合{0}的所有子集是______________。

2. 设A={1,2,3,{1,2},{3}}，B={2,{1},{2,3}}，则B- A=__________。

3. 有偏序集(N,≤)，即自然数集N上的小于等于关系，N的子集A={2,3,6,8}的下确界和上确界分别是______、_______。

4. 设A={1,2,3,4,5,6}，R={<1,5>,<2,3>,<2,6>,<3,2>,<3,6>,<5,1>, <6,2>,<6,3>}∪I A，则[1]=_____________，[2]=_______________。

5. n个顶点的有向完全图边数是______，每个顶点的度数是_____。

6. 设图G1=<V1, E1>和G2=<V2, E2>，若____________，则G2是G1的真子图；若____________，则G2是G1的生成子图。

二、简答题(每题 10 分，计 40 分)1. 设A是一个非空集合，问(1)A上是否存在一个既是等价关系又是偏序关系的关系？若不存在，请说明理由；若存在，请给出一个实例。

(2) A上是否存在一个既是自反的又是反自反的关系？若不存在，请说明理由；若存在，请给出一个实例。

2. 是否存在每个顶点的度数≥3且只有7条边的简单平面连通图？请说明理由。

3. 某公司来了9名新员工，工作时间不能互相交谈，为了尽快互相了解，他们决定利用每天吃午饭时间相互交谈，于是，每天吃午饭时他们围在一张圆桌旁坐下，他们是这样安排的，每一次每人的左右邻均与以前的人不同，问这样的安排法能坚持多久？4. 有向图D如图所示，(1) 给出D的邻接矩阵A；(2) D中长度为1, 2, 3, 4的通路各有多少条？其中回路分别为多少条？(3) D中长度小于或等于4的通路为多少条？其中有多少条回路？三、计算题(每题 10 分，计 20 分)1. 设A ＝{a, b, c, d}，R 是A 上的二元关系，且R ＝{<a, b>, <b, a>, <b, c>, <c, d>}，求r(R)、s(R)和t(R)。

图论试题及答案解析图片一、选择题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、给定⽆向图如图所⽰，下⾯给出的顶点集⼦集中，是点割集的为（A,B,C,D）。

A. {b, d} B. {d} C. {a, c} D. {g, e} bf 内容需要下载⽂档才能查看 2、设V＝{a,b,c,d},与V能构成强连通图的边集E＝（ A ）。

A. {,,,,} B. {,,,,} C. {,,,,} {,,,,} 3、⼀个连通的⽆向图G，如果它的所有结点的度数都是偶数，那么它具有⼀条（ B ）。

A. 哈密尔顿回路 B. 欧拉回路 C. 哈密尔顿通路 D. 欧拉通路 4、如图所⽰各图，其中存在哈密顿回路的图是（ A, C ）。

内容需要下载⽂档才能查看 第 1 页共 5 页 图论期末考试题⽬参考 《图论》 5. 下图中既是欧拉图，⼜是哈密尔顿图的有（D）。

5、设G是有5个顶点的完全图，则G（ B ）。

D. ⽆哈密尔顿路 E. 可以⼀笔画出 F. 不能⼀笔画出 G. 是平⾯图 6、设G是连通简单平⾯图，G中有11个顶点5个⾯，则G中的边是（ D ）。

A. 10 B. 12 C. 16 D. 14 ⼆、填空题 1、完全图K8具有（ 28 ）条边。

2、图G如图所⽰， ab fc 那么图G的割点是（ a, f ）。

e d 3、⽆向图G为欧拉图，当且仅当G是连通的，且G中⽆（奇数度）结点。

第 2 页共 5 页 图论期末考试题⽬参考 《图论》 4、连通有向图D含有欧拉回路的充分必要条件是（ D中每个结点的⼊度＝出度）。

5、 n个结点、m条边的⽆向连通图是树当且仅当m=__（3）___。

(1) n+1 (2) n (3) n-1 (4)2n-1 三、 1、设图G=(P,E) 中有12条边，6个度数为3的顶点，其余顶点的度数均⼩于3，求G⾄少有多少个顶点。

解答：设G有n个顶点，由定理1， ∑d i=1nG(vi)=2m=24 (|E|=m) 由题设 24<3×6+3(n?6) ∴ 3n>24 即 n>8 因此，G中⾄少有9个顶点。

图论复习题（二）图论复习题一、选择题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 ．E v 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 ）。