当前位置：文档之家› 张清华图论课后题答案

张清华图论课后题答案

第1章图论预备知识

1.1

解：(1) p={φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}

(2) p={,{a},{{b,c}},{a,{b,c}}} (3) p={,{}}

(4) p={,{},{{}},{,{}}}

(5)p={,{{a,b}},{{a,a,b}},{{a,b,a,b}},{{a,b},{a,a,b}},{{a,b},{a,b,a,b}},{{a,b},{a,a,b},{a,b,a,b}}} 1.2 解：(1) 真 (2) 假 (3)假 (4)假 1.3 解：(1) 不成立，A={1} B={1,2} C={2} (2) 不成立，A={1} B={1,2} C={1,3}

1.4 证明：设(x,y)∈(A ∩B)X(C ∩D) 说明x ∈A ∩B,y ∈C ∩D 由于 x ∈A,y ∈C 所以 (x,y) ∈A X C 由于x ∈B,y ∈D 所以 (x,y) ∈B X D 所以 (x,y) ∈（A X C ）∩（B X D ）反过来，如果（x,y ）∈(A X C) ∩（B X D ）由于 (x,y) ∈（A X C ）所以 x ∈A,y ∈C 由于 (x,y) ∈（B X D ）所以x ∈B,y ∈D 所以x ∈(A ∩B) y ∈(C ∩D) 所以 (x,y) ∈(A ∩B)X(C ∩D)

所以(A ∩B)X(C ∩D)= (A X C) ∩（B X D ） 1.5 解：Hasse 图

φφφφφφφφφ

极大元{9,24,10,7} 极小元{3,2,5,7} 最大元{24} 最小元{2}

1.6 解

(2)关系图为：

(3)不存在最大元，最小元为{2}

1.7 解：(1)R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>} (2)略

(3)I A ?R 故R 是自反的。 <1,2>∈R <2,3>R 但是<1,3>

?R 故不满足传递性

1.8 解：(1) 不成立 A={1} B={2} C={3} D={4} 则左式={<1,3>，<1,4>,<2,3>,<2,4>} 右式={<1,3>,<2,4>}

(2) 不成立 A={1,3} B={1} C={2,4} D={2} 则左式={<3,4>}

右式={<1,4>,<3,2>,<3,4>}

(3) 不成立 A={1} B={2} C={3} D={4} 则左式={<1,3>,<1,4>,<2,3>,<2,4>} 右式={<1,3>,<2,4>} (4) 成立证明：设

∈(A-B)X C ?x (A-B)∧ y C

?x A ∧x B ∧ y C A X C ∧

B X

C (A X C)-(B XC)

故得（A-B ）X C=（A X C ）-（B X C ）

∈∈∈∈∈∈?∈∈?∈

1.9略

1.10略

1.11解：A为n个元素的优先级和，A上有2n2 个不同的二元关系，理由为：设A，B为集合，AXB的任何子集所定义的二元关系称作从A到B的二元关系，特别当A=B时，称作A上的二元关系，若|A|=n，则|AXA|=n2，那么A上共有2n2个不同的二元关系。

1.12略

1.13解：1)真.由于R1和R2和R2都是自反的,因而对任何,都有(x,x)∈R1,(x,x)∈R

2.因此,对任何x∈A,都有(x,x)∈R1R2.所以R1R2是自反的。

2)假.令A={a,b},R1={(a,b)},R2={b,a}.那么R1R2={(a,a)},它就不是A上的反自反关系.

3)假.令A={a,b,c},R1={(a,b),(b,a)},R2={(b,c),(c,b)}.那末R1R2={(a,c)},就不是A的对称关系.

4)假.令A={a,b,c,d},R1={(a,c),(b,c)},R2={(c,b),(d,a)}易证R1,R2都是反对称关系.但是R1R2={(a,b),(b,a)}就不是A上的反对称关系.

5)假.令A={a,b,c},R1={(a,c),(b,a),(b,c)},R2={(c,b),(a,c),(a,b)},易证R1和R2都是传递关∈系,但R1R2={(a,b),(b,b),(b,c)}就不是A上的传递关系.

1.14证明：由任意的a，存在一个b，使得∈R,由对称性所以∈R,由传递性∈R,所以R是等价关系。

1.15证明：①x∈A，∈R,∈S→∈R∩S，所以R∩S有自反性；

