2011研究生图论期末试题

目录第一章图的基本概念 (1)二路和连通性 (3)第二章树 (3)第三章图的连通度 (4)第四章欧拉图与哈密尔顿图 (5)一，欧拉图 (5)二．哈密尔顿图 (6)第五章匹配与因子分解 (9)一．匹配 (9)二．偶图的覆盖于匹配 (10)三．因子分解 (11)第六章平面图 (14)二．对偶图 (16)三．平面图的判定 (17)四．平面性算法 (20)第七章图的着色 (24)一．边着色 (24)二．顶点着色 (25)第九章有向图 (30)二有向树 (30)第一章图的基本概念1.点集与边集均为有限集合的图称为有限图。

2.只有一个顶点而无边的图称为平凡图。

3.边集为空的图称为空图。

4.既没有环也没有重边的图称为简单图。

5.其他所有的图都称为复合图。

6.具有二分类（X, Y）的偶图（或二部图）：是指该图的点集可以分解为两个（非空）子集X 和Y ，使得每条边的一个端点在X 中，另一个端点在Y 中。

7.完全偶图：是指具有二分类（X, Y）的简单偶图，其中X的每个顶点与Y 的每个顶点相连，若|X|=m，|Y|=n，则这样的偶图记为Km,n8. 定理1 若n 阶图G 是自补的（即），则n = 0, 1（mod 4）9. 图G 的顶点的最小度。

10. 图G 的顶点的最大度。

11. k-正则图: 每个点的度均为 k 的简单图。

例如,完全图和完全偶图Kn,n 均是正则图。

12. 推论1 任意图中，奇点的个数为偶数。

13.14. 频序列：定理4 一个简单图G 的n 个点的度数不能互不相同。

15. 定理5 一个n 阶图G 相和它的补图有相同的频序列。

16.17.18. 对称差：G1△G2 = (G1∪G2) - (G1∩G2) = (G1-G2)∪(G2-G1)19. 定义： 联图 在不相交的G1和G2的并图G1+G2中，把G1的每个顶点和G2的每个顶点连接起来所得到的图称为G1和G2的联图，记为G1∨G220. 积图：积图 设G1= (V1, E1)，G2 = (V2, E2)，对点集V = V1×V2中的任意两个点u =(u1,u2)和v = (v1,v2)，当(u1 = v1和 u2 adj v2) 或 (u2 = v2 和 u1 adj v1) 时就把 u 和 v 连接起来所得到的图G 称为G1和G2积图。

东北大学考试试卷（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的子半群和子独异点。

图论测试题及答案一、选择题1. 在图论中，如果一个图的每个顶点的度数都是偶数，那么这个图一定存在欧拉路径吗？A. 是的B. 不一定C. 没有欧拉路径D. 无法确定答案：B2. 图论中的哈密顿路径是指什么？A. 经过图中所有顶点的路径B. 经过图中所有顶点的回路C. 经过图中某些顶点的路径D. 经过图中某些顶点的回路答案：A3. 如果一个图是完全图，那么它的边数是多少？A. 顶点数的一半B. 顶点数的平方C. 顶点数的两倍D. 顶点数减一答案：B二、填空题4. 在无向图中，如果存在一条路径，使得每个顶点只被经过一次，并且起点和终点相同，这样的路径被称为________。

答案：欧拉回路5. 图论中的二分图是指图中的顶点可以被分成两个不相交的集合，使得同一个集合内的顶点之间没有边，而不同集合之间的顶点之间有边，这种图也被称为________。

答案：二部图三、简答题6. 请简述图论中的最短路径问题，并给出解决该问题的一种算法。

答案：最短路径问题是在图中找到两个顶点之间的最短路径的问题。

解决该问题的一种算法是迪杰斯特拉算法（Dijkstra's algorithm），该算法通过维护一个顶点集合来记录已经找到最短路径的顶点，并迭代更新距离，直到找到从起点到所有顶点的最短路径。

7. 描述图论中的图着色问题，并说明其在实际生活中的应用。

