北师17春《图论》离线作业答案
《图论》作业
本课程作业由两部分组成。第一部分为“客观题部分”，由5个选择题组成，每题1分，共5分。第二部分为“主观题部分”，由解答题组成，共25分。作业总分30分，将作为平时成绩记入课程总成绩。
客观题部分：
一、选择题（每题1分，共5题）
下图
● ●
● ●
中顶点的最大度数为 ()
A. 1 B. 2 C. 3 D. 4
2. 完全2部分图Km,n的边数和ε(Km,n)=()。
A. m+n B. max{m,n} C.m+n+1 D.mn
3. 下面图() 是树。
A. ● ● B. ● C. ● ● D. ● ●
●
● ● ● ● ● ● ● ●
面图（）是欧拉图。
A. ● ● B. ● ● C. ● ● D. ●
● ●
● ● ● ● ● ● ●
下面图 （）不是哈密尔顿图。
A. ● ● B. ● ● C. ● ● D.● ●
● ● ●
● ● ● ● ● ● ● ●
主观题部分：
解答题（每题5分，共5题）
1、由匹配 开始，用最大匹配的算法找出下图的一个最大匹配。
2、将延迟认可算法应用于下面的优先秩评定矩阵找出它的一个稳定的完备婚姻。
用BF－算法构造下图中根值于u的BFS－树
4、找下表所确定的交易商问题的核心分配。
5、设e是图G的一条边。证明
转载请注明出处www.ap5u.com
页:
[1]