②x,y∈A,因为R,S是反对称的，∈R∩S∧∈R∩S(∈R∧∈S) ∧(∈R∧∈S)(∈R∧∈R) ∧(∈S∧∈S)x=y∧y=xx=y

所以，R∩S有反对称性。

③x,y,z∈A,因为R,S是传递的，

∈R∩S∧∈R∩S∈R∧∈S∧∈R∧∈S∈R∧∈R∧∈S∧∈S∈R∧∈S∈R∩S

所以，R∩S有传递性。

所以R∩S也是A上的偏序关系。

1.16解：

r(R)={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<1,2>,<2,3>,<2,5>,<3,4>,<4,3>,<5,5>}

s(R)={<1,2>,<2,1>,<2,3>,<3,2>,<2,5>,<5,2>,<3,4>,<4,3>,<5,5>}

t(R)={<1,2>,<1,3>,<1,4>,<1,5>,<2,3>,<2,4>,<2,5>,<3,3>,<3,4>,<4,3>,<4,4>,<5,5>}

1.17 (1)证明：①对任意a,b,a+b=a+b,故得(a,b)R(a,b),关系R具有自反性;

②如果(a,b)R(c,d),则a+d=b+c,c+b=d+a,故得(c,d)R(a,b),

关系R具有对称性;

③如果(a,b)R(c,d),(c,d)R(e,f),则a+d=b+c,c+f=d+e,

故得a+f=b+e,(a,b)R(e,f),关系R具有传递性;

于是关系R是等价关系.

1.18略

1.19略

1.20解：(1) 单射

(2) 满射

(3) 既不是单射，也不是满射

(4) 满射

(5) 双射

1.21解：(1) O(n3)

(2) O(n5)

(3) O(n3n!)

第2章图

2.1

解：

(1)

(2)

2.2 解：

构成无向图的度序列：(1)、(2)、(3)、(4)、(6) 构成无向简单图的度序列：(2)、(3)、(4) 2.3

解：补图为：

2.4

a:出度为3、入度为1 b:出度为2、入度为2 c:出度为2、入度为3 d:出度为2、入度为3 e:出度为2、入度为2

a:出度为3、入度为1 b:出度为1、入度为2 c:出度为3、入度为3 d:出度为3、入度为2 e:出度为0、入度为3

设图G 中结点数为n,则有3x4+3x(n-3)=2x12.求得n=7,即图G 有7个结点. 2.5

证明将习图2.2的两图顶点标号为如下的(a)与(b)图

作映射f : f(v i )→u i (1≤ i ≤ 10)

容易证明，对?v i v j ∈E((a)),有f(v i v j )=u i u j ∈E((b)) (1≤ i ≤ 10, 1≤j ≤ 10 ) 由图的同构定义知，两个图是同构的。 2.6

解：同构对应关系：a —8、b —7、c —4、d —9、e —5、f —6、g —1、h —2、i —10、j —3. 2.7

证：设在一有向完全图G 中，边数为n.则可知 .即所有结点的入度和等于所有节点的出度和，即所有结点的入度的平方和等于所有节点的出度的平方和。 2.8

(a)

v 2

u 4 u (b)

(1)

(2)

2.9

证明：用反证法。

设无向图G 只有两个奇点u,v ，若u,v 不连通，即它们之间没任何通路，则G 至少有两个连通分支G1,G2，且u,v 分别属于G1和G2，于是G1和G2中各有一个奇度结点，与握手定理矛盾，因此u,v 必连通。 2.10

解：点割集为：{v1，v3}、{v4}、{v6}

割点为：v4、v6 2.11

