自考 离散数学教材课后题第五章答案

千里之行，始于足下。第2页/共2页精品文档推荐自考离散数学教材课后题第五章答案5.1习题参考答案

1、设无向图G有16条边，有3个4度结点，4个3度结点，其余结点的度数均小于3，咨询：G中至少有几个结点。

阮允准同学提供答案:

解：设度数小于3的结点有x个，则有

3×4＋4×3＋2x≥2×16

解得：x≥4

因此度数小于3的结点至少有4个

因此G至少有11个结点

2、设无向图G有9个结点，每个结点的度数别是5算是6，证明：G中至少有5个6度结点或至少有6个5度结点。

阮允准同学答案：

证明：由题意可知：度数为5的结点数只能是0,2，4,6，8。

若度数为5的结点数为0,2，4个，则度数为6的结点数为9，7,5个结论成立。

若度数为5的结点数为6,8个，结论显然成立。

由上可知，G中至少有5个6度点或至少有6个5度点。

3、证明：简单图的最大度小于结点数。

阮同学以为题中应指定是无向简单图.

晓津证明如下：设简单图有n个结点，某结点的度为最大度，因为简单图任一结点没有平行边，而任一结点的的边必连有另一结点，则其最多有n-1条边与其他结点相连，所以其度数最多惟独n-1条，小于结点数n.

4、设图G有n个结点，n+1条边，证明：G中至少有一具结点度数≥3。

阮同学给出证明如下：

证明：设G中所有结点的度数都小于3，即每个结点度数都小于等于2，则所有结点度数之和小于等于2n，因此G的边数必小于等于n，这和已知G有n+1条边相矛盾。因此结论成立。

5、试证明下图中两个图别同构。

晓津证明：同构的充要条件是两图的结点和边分不存在一一对应且保持关联关系。我们能够看出，(a)图和(b)图中都有一具三度结点，(a)图中三度结点的某条边关联着两个一度结点和一具二度结点，而(b)图中三度结点关联着两个二度结点和一具一度结点，所以可断定二图别是同构的。

6、画出所有5个结点3条边，以及5个结点7条边的简单图。

解：如下图所示：(晓津与阮同学答案一致)

7、证明：下图中的图是同构的。

证明如下：

在两图中我们能够看到有

a→e,b→h,c→f,d→g

两图中存在结点与边的一一对应关系，并保持关联关系。

8、证明：下面两图是同构的。

阮同学给出证明如下：

证明：找出对应关系：aq,br,cs,dt,eu,

fv,gw,hx

9、证明：三次正则图必有偶数个结点。

阮同学证明如下：

由题意可知每个结点度数基本上3度，即每个结点均为奇结点，依照有偶数个奇结点可知，三次正则图必有偶数个奇结点。

5.2习题参考答案

1、给定图G，如下图所示，求出G中从A到F的所有初级路。

解：从A到F的初级路有：

ABCF、ABEF、ADEF、ABECF、ABCEF、ADECF、ADEBCF

2、给定图G，如下图所示，找到G中从v2动身的所有初级回路。

晓津以为图中少了一具箭头：从V1到V2有一箭头。

从V2动身的初级回路有：V2V4V1V2、V2V3V4V1V2.

3、设G为无向连通图，有n个结点，这么G中至少有几条边？为啥？对有向图怎么？

解：若G为无向连通图，有n个结点，则G中至少有n-1条边。因为在n个结点的图中，任取一具结点为起始点，若要连通其他每个结点，则其他每个结点至少应有1度,此结点则有n-1度。所以总的度数至少为2n-2度，而度数为边的2倍，可算得边数为n-1.

关于有向图，若是弱连通，则与无向图一样至少为n-1,若是单侧连通也是这样，而强连通边数至少为n。(此题依照阮允准同学的答案更正)

4、设V'和E'分不为无向连通图G的点割集和边割集，G-E'的连通分支数一定是多少？G-V'的连通分支数也是定数吗?

解：

G-E'的连通分支数一定是2，而G-V'的连通分支数就别是定数了。有也许大于2.

5、设有七人a,b,c,d,e,f,g,已知：a会说英语，b会说汉语和英语，c会说英语、意大利语和俄语，d会说日语和汉语,e会说德语和意大利语，f会说法语、日语和俄语，g会说法语和德语，试咨询这七人间能够任意交谈吗？

答：能够。设七个人为图中的7个结点，以他们之间有共同语言为条件画边，能够看出，七个人的结点在图中是连通的，所以这七个人间能够经过相互翻译任意交谈。

6、一具有向图是强连通的，当且仅当G中有一具回路，它至少包含每个结点一次。

证明如下：

必要性：假如图中的任何一具回路都别能包含所有结点,则可知未被包含在回路内的结点别能与其他结点中的某一结点连通。这与本图是强连通的相矛盾。所以必有如此一具路它至少包含每个结点一次。

充分性：当G中有一具回路，它至少包含每个结点一次时，能够懂，任一结点可达其他所有结点，所以它是强连通的。