答案：图着色问题是将图的顶点着色，使得任何两个相邻的顶点颜色不同。

在实际生活中，图着色问题可以应用于时间表的安排、频率分配、电路设计等领域，其中每个顶点代表一个任务或频道，而颜色则代表不同的时间段或频率。

结束语：以上是图论测试题及答案，希望能够帮助大家更好地理解和掌握图论的基本概念和算法。

图论及网络总复习题一、选择题1、设G是由5个顶点构成的完全图，则从G中删去（）边可以得到树。

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

A．无回路的连通图B．有n个结点，n-1条边的连通图C．对每对结点间都有通路的图D．连通但删去任意一条边则不连通的图。

3、5阶无向完全图的边数为（）。

A．5 B．10 C．15 D．204、把平面分成x个区域，每两个区域都相邻，问x最大为（）A．6 B．4 C．5 D．35、设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是（）A．n/2 B．n(n+1) C．nk-2m D．n(k+1)-2m 6、图G1和G2的结点和边分别存在一一对应关系是G1和G2同构的（）。

A．充分条件B．必要条件C．充分必要条件D．既不充分也不必要条件7、设G=<V，E>为有向图，V={a,b,c,d,e,f}，E={<a,b>,<b,c>,<a,d>,<d,e>,<f,e>}是（）。

A．强连通图B．单向连通图C．弱连通图D．不连通图8、无向图G中的边e是G的割边（桥）的充分必要条件是（）。

A．e是重边B．e不是重边C．e不包含在G的任一简单回路中D．e不包含在G的某一简单回路中9、在有n个结点的连通图中，其边数（）A．最多有n-1条B．至少有n-1条C．最多有n条D．至少有n条10．设无向简单图的顶点个数为n，则该图最多有（）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．n211．n个结点的完全有向图含有边的数目（）。

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

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

图论试题及答案解析图片一、选择题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. 高斯答案：A2. 在图论中，一个图的顶点集合为空，但边集合不为空的图称为（）。

A. 空图B. 完全图C. 树D. 多重图答案：A3. 如果一个图的任意两个顶点之间都存在一条路径，则称该图为（）。

A. 连通图B. 强连通图C. 弱连通图D. 无环图答案：A4. 在图论中，一个图的边的集合可以划分为若干个不相交的路径，使得图中的每个顶点恰好属于其中一条路径，这样的图称为（）。

A. 欧拉图B. 哈密顿图C. 树答案：C5. 图论中，一个图的边的集合可以划分为若干个不相交的回路，使得图中的每个顶点恰好属于其中一条回路，这样的图称为（）。

A. 欧拉图B. 哈密顿图C. 树D. 环答案：A二、多项选择题1. 下列哪些是图论中的基本术语（）。

A. 顶点B. 边D. 权重答案：ABCD2. 在图论中，以下哪些图是无向图（）。

A. 完全图B. 树C. 多重图D. 有向图答案：ABC3. 图论中，以下哪些图是连通图（）。

A. 完全图B. 树C. 多重图D. 空图答案：ABC三、填空题1. 图论中，一个图的顶点集合为V，边集合为E，那么图可以表示为G=（）。

答案：(V, E)2. 如果一个图的任意两个顶点之间都存在一条路径，则称该图为（）。

答案：连通图3. 在图论中，一个图的边的集合可以划分为若干个不相交的路径，使得图中的每个顶点恰好属于其中一条路径，这样的图称为（）。

答案：树四、简答题1. 请解释什么是图论中的“完全图”？答案：完全图是指图中每一对不同的顶点之间都恰好有一条边相连的图。

在完全图Kn中，n个顶点两两相连，共有n(n-1)/2条边。

2. 请解释什么是图论中的“欧拉路径”和“欧拉回路”？答案：欧拉路径是指图中存在一条路径，该路径恰好经过每条边一次。

欧拉回路是指图中存在一条回路，该回路恰好经过每条边一次。