解：强连通图：(a ）

单相连通图：（b ）（c ）（d ）弱连通图：（a ）（b ）（c ）（d ） 2.12

证明:设v0v1…vk为G中一条最长路，则v0的邻接顶点一定在该路上，否则，与假设矛盾。现取与v0相邻的脚标最大者，记为l，则l ,于是得圈v0v1v2…vlv0,该圈长为l+1，显然不小于δ+1。

2.13

证明：证其逆否命题：e不是割边当且仅当e含在G的某个圈中。

必要性：设e=xy不是割边。假定e位于G的某个连通分支G1中，则G1-e仍连通。故在G1_e中有(x,y)路P，P+e便构成G1中一个含有e的圈。

充分性：设e含在G的某个圈C中，而C含于某连通分支G1中，则G1-e仍连通。故W(G-e)=W(G)，这说明e不是割边,证毕。

2.14

证明：用数学归纳法证明：

（1）n=1时，G为平凡图，显然G连通。

（2）n=2时，此时G为K2，当然连通。

（3）假设当n=k（k≥2）时，结论成立。

当n=k+1时，若此时每个结点度数为k，则结论显然成立，否则必存在一个结点v度数至多只有k-1度，即这个结点最多只有k-1条边和它相连。因为此时总的边数,则其它k个结点之间的边数

。根据归纳假设，显然这k个结点之间是连通的，而根据上面我们知道，至少有一条边使v和其它结点相连，所以此时这个图是连通的,结论成立。

2.15

证明：

（1）因为G连通，且G无割边，所以任意两个结点u,v，都存在简单道路p=u…wv.又因为G无割边，所以，删除边wv后，子图依然连通，即w,v存在简单道路,以此类推，可以找到一条和p每条边都不相同的p’’=v…u,这样p和p’’就

构成了一条回路。

（2）因为G中任意两个结点都位于同一回路中，所以任意结点u,和任意边e的两个端点v1,v2都分别在两个回路C1，C2中，如果C1=C2=u…v1…v2…u,那么将回路中v1…v2,用v1v2=e替换，就得到新的新的回路，并满足要求。如果C1≠C2，C1=u…v1…u,C2=u…v2…u,那么构成新的道路P=u…v1…u…v2…u,在其中将重复边剔出掉，得到新的回路C3，其中包含v1,v2结点，可以将回路中v1…v2用v1v2=e替换，就得到新的新的回路，并满足要求。

（3）对任意两条边e1,e2其端点分别为u1,u2,v1,v2。根据（2）存在回路C1 = u1…v1v2…u1,C2=u2…v1v2…u2。那么可以形成新的闭道路P=u1…v1v2…u2…

v1v2…u1,在其中将重复边剔出到，得到新的回路C3，其中包含e2和u1,u2结点，可以将回路中u1…u2用u1u2=e1替换，就得到新的新的回路，包含e1,e2,满足要求。

(4)因为任意两条边都在同一回路中，所以不存在割边。假设边e是割边，那么删除此边，图不连通，分支中的任何一对不在同一分支中的边，不能构成回路，与条件矛盾。所以，G中无割边。

2.16

解：(1)deg(v1)=2、deg(v2)=3

(2)否(3) 4

(4)略

2.17

解：(1)A=

(2)===

V1到V4长度为1、2、3、4的路各有1、1、2、3条。

2.18

解：无向图G:

可达矩阵P = 有可达矩阵可知改图为强连通图。

2.19

解：

(1)邻接矩阵A =

(2)G中长度为3的通路有23条，其中有7条为回路。

(3)图G为强连通图

2.20

解：邻接矩阵A =

关联矩阵M(G) =

2.21

解：(1)当r=1时，没有长度大于等于1的圈。

当2≤r≤s时，有长度为4,6,…,2r的圈，它们都是偶圈，因而非同构的圈共有r-1种。

(2)至多有r个顶点彼此不相邻。

(3)至多有r条边彼此不相邻。

(4)k=λ= r

2.22

证明：反证法。

若存在某个具有奇数个面，且每个面均有奇数条棱的多面体V，不妨设V有r(r为奇数)个面，设为R1,R2,…,Rr，S1,S2,…,Sr分别为它们的棱数，均为奇数。作无向图G如下：在V的每个面中放一个顶点vi，i=1,2,…,r, 且两个面Ri与Rj 有公共面就连边。若存在这样的无向图G，则d(vi)均为奇数Si，由握手定理得

为边数

但因r,Si(i=1,2,…,n)均为奇数，上面等式不可能成立。故不存在这样的无向图G，从而也不存在满足要求的多面体。

2.23

解：设G是n阶m条边的自补图,即G为n阶m条边的简单图,且G?G 。

于是，G 的边数m’=m，且m+m'=2m=n(n-1)/2。于是n(n-1)=4m，因而n=4k，或n-1=4k，k为正整数。

2.24

证明：

为偶数(n 为奇数)。

于是，若为奇数，必有d G (v)也为奇数。

故

与G 中奇度顶点个数相等。

2.25

解:都可以实现，如下图

2.26

解：(1)错误、(2)正确、(3)正确 2.27 略 2.28

解：无向完全图K n 当n ≥3且n 为奇数时才是欧拉图。当n>3且n 为偶数时存在欧拉路而不存在欧拉回路。

2.29 略 2.30 略 2.31 略

第3章树与最短路径

3.1

(1)

(2)

该树的结点个数n=5，故边数m=n-1=4,因为1

2deg(v )n

i i m ==∑，所以5个结点分配

的度数为8，由于树是简单连通图，知1deg(v)4≤≤，则该树的度数序列必是下列情况之一， (1)1，1，2，2，2 (2)1，1，1，2，3 (3)1，1，1，1，4

这些度数序列对应的简单树为

3.2

该树的结点个数为v ，则边数1m v =-，又因为1deg(v )22(1)n

i i m v ===-∑，所以

可知一棵树的结点个数之和为2(1)v -。 3.3

设有n 个一度结点，则结点个数为=3+5+8+n ，边数为=3+5+8+n-1,则

2353842(358n)n ?+?+?+=+++.可得n=23.

3.4

设有n 个一度结点，23231,:n 23k k n n n n n n kn +++

+-++++边数：度数则：

23232(1)n 23k k n n n n n n kn ++++-=++++

342(k 2)2k n n n n =+++-+

3.5

反证法。假设没有结点度数大于等于3的结点，则只有度为1的结点3个和度为2的结点n 个。边数：3+n-1，度数：3+2n.所以2（3+n-1）=3+2n 。等式左边为偶数，右边为奇数，相互矛盾，假设不成立。所以至少有一个结点度数大于等于3.

3.6 设度为2,3,

k 的结点个数为23,,

k n n n 则23232(2++++-1)2+2+3+

k k n n n n n kn =

则342(k 2)n 0k n n ++

+-=由于23,,

0k n n n ≥，故23,,

k n n n 全为0.

当20n =时，只有两个度为1的结点，所以T 是一条直线。

当20n ≠时，有两个度为1的结点，其他结点度数都为2，T 仍为一条直线。综上T 是一条直线。 3.7 =>若12

()n d d d 为度数序列,则该树的结点个数为n ，边数为n-1,所以

deg(v )2(n 1)n

n i d

d d ==++

+=-∑

<=若122(n 1)n d d d +++=-，则该树的结点为n ，且结点度数依次为12n d d d 。

即12()n d d d 是一棵树的度数序列。

3.8证明

假设1v 中没有树叶，则||2)deg(11v v ≥， 21v v 是二部图结点分类，且1v 中顶点的出度最少为2，则||2)deg(21v v ≤，可得||||12v v ≥与题中给的||||12v v ≤相矛

盾。所以1v 中至少有一片树叶。 3.9

T 是一棵树，则T 中任意两个结点之间有且仅有一条路，所以T 中任意两点仅有唯一的简单通路，反之亦成立。 3.10

Kruskal 算法可求得如下最小生成树: 4

3.11

v 且，所以结点v的关联便只有一条。又因为证明:因为G为连通图V deg(v)=1

G的任何一棵生成树T必为G的生成子图且连通，即T包含G的所有结点且连通，而v的关联边只有e一条边，故e一定是任何一棵树的枝。

3.12

证明：如果简单连通图G无回路，则G本身就是生成树。即G的任何一条边都可以是某一生成树的枝。若G中有回路，则去掉任意一条边，则图仍连通，若图中仍有回路，重复上述过程知道图中无回路为止。去掉的边不一样，则得到的生成树不一样，又因为去边是在回路中任意去掉的一条边，所以G中任一条边都可以是某一生成树的枝。

3.13

正则二叉树为为完全二叉树且所有叶结点在同一层。因为完全二叉树的分支节点的出度都是2，则可知除根节点外，其他每层上的结点个数都为偶数，故一棵正则二叉树必有奇数个结点。

3.14

3.15

3.16

0u 到各结点的最短路径为： 01u u 1l →= 02

u u 2l →=

023u u u 3l →→= 0234u u u u 6l →→→= 0235u u u u 9l →→→=

u u 4l →=

067u u u 6

l →→=

3.17

5316156146136121v v v v v v v v v v v v v →→→→→→→→ 3

125

6124323

2v v v v v v v v v v v v →→→→→→→→

6354343v v v v v v v →→→→3

454v v v v →→565v v →

3.18

1367813v v v v v l →→→→= 3.19

解：图中有两个奇点E,F 。取一条连接EF 的路EGF ，添加重复边（E ，G ）和（G ，F ），经检验可得满足定理的条件，即为最优方案,其最优回路:DBACBEGEDFGFCD. 3.20

最邻近算法：

acedba 37 bdecab 37 cedbac 37 dbeacd 36 最短哈密顿回路为：dbeacd 最邻近插入法： aa aca acea acdea

abcdea acbdea acdbea acdeba 其权值分别为：52，40，36，43 最短哈密顿回路为：acdbea

第五章独立集、支配集与匹配 5.1

证明：?由G 是二部图可知，其子图H 也是二部图，显然二部图的顶点划分（X ，Y ）中的X ，Y 均是二部图的独立集，则有2

)

