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?