五、计算题1. 给定一个图G=(V, E)，其中V={A, B, C, D, E}，E={(A, B), (B, C), (C, D), (D, E), (E, A), (A, C)}，请判断该图是否为连通图，并说明理由。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

《图论》考试试卷（A卷）班级_________________ 姓名 ____________________ 学号____________________一、填空题（每空2分，共30分）1.____ 条边的图中全部顶点的总次数是100。

2.100个顶点的星的最大顶点次数是 _____ o3.____ 个顶点的图的生成子树中有 ______ 个顶点和100条边。

4.Peterson 图____ （是、否）Euler 图，____ （是、否）Hamilton 图。

5.Kg的每个顶点次数为_______ ，总共有____ 条边，有_____ 种完美匹配，它的平面嵌入的厚度下界为____ 。

6.对一个括号序列进行检测，从左向右数到第99个括号时，记录了右括号_______ 个，因此得出结论为坏括号序列。

7.100个顶点的极大连通平而图中最多有 _____ 条边，_____ 个面。

&有向图G的底图GC是连通的，则G至少为一______ 连通有向图；若存在一个以G的某个顶点％为根的外向树，则G为一______ 连通有向图。

二、画图题（每题5分，共15分）1.画岀所有不同构的5顶点树。

2.画出5次止则完全图，证明它是否为Euler图。

3.画出面数最多的6顶点连通二分平面图的平面嵌入,并指出它有几个面。

三、应用题（10分）1.有〃把钥匙和"把锁混在一起，确定知道每把锁都能有一把钥匙打开，锁匠想把它们一对对的分开，那么有多少种分法是每对中的钥匙都无法打开锁的。

①给出求解上述问题的递归公式，并证明之；②算出n = 6时问题的解。

四、算法题（第1、2、3每题10分，4题15分，共45分）1.写出用Kruskal算法求图1牛成子树的运行过程：①按算法的运行顺序写出每一轮所选的边；②写出对所选的边所进行的操作及其原因（指出算法如何判断所选边是否符合生成树的条件）；③给出算法终止的条件。

（设算法按照下标山小到大的顺序遍历所有边，R对每条边时/ ,都有j v Jo）2.若有5字符出现的概率表为字符a b c d e出现概率0.20.160.130.2S0.23写出用HulTman算法求上表中5字符Huffman编码的运行过程：①依“左子概率小于右子”的原则，按算法的运行顺序写出每一轮构造的由有序二元树组成的森林；②给出算法终止的条件；③按照“左0右1”的原则给出这5个字符的Huffman编码。

图论期末复习题1. 写出下图G 中三个结点的度数。

并求出该图的最大度、最小度。

该图是不是简单图？是不是欧拉图？半欧拉图？是不是平面图？画出该图关于完全图的补图。

vv 3vG G答：d(v1)=3,d(v2)=2，d(v3)=4，()4,()2G G δΔ==，图G 是简单图，不是欧拉b,a),(b,e),(b,c)}是否是边割集？该图的点连通度、边连通度分别为多少？{(b,a),(b,e),(b,c)}是边割集。

图G 的点连通度图，是半欧拉图。

是平面图。

其补图如下。