(})(),(max{)(H V H Y H X H ≥

≥α，其中)(H v 是子图H 的顶点数，)(H α是图H 的最大独立集中具有的点的数目。

? 反证法：若G 不是二部图，则G 含有奇圈H ，H 是G 的子图，但

)

(21)()(H v H v H <-=

α这与已知条件矛盾，故G 是二部图。 5.2

证明：?G 是二部图，则其子图H 也是二部图，因为)(2

)(H v H =α，故对子图H 有)(2

,)(2121H v v H v v ==

，则必有一个匹配关联G 中所有结点，故G 有一个完美匹配。

?G 有一个完美匹配，则子图H 也有完美匹配，故该匹配关联H 的所有结点，所以)(2

)(H v H =α。 5.3

(1)G 中极小支配集为{v1, v3}, {v2, v4, v5}，支配数2。 (2)G 中极小点覆盖集为{v1, v3}, {v2, v4, v5}，点覆盖数2。 (3)G 中极大点独立集为{v1, v3}, {v2, v4, v5}，点独立数3。 (4)G 中极大匹配为{a, c}, {a, f}, {b, d}, {b, f}, {e, c}, {e, d}，匹配数2。

(5)G 中极小边覆盖集为{a, b, f}, {a, e, c}, {b, e, d}, {d, c, e}, {d, f, b}, {c, f, a}，边覆盖数3。 5.4

证明：G 是二分图，并且0)(>G δ则βαθη+=+，又βη=，故θα=。 5.5

（a ）极小点覆盖{a,c,e,g},{b,c,d,e,g}{b,d,e,f}{b,c,d,f} 极大独立集{b,d,f}{a,f}{a,c,g}{a,e,g} 最小点覆盖{a,c,e,g}{b,d,e,f}{b,c,d,f} 最大独立集{b,d,f}{a,c,g}{a,e,g}

(b)极小点覆盖{b,c,e,f}{b,c,d,f}{b,c,d,e}{a,c,e,f}{a,c,d,e}{a,b,d,e} 极大独立集{a,d}{a,e}{a,f}{b,d}{b,f}{c,f}

最小点覆盖{b,c,e,f}{b,c,d,f}{b,c,d,e}{a,c,e,f}{a,c,d,e}{a,b,d,e} 最大独立集{a,d}{a,e}{a,f}{b,d}{b,f}{c,f} 5.6

2004图论复习题答案

图论复习题答案一、判断题，对打，错打 1．无向完全图是正则图。 () 2．零图是平凡图。() 3．连通图的补图是连通图.() 4．非连通图的补图是非连通图。() 5．若连通无向简单图G中无圈，则每条边都是割边。() 6．若无向简单图G是（n，m）图，并且m=n-1，则G是树。() 7．任何树都至少有2片树叶。() 8．任何无向图G都至少有一个生成树。() 9．非平凡树是二分图。() 10．所有树叶的级均相同的二元树是完全二元树。() 11．任何一个位置二元树的树叶都对应唯一一个前缀码。() 12． K是欧拉图也是哈密顿图。() 3,3 13．二分图的对偶图是欧拉图。() 14．平面图的对偶图是连通图。() 页脚内容1

15．设G*是平面图G的对偶图，则G*的面数等于G的顶点数。() 二、填空题 1．无向完全图K6有15条边。 2．有三个顶点的所有互不同构的简单无向图有4个。 3．设树T中有2个3度顶点和3个4度顶点，其余的顶点都是树叶，则T中有10片树叶。 4．若连通无向图G是（n，m）图，T是G的生成树，则基本割集有n-1个，基本圈有m-n+1个。 5．设连通无向图G有k个奇顶点，要使G变成欧拉图，在G中至少要加k/2条边。 6．连通无向图G是（n，m）图，若G是平面图，则G有m-n+2个面。三、解答题 1．有向图D如图1所示，利用D的邻接矩阵及其幂运算求解下列问题：（1）D中长度等于3的通路和回路各有多少条。（2）求D的可达性矩阵。（3）求D的强分图。解：（1） a b c d e 图1 页脚内容2

页脚内容3 M=????????????????000101000000001 010*******M 2=?? ? ? ??????? ?????010******* 000101000001000 M 3=????????????????10000 01000010000001010000M 4=??? ???? ? ??? ?????00010 01000 100000100000010 由M 3可知，D 中长度等于3的通路有5条，长度等于3的回路有3条。（2） I+M+M 2+M 3+M 4=????????????? ???100000100000100 0001000001 +??????????? ?? ???000101000000001 010******* +??????????? ?? ???010000001000010 1000001000 +??? ???? ? ??? ?? ???100000100001000 0001010000 + ????????????????00010 01000100000100000010 =??? ???? ???? ?? ???21020 1301011111 020******* D 的可达性矩阵为 R=B （I+M+M 2+M 3+M 4）=??? ???? ? ????? ???110101********* 1101011011 b c d e 图1

课后习题答案

第一章液压传动概述液压传动系统由哪几部分组成各组成部分的作用是什么解答：液压传动由以下四部分组成：（1）动力元件(液压泵)：它是把原动机输出的机械能转换成油液压力能的元件。作用:给液压系统提供压力油，是液压系统的心脏。（2）执行元件：包括液压缸和液压马达等。作用:把油液的压力能转换成机械能以驱动工作机构的元件。（3）控制元件：包括压力、方向、流量控制阀。作用:是对液压系统中油液的压力、流量和流动方向进行控制和调节的元件。（4）辅助元件：除上述三项以外的、液压系统中所需的其它装置。如油箱、滤油器、油管、管接头等。作用:保证液压系统有效工作，寿命长。第二章液压泵和液压马达要提高齿轮泵的压力需解决哪些关键问题通常都采用哪些措施解答：（1）困油现象：采取措施：在两端盖板上开卸荷槽。（2）径向不平衡力：采取措施：缩小压油口直径；增大扫膛处的径向间隙；过渡区连通；支撑上采用滚针轴承或滑动轴承。（3）齿轮泵的泄漏：采取措施：采用断面间隙自动补偿装置。齿轮泵的模数 mm m 4=，齿数9=z ，齿宽mm B 18=，在额定压力下，转速min 2000r n =时，泵的实际输出流量min 30L Q =，求泵的容积效率。解答：()() 2 2630 0.876.6~7 6.69418200010v t q q q zm bn η-= ===????? YB63型叶片泵的最高压力MPa P 3.6max =，叶片宽度mm B 24=，叶片厚度mm 25.2=δ，叶片数 12=Z ，叶片倾角?=13θ,定子曲线长径mm R 49=，短径mm r 43=，泵的容积效率9.0=v η，机械效率 90.0=m η，泵轴转速min 960r n =，试求：(1) 叶片泵的实际流量是多少(2)叶片泵的输出功率是多少解答：（1） ()()()()() 22 223 322cos 20.0490.04320.0490.0430.024120.0249600.9cos131.0210v R r q R r bz Bn m s πηφπ-??=--???? ?-?? =--?????????? =? （2） 633 6.310 1.0210 6.4210N pq -==???=?出斜盘式轴向柱塞泵的斜盘倾角?=20β，柱塞直径mm d 22=，柱塞分布圆直径mm D 68=，柱塞数7=z ，机械效率90.0=m η，容积效率97.0=v η，泵转速min 1450r n =，泵输出压力MPa p 28=，试计算：(1)平

图论张先迪李正良课后习题答案

习题一作者---寒江独钓 1.证明：在n 阶连通图中 (1) 至少有n-1条边； (2) 如果边数大于n-1，则至少有一条闭迹； (3) 如果恰有n-1条边，则至少有一个奇度点。证明: (1) 若G 中没有1度顶点，由握手定理： ()2()21v V G m d v n m n m n ∈= ≥?≥?>-∑ 若G 中有1度顶点u ，对G 的顶点数作数学归纳。当n=2时，结论显然；设结论对n=k 时成立。当n=k+1时，考虑G-u,它仍然为连通图，所以，边数≥k-1.于是G 的边数≥k. (2) 考虑G 中途径： 121:n n W v v v v -→→→→L 若W 是路，则长为n-1;但由于G 的边数大于n-1,因此，存在v i 与v j ,它们相异，但邻接。于是： 1i i j i v v v v +→→→→L 为G 中一闭途径，于是也就存在闭迹。 (3) 若不然，G 中顶点度数至少为2，于是由握手定理： ()2()21v V G m d v n m n m n ∈= ≥?≥?>-∑ 这与G 中恰有n-1条边矛盾！ 2.(1)2n ?12n 2?12n ?1 (2)2n?2?1 (3) 2n?2 。证明 :u 1的两个邻接点与v 1的两个邻接点状况不同。所以，两图不同构。 4.证明下面两图同构。 u 1 v 1

证明:作映射f : v i ? u i (i=1,2….10) 容易证明，对?v i v j ∈E ((a)),有f (v i v j,),=,u i,u j,∈,E,((b)) (1≤ i ≤ 10, 1≤j ≤ 10 ) 由图的同构定义知，图(a)与(b)是同构的。 5.指出4个顶点的非同构的所有简单图。分析：四个顶点的简单图最少边数为0，最多边数为6，所以可按边数进行枚举。 (a) v 2 v 3 u 4 u (b)

电子科技大学研究生试题《图论及其应用》(参考答案)

电子科技大学研究生试题《图论及其应用》(参考答案) 考试时间：120分钟一．填空题(每题3分，共18分) 1．4个顶点的不同构的简单图共有__11___个； 2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于3。则G 中顶点数至少有__9___个； 3．设n 阶无向图是由k(k ?2)棵树构成的森林，则图G 的边数m= _n-k____; 4．下图G 是否是平面图？答__是___; 是否可1-因子分解？答__是_. 5．下图G 的点色数=)(G χ______, 边色数=')(G χ__5____。图G 二．单项选择(每题3分，共21分) 1．下面给出的序列中，是某简单图的度序列的是( A ) (A) (11123); (B) (233445); (C) (23445); (D) (1333). 2．已知图G 如图所示，则它的同构图是（ D ） 3．下列图中，是欧拉图的是（ D ） 4．下列图中，不是哈密尔顿图的是（B ） 5．下列图中，是可平面图的图的是（B ） A C D A B C D

6．下列图中，不是偶图的是（ B ） 7．下列图中，存在完美匹配的图是（B ）三．作图(6分) 1．画出一个有欧拉闭迹和哈密尔顿圈的图； 2．画出一个有欧拉闭迹但没有哈密尔顿圈的图； 3．画出一个没有欧拉闭迹但有哈密尔顿圈的图；解：四．(10分)求下图的最小生成树，并求其最小生成树的权值之和。解：由克鲁斯克尔算法的其一最小生成树如下图：权和为：20. 五．(8分)求下图G 的色多项式P k (G). 解：用公式 (G P k -G 的色多项式： )3)(3)()(45-++=k k k G P k 。六．(10分) 22，n 3个顶点的度数为3，…，n k 个顶点的度数为k ，而其余顶点的度数为1，求1度顶点的个数。解：设该树有n 1个1度顶点，树的边数为m. 一方面：2m=n 1+2n 2+…+kn k 另一方面：m= n 1+n 2+…+n k -1 v v 1 3 图G

图论练习题2009(学生练习)

图论练习题一、基本题 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、把平面分成x个区域，每两个区域都相邻，问x最大为（） A．6 B．4 C．5 D．3 5、设图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、设G=为有向图，则有（）。 A．E?V x V B．E?V x V C．V x V?E D．V x V=E 7、图G1和G2的结点和边分别存在一一对应关系是G1和G2同构的（）。 A．充分条件B．必要条件C．充分必要条件D．既不充分也不必要条件8、设G=为有向图，V={a,b,c,d,e,f}，E={,,,,}是（）。A．强连通图B．单向连通图C．弱连通图D．不连通图 9、无向图G中的边e是G的割边（桥）的充分必要条件是（）。 A．e是重边B．e不是重边 C．e不包含在G的任一简单回路中D．e不包含在G的某一简单回路中 10、在有n个结点的连通图中，其边数（） A．最多有n-1条B．至少有n-1条C．最多有n条D．至少有n条 11．设无向简单图的顶点个数为n，则该图最多有（）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．n2 12．要连通具有n个顶点的有向图，至少需要（）条边。 A．n-l B．n C．n+l D．2n 13．n个结点的完全有向图含有边的数目（）。 A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l） 14．一个有n个结点的图，最少有（）个连通分量。 A．0 B．1 C．n-1 D．n 15．一个有n个结点的图，最多有（）个连通分量。 A．0 B．1 C．n-1 D．n 16．在一个无向图中，所有顶点的度数之和等于所有边数（）倍。 A．1/2 B．2 C．1 D．4 17．在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。 A．1/2 B．2 C．1 D．4

课后习题及答案

1 文件系统阶段的数据管理有些什么缺陷试举例说明。文件系统有三个缺陷：（1）数据冗余性（redundancy)。由于文件之间缺乏联系，造成每个应用程序都有对应的文件，有可能同样的数据在多个文件中重复存储。（2）数据不一致性（inconsistency)。这往往是由数据冗余造成的，在进行更新操作时，稍不谨慎，就可能使同样的数据在不同的文件中不一样。（3）数据联系弱(poor data relationship)。这是由文件之间相互独立，缺乏联系造成的。 2 计算机系统安全性（1）为计算机系统建立和采取的各种安全保护措施，以保护计算机系统中的硬件、软件及数据；（2）防止其因偶然或恶意的原因使系统遭到破坏，数据遭到更改或泄露等。 3. 自主存取控制缺点（1）可能存在数据的“无意泄露” （2）原因：这种机制仅仅通过对数据的存取权限来进行安全控制，而数据本身并无安全性标记（3）解决：对系统控制下的所有主客体实施强制存取控制策略 4. 数据字典的内容和作用是什么数据项、数据结构数据流数据存储和加工过程。 5. 一条完整性规则可以用一个五元组（D，O，A，C，P）来形式化地表示。对于“学号不能为空”的这条完整性约束用五元组描述 D：代表约束作用的数据对象为SNO属性； O（operation）：当用户插入或修改数据时需要检查该完整性规则； A（assertion）：SNO不能为空； C（condition）：A可作用于所有记录的SNO属性； P（procdure）：拒绝执行用户请求。 6.数据库管理系统（DBMS）