7、若有简单图至多有2n个结点，每个结点度数至少为n，G是连通图。

又若简单图G至多有2n个结点，每个结点度数至少为n-1，这么G是连通图吗？为啥？

答：G别再是连通图，假若n=1时，G中至多可有2个结点，而每个结点度数至少能够为0，显然这两个结点别能连通。

以下是阮同学的答案：

办法一：设v1、v2是那个简单图的任意两个结点，由已知可得，v1、v2的度数至少为n，

（1）若v1、v2之间有边，则显然v1、v2是连通的。

（2）若v1、v2无边，则v1和剩下的结点中的n个结点有边相连，v2也和剩下的结点中的n个结点有边相连。因为剩下的结点最多惟独2n-2个，由抽屉原理可得，至少存在一具结点，它和v1、v2都有边相连，此刻v1和v2也是连通的。

由（1）（2）可知，结论成立

办法二：显然那个图中任意的一对结点的度数之和大于等于2n，因此那个图是汉密尔顿图，因此那个图是连通的。

8、简单图G有n个结点，e条边，设e>0.5(n-1)(n-2),证明：G是连通的。

证明如下：n个结点的简单无向图，连通的最低条件是有n-1条边。而

e>0.5(n-1)(n-2)

可得e≥n-1，所以G是连通的。

上面的答案是错误的，阮允准同学纠正如下：因为一具连通图至少要有n-1条边，但并别是讲至少有n-1条边的图一定是连通图。同时容易验证那个结论别成立。

证明如下：

在图G中，它的结点数为n，设v是G中任一结点，若把v去掉后，其它n-1结点，每个结点度数最多有n-1度，所以n-1个结点之间最多惟独0.5（n-1)(n-2)条边，而e＞0.5(n-1)(n-2),因此至少有一条边连接v和其它结点。

下面我用数学归纳法进一步证明：

（1）容易证明当n=1,2时，结论成立

（2）假设当n=k时，结论成立，即若e＞0.5（k-1)(k-2)时结论成立

（3）当n=k+1时，若此刻每个结点度数为k，则结论显然成立，否则必存在一具结点v度数至多惟独k-1度，即那个结点最多惟独k-1条边和它相连。因为此刻总的边数e>0.5k(k-1),则其它k个结点之间的边数e'＞

0.5k(k-1)-(k-1)=0.5(k-1)(k-2)。依照归纳假设，显然这k个结点之间是连通的，而依照上面我们懂，至少有一条边使v和其它结点相连，因此此刻那个图是连通的。

依照（1）（2）（3）可知结论成立。

5.3习题参考答案

1、设图G=,V={v1,v2,v3,v4}的邻接矩阵

则v1的入度deg(v1)是多少？v4的出度deg(v4)是多少？从v1到v4长度为2的路有几条？

解：1、v1的入度是3.

v4的出度是1，

因为

A2(G)=2011

22011112

0101

因此从v1到v4长度为2的路有1条。

2、有向图G如图所示，求G中长度为4的路径总数，并指出其中有多少条是回路。v3到v4的迹有几条。

答：长度为4的路径总数为15条，其中3条

是回路。从v3到v4的迹有3条。

3、给定图G如下图求：a)给出G的邻接矩阵

b)求各结点的出、入度

c)求从结点c动身长度为3的所有回路

A(G

)=010110111100

1000

解:邻接矩阵如图：(按字母顺序)

M（G）＝00100

10100

00011

00110

01000

a的出度是1，入度为1

b的出度是1，入度为1

c的出度是2，入度为3

d的出度是2，入度为2

e的出度是1，入度为1

晓津补充一下：出度就能够数该行的非零个数，入度则可数该列的非

零个数

从结点c动身长度为3的回路有：c-e-b-c,c-d-d-c

4、给定G如图所示，

a)写出邻接矩阵

b)G中长度为4的路有几条？

c)G中有几条回路？

解：(晓津有疑咨询，v2、v3间没有箭头，则此图有错，暂且明白为双向连通吧)

a)M（G）＝00001

10100

01001

10100

01010

b)有52条

c)无数条

(看到这个地方，晓津认为v2、v3间的箭头应向右更符合其本意，因为图中有某种对应的关系。)

5、试用矩阵法推断有向图。

G=,}连通性。

答：别连通

晓津补充一下：原矩阵为：

M(G)=1001000001010000

由此矩阵得到的路径矩阵为：

M4(G)=1001000001010000

能够发觉图中些结点间没有路径存在。

6、求出下图所示图G的邻接矩阵、可达矩阵，找出从v2到v3长度为3的初级路，并计算出A2,A3举行验证。

解：邻接矩阵为：

M(G)=0101001101010100

其余答案略，用阮同学的话讲算是："太烦恼了，自个儿算一算吧":)

7、设图G中的边满脚W(G-e)>W(G),称为e为G的割边（桥）。

证明：e是割边，当且仅当e别包含在G的任一回路中。

证明：

必要性：设e是G某一连通分支的一条边。

假设e包含在G的某一回路中，若把e去掉