77范文网 - 专业文章范例文档资料分享平台

离散数学习题解答第6部分(图论)(2)

来源:网络收集 时间:2020-04-17 下载这篇文档 手机版
说明:文章内容仅供预览,部分内容可能不全,需要完整文档或者需要复制内容,请下载word后使用。下载word有问题请添加微信号:或QQ: 处理(尽可能给您提供完整文档),感谢您的支持与谅解。点击这里给我发消息

n1(n1?1)n2(n2?1)n(n?1)????kk222

(n?1)(n1?1)(n?1)(n2?1)(n?1)(nk?1)?????222?=(n-1)·== ≤

1·((n1-1)+(n2-1)+?+(nk-1)) 21(n-1)((n1+n2+?+nk)-k) 21(n-1)(n-k) 21(n-1)(n-2) (k≥2) 21(n-1)(n-2)矛盾。 2这与已知M>

因此假设错误,G是连通图。

11.设G=(V,E)是无向完全图(无自环),|V|=n

1) 求G中有多少初级圈?

2) 设e∈E,求含有e的初级圈有几个?

3) 设u,v∈V,u≠v,求由u到v有几条初级路?

[解] 1)在一个有n个结点的无向完全图(无自环)中,构成一个初级圈,至少需3个结点,至多有n个结点,故G中初级圈的个数为

2!?n?3!?n?(n?2)!?n?(n?1)!?n?????????????????????2?3?2?4?2?n?2?2?n??1??Akn(个)k?32列(除2);长为k的圈排列可形成k个线排列(除k)。 2)含有边e的初级圈为

n?2k?0n

即将从n个结点中选出的k个结点进行排列,然后除去重复:每个排列的倒排

A1n?2?A2n?2???An?2n?2??Akn?2(个)

即,从u到v的直接边(完全图,该边存在)是一条;再将该直接边加到其它初级路里,就构成了含边(u,v)的初级圈,从而由2)可得如上数值。

6

12.试证在简单有向图中

1) 每个结点及每条边都属于且只属于一个弱分图; 2) 每个结点及每条边都至少属于一个单向分图。

[证] 1)有向图中的弱连通性建立了G中结点集合V上的等价关系,因此构成了V上的一个划分;同时,还建立了边集上的一个划分。因此,每一个弱连通支就是一个“划分块”。设G1,G2,?,Gk为G的所有弱连通分图,则有:

V(G)=V(G1)∪V(G2)?∪V(Gk) E(G)=E(G1)∪E(G2)?∪E(Gk)

并且,当i≠j时,V(Gi)∩V(Gj)=φ,E(Gi)∩E(Gj)=φ。因此,每个结点及每条边都属于且只属于一个弱图。

2)有向图中的单向连通性建立了G中结点集合V上的一个相容关系,因此构成了V上的一个覆盖;同时,还建立了边集上的一个覆盖;每一个单向分图就是一个“覆盖快”。设G1,G2?,Gk为G的所有单向分图,则有

V(G)=V(G1)∪V(G2)∪?∪V(Gk) E(G)=E(G1)∪E(G2)∪?∪E(Gk) 因此,每个结点及每条边都至少属于一个单向分图。

13.试用有向图描述出下述问题的解法路径:某人m带一条狗d,一只猫c和一只

兔子r过河,没有船,他每次游过河时只能带一只动物,当没有人管理时狗和兔子不能相处,猫和兔子也不能相处。在这些条件的约束下,他怎样才能将这三只动物从北岸带往南岸?

[解] 将人,狗,兔中任意几种在一起的情况看作是一种状态;一个布局是一个二元

组,由两个互补的状态构成,二元组的前者表示河北岸的状态,后者表示河南岸的状态。初始布局为(pdcr,φ),终止布局为(φ,pdcr)安全布局有十种,不安全布局有六种,它们是:

(dr,pc),(cr,pd),(dcr,p), (pc,dr),(pd,cr),(p,dcr)。 按题意构造有向图,其解法路径如下: φ pdcr, pcr,d pdc,r dc,pr c,pdr dpc,r pdr,c pr,dc φ,pdcr 14.求下列图中的所有强连通支,单向连通支,弱连通支。

7

v1 v2 v3 v4 v5

v6

v10

[解] 1)有六个强连通支,它们是:

G1=({v1,v2,v3,v9,v10},{(v1,v2),(v2,v9),(v9,v10),(v10,v1),(v2,v3),

(v3,v9)})