：①即数据库管理系统（Database Management System)，是位于用户与操作系统之间的一层数据管理软件，②为用户或应用程序提供访问DB的方法，包括DB的建立、查询、更新及各种数据控制。 DBMS总是基于某种数据模型，可以分为层次型、网状型、关系型、面向对象型DBMS。 7.关系模型：①用二维表格结构表示实体集，②外键表示实体间联系的数据模型称为关系模型。 8.联接查询：①查询时先对表进行笛卡尔积操作，②然后再做等值联接、选择、投影等操作。联接查询的效率比嵌套查询低。 9. 数据库设计：①数据库设计是指对于一个给定的应用环境，②提供一个确定最优数据模型与处理模式的逻辑设计，以及一个确定数据库存储结构与存取方法的物理设计，建立起既能反映现实世界信息和信息联系，满足用户数据要求和加工要求，又能被某个数据库管理系统所接受，同时能实现系统目标，并有效存取数据的数据库。 10．事务的特征有哪些事务概念原子性一致性隔离性持续性 11．已知3个域： D1=商品集合=电脑，打印机 D3=生产厂=联想，惠普求D1，D2，D3的卡尔积为： 12.数据库的恢复技术有哪些数据转储和和登录日志文件是数据库恢复的

离散数学试卷及答案(2)

一、填空 20% （每小题2分） 1、 P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为；“虽然你努力了，但还是失败了”的翻译为。 2、论域D={1，2}，指定谓词P 则公式),(x y yP x ??真值为。 2、设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是。 3、设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R= （列举法）。 R 的关系矩阵M R = 。 5、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ； A 上既是对称的又是反对称的关系R= 。 6、设代数系统，其中A={a ，b ，c}, 则幺元是；是否有幂等性；是否有对称性。 7、4阶群必是群或群。 8、下面偏序格是分配格的是。

9、n 个结点的无向完全图K n 的边数为，欧拉图的充要条件是。 10、公式R Q P Q P P ?∧∨?∧∧?∨)(())(( 的根树表示为。二、选择 20% （每小题2分） 1、在下述公式中是重言式为（） A ．)()(Q P Q P ∨→∧； B ．))()(()(P Q Q P Q P →∧→??； C ．Q Q P ∧→?)(； D ．)(Q P P ∨→ 。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为（），成真赋值的个数为（）。 A ．0； B ．1； C ．2； D ．3 。 3、设}}2,1{},1{,{Φ=S ，则 S 2 有（）个元素。 A ．3； B ．6； C ．7； D ．8 。 4、设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产生的S S ?上一个划分共有（）个分块。 A ．4； B ．5； C ．6； D ．9 。 5、设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为