2. 给定图G1，集合{f}, {a,e,c}, {g,k,j}, {b,e,f,k,h}，哪些是点割集？ 集合{( G1 G2答：{a,e,c}, {g,k,j}, {b,e,f,k,h}都是点割集，{f}不是点割集，()3G κ=，边连通度()3G λ=。

多少条？长度不超过3的通路有多少条？该图是哪类连通？ 解：邻接矩阵，，3. 观察上面有向图G2，写出邻接矩阵，由邻接矩阵计算可达矩阵。

并计算：长度为3的通路有，4A ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦１２１１２２２３３３２３２１０１A ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦０１００００１１１１０１１０００2A ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦００１１２１０１１１１１０１００3A ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦２１０１１２１１２２１２００１１232212332344241111B A A A ⎡⎤⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥=++=++=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦⎣⎦０１００００１１２１０１００１１２１０１１２１１１１０１１１１１２２１２１００００１００００１１ 因此，可达矩阵 1111111111111111P ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦由矩阵，图G 中长度为3的通路共有3A 4(3),118ij i j a ==∑条。

由矩阵B ，图G 中长度不超过3的通路共有4,136ij i j b ==∑条。

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

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

A．无回路的连通图B．有n个结点，n-1条边的连通图C．对每对结点间都有通路的图D．连通但删去任意一条边则不连通的图。

3、5阶无向完全图的边数为（）。

A．5 B．10 C．15 D．20 4、设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是（）A．n/2 B．n(n+1) C．nk-2m D．n(k+1)-2m 5、设G=为有向图，则有（）。

A．E?V x V B．E?V x V C．V x V?E D．V x V=E 6、图G1和G2的结点和边分别存在一一对应关系是G1和G2同构的（）。

A．充分条件B．必要条件C．充分必要条件D．既不充分也不必要条件7、设G=为有向图，V={a,b,c,d,e,f}，E={,,,,}是（）。

A．强连通图B．单向连通图C．弱连通图D．不连通图8、无向图G中的边e是G的割边（桥）的充分必要条件是（）。

A．e是重边B．e不是重边C．e不包含在G的任一简单回路中D．e不包含在G的某一简单回路中9、在有n个结点的连通图中，其边数（）A．最多有n-1条B．至少有n-1条B．C．最多有n条D．至少有n条10．设无向简单图的顶点个数为n，则该图最多有（）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．n211．n个结点的完全有向图含有边的数目（）。

A．n*n Ｂ．n（n＋１）C．n／2 D．n*（n－l）12．一个有n 个结点的图，最少有（）个连通分量。

A．0 B．1 C．n-1 D．n13．一个有n个结点的图，最多有（）个连通分量。

A．0 B．1 C．n-1 D．n14．在一个无向图中，所有顶点的度数之和等于所有边数（）倍。

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

1 / 2南京邮电大学2010/2011学年 第一学期《图论与代数系统》清欠考试试卷本试卷共4页；考试时间110分钟；专业班级学号姓名为。

2．在代数系统(,,)N +⨯中，N 对运算+的幺元是__________，对运算⨯的幺元是____________。

3．设,A <≤>是一个偏序集， 则称,A <≤>为格。

4．有限布尔代数的元素的个数必定等于。

5．n 个结点的无向完全图n k 的边数为。

6．给定无孤立结点图G ，G 中的欧拉路是指。

7．若一条路中所有的边12,,...n e e e 均不相同，称作。

8．一个代数系统,*S <>，其中S 是非空集合，*是S 上的一个二元运算。

如果：（1），（2），则称代数系统,*S <>为半群。

二、判别题，正确的打√、错误的打⨯。

（20分，每题2分）1． 分配格一定是布尔格。

（ ） 2． 自然数集合上的减法运算是封闭的。

（ ）3． 强连通图一定是单侧连通的。

（ ）4． 群中一定有零元。

（ ）5． 代数系统<N,+>每个元素都有逆元。

（ ）装 订 线 内 不 要 答 题自觉遵 守 考 试 规 则，诚 信 考 试，绝 不作 弊2 / 26． 元素个数为4的格一定是布尔格。

（ ） 7． 一个图的生成子图必是唯一的。

（ ） 8． 存在割点的连通图其连通度必为1。

（ ）9． 对于两个图，如果结点数目相等，边数相等，度数相等的结点数目也相等，则这 两个图同构。

（ ）10．在任何有向图中，所有节点的入度之和等于所有节点的出度之和。

（ ） 三、解答题（50分，每题10分）1.请画出两个含有5个元素的非分配格。

2.写出下图的邻接矩阵，并求出可达性矩阵。

3.下面各图中，哪些可以一笔画？哪些可以从任一点一笔画？（a ） (b) (c) 4．判断所给的图G 是否为汉密尔顿图，如果是，则给出汗密尔顿回路，否则证明其不是汉密尔顿图。