G2=({v4},φ),G3=({v8},φ),G4=({v7},φ), G5=({v5},{(v5,v5)}),G6=({v6},φ)。

2)有四个单向连通支,它们是:

G1=({v1,v2,v3,v4,v9,v10},{(v1,v2),(v2,v9),(v9,v10),(v10,v1),(v2,

v3),(v3,v9),(v3,v4)}),

G2=({v4,v7,v8},{(v7,v8),(v8,v4)}), G3=({v5},{v5,v5}),G4=({v6},φ) 3)有三个弱连通支,它们是

G1=({v1,v2,v3,v4,v7,v8,v9,v10},{(v1,v2),(v2,v9),(v9,v10),(v10,

v1),(v2,v3),(v3,v9),(v3,v4),(v7,v8),(v8,v4)}) G2=({v5},{(v5,v5)}),G3=({v6,φ})

15.给出有向图如下所示: 1) 求它的邻接矩阵A;

2) 求A2,A3,A4,指出从v1到v4长度为

1,2,3,4的路径各有几条?

3) 求AT,ATA,AAT,说明ATA和AAT

中元素(2,3)和(2,2)的意义;

4) 求A(2),A

(3)

v9 v8 v7

v1

v2 v4 ,A

(4)

及可过矩陈R;

v3

5) 求出强度通支。 [解] 1)它的邻接矩阵

8

?0??0A??0??0?2)?0??0A2??0??0??0??03A??0??0??0??0A4??0??0?101??011?101??100??101??0??011??0101??0???100???0111??0??201??0111??0???011???0212??0??122??0212??0???201???0101??0??011??0?101??0???100???0101??0??011??0?101??0???100???0101??0??011??0???1010???100???0111??201?111??011??212??122?212??201??323??

413?323??122??从v1到v4长度为1的路有1条,是(v1,v4);

从v1到v4长度为2的路有1条,是(v1,v2),(v2,v4); 从v1到v4长度为3的路有2条,是: (v1,v2),(v2,v8),(v3,v4); (v1,v4),(v4,v2),(v2,v4)。 从v1到v4长度为4的路有3条,是: (v1,v2),(v2,v3),(v3,v2),(v2,v4); (v1,v2),(v2,v4),(v4,v2),(v2,v4); (v1,v4),(v4,v2),(v2,v3),(v3,v4); 3)

?0?T

A=?1?0??1?001101010??1? 0??0?? 9

?0000??0????1011??0ATA??0100??0????1110??0???0101?00?0011?10AAT?0101?01?0100??11101101011??0??11??0?01??0???00???00??21??1??12?0??21???0???1000302211100110??2?1??3?? 1??0?0??1??在ATA中,元素(2,3)=0的意义是:

不存在着这样的结点,从它发出的边同时终止于结点v2及v3;

在ATA中,元素(2,3)=3的意义是:deg(v2)=3,即结点v2的入度为3。

在AAT中,元素(2,3)=1的意义是:存在着一个结点,v4从v2及v3发出的边同时终之于它;

在AAT中,元素(2,2)=2的意义是:deg(v2)=2,即结点v2的出度为2。 4)

A(2)?0?0???0??0?0?0???0??0?0?0???0??010111110010011111??0?01???1??0??0??01??0?01???1??0??1??0101110111011010001010101111110

A(3)1??0?01????1??0??0??01??0?01????1??0??0??0?0?0??0??011101111111010111?1??1??1?1?1??1??1?A(4)111??0?0111???111??0??111??0R?A?A(2)?A(4)?0?0???0??01?1???1??0?11?11??11??11?111?111??111??111?

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读,免费范文网,提供经典小说综合文库离散数学习题解答第6部分(图论)(2)在线全文阅读。

离散数学习题解答第6部分(图论)(2).doc 将本文的Word文档下载到电脑,方便复制、编辑、收藏和打印 下载失败或者文档不完整,请联系客服人员解决!
本文链接:https://www.77cn.com.cn/wenku/zonghe/988498.html(转载请注明文章来源)
Copyright © 2008-2022 免费范文网 版权所有
声明 :本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。
客服QQ: 邮箱:tiandhx2@hotmail.com
苏ICP备16052595号-18
× 注册会员免费下载(下载后可以自由复制和排版)
注册会员下载
全站内容免费自由复制
注册会员下载
全站内容免费自由复制
注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信: QQ: