2023年7月19日发(作者：)

离散数学期末练习题-(带答案) A.

(pq)p

C.

p(qp)

B.

p(qp)

D.

(pq)p

8．设R(x):x为有理数；Q(x):x为实数。命题“任何有理数都是实数”的符号化为（ ）

A．(x)(R(x)Q(x)) B．(x)(R(x)Q(x))

C．(x)(R(x)Q(x)) D．x(R(x)Q(x))

9.设个体域D{a,b}，与公式xA(x)等价的命题公式是( )

A．A(a)A(b) B．A(a)A(b)

C．A(a)A(b) D．A(b)A(a)

10.下列等价式不正确的是（ ）。

A．x(P(x)Q(x))xP(x)xQ(x)

B．x(P(x)Q(x))xP(x)xQ(x)

C．x(P(x)Q(x))xP(x)xQ(x)

D．x(P(x)Q)xP(x)Q

11. 设个体域D{a,b}，与公式xA(x)等价的命题公式是( )

A．A(a)A(b) B．A(a)A(b)

C．A(a)A(b) D．A(b)A(a)

12.设X={,{a},{a,}}，则下列陈述正确的是（ ）。

A.aX B.{a,}X

C.{{a,}}X D.{}X

13.有向图D是连通图，当且仅当（ ）。

A. 图D中至少有一条通路

B. 图D中有通过每个顶点至少一次的通路

C. 图D的连通分支数为一

D. 图D中有通过每个顶点至少一次的回路

14.设A={a,b,c}，则下列是集合A的划分的是( )

A.{{b,c},{c}} B.

{{a},{b,c}}

C.{{a,b},{a,c}} D.

{{a,b},c}

15.下列谓词公式中是前束范式的是（ ）。

A．xF(x)(x)G(x) B．xF(x)yG(y)

C．x(P(x)yQ(x,y)) D．xy(P(x)Q(x,y))

16.设M{x|f1(x)0},N{x|f2(x)0}，则方程f1(x)f2(x)0的解为（A．M∩N B．M∪ N

C．MN C．M-N

）。 17.设GA,是群，则下列陈述不正确的是（ ）。

A.

(a1)1a

C.

(ab)1a1b1

A.

abb1

C.

abab1

B.

anamanm

D.

(a1ba)na1bna

B.

aba1

D.

abab1

18.在整数集合Z上，下列定义的运算满足结合律的是（ ）。

19. 设简单图G所有结点的度数之和为50，则G的边数为（ ）。

( )

A. 50 B. 25

C. 10 D. 5

20.设简单无向图G是一个有5个顶点的4－正则图，则G有（ ）条边。

A. 4 B. 5 C. 10 D. 20

21.设集合A{1,2,3,4},A上的等价关系R{1,1,3,2,2,3,

4,4}IA，则对应于R的划分是（ ）。

A.

{{1},{2,3},{4}}

C.

{{1,3},{2},{4}}

B.

{{1,3},{2,4}}

D.

{{1},{2},{3},{4}}

22.设集合A{1,2,3,4},A上的等价关系R{1,3,3,1,2,4,

4,2}IA，则对应于R的划分是（ ）。

A.

{{1},{2,3},{4}}

C.

{{1,3},{2},{4}}

B.

{{1,3},{2,4}}

D.

{{1},{2},{3},{4}}

23.设GA,是群，则下列陈述不正确的是（ ）。

A.

(a1)1a

C.

anamanm

24.A{1,2,B.

(ab)1a1b1

D.

(a1ba)na1bna

。

,10}，下列定义的运算关于集合A是不封闭的是（ ）A.

xymax{x,y}，即x,y的较大数

B.

xymin{x,y}，即x,y的较小数

C.

xygcd{x,y}，即x,y的最大公约数

D.

xylcm{x,y}，即x,y的最小公倍数

25. 设X{1,2,3},Y{a,b,c,d},f{1,a,2,b,3,c}，则f是

( )。

A．从X到Y的双射

B．从X到Y的满射，但不是单射

C．从X到Y的单射，但不是满射

D．从X到Y的二元关系，但不是从X到Y的映射 26.设简单无向图G是一个有6个顶点的5－正则图，则G有( )条边。

A. 5 B. 6 C. 15 D. 30

abd27.图G如下图所示，以下说法正确的是( )。

A．a是割点 B．{b,c}是点割集

C．{b,d}是点割集 D．{c}是割点

A．链

B．钻石格

c28.格L是分配格的充要条件是L不含与下面哪一个选项同构的子格（ ）。

C．五角格 D. 五角格与钻石格

29.下列图是欧拉图的是（ D ）。

30.给定一个有n个结点的无向树，下列陈述不正确的是（ ）。

A．所有结点的度数≥2

B．无回路但若增加一条新边就会变成回路

C．连通且ev1，其中e是边数，v是结点数

D．无回路的连通图

31. 设A有5个元素，则其幂集P(A)的元素总个数为（ ）。

A. 32

C. 50

（ ）。

A. (1,2,2,3,4,5)

C. (1,1,1,2,3)

B.25

D. 5

32．若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是B. (1,2,3,4,5,5)

D. (2,3,3,4,5,6)

33. 设A{a,{a},{a,{a}}}则其幂集P(A)的元素总个数为（ ）。

A. 3

C. 8

B. 4

D. 16

34. 在实数集合R上，下列定义的运算中不可结合的是（ ）。

A.

abab2ab

B.

abab

C.

ababab

D.

abab

35. 无向图G是欧拉图，当且仅当（ ）。 A. G的所有结点的度数全为偶数

B. G中所有结点的度数全为奇数

C. G连通且所有结点度数全为奇数

D. G连通且所有结点度数全为偶数

36.下列不一定是树的是（ ）

．．．A. 无回路的连通图D

B. 有n个结点，n-1条边的连通图

C. 每对结点之间都有通路的图

D. 连通但删去一条边则不连通的图

37. 设简单图G所有结点的度数之和为48，则G的边数为

( )

A. 48 B. 24

C. 16 D. 12

38．下面既是哈密顿图又是欧拉图的图形是（ B ）。

39.下列必为欧拉图的是（ ）

A.有回路的连通图

C.有1个奇数度结点的连通图

40.二部图

K3,3是（ ）。

A.欧拉图

C.平面图

B. 哈密顿图

D. 完全图

B.不可以一笔画的图

D.无奇数度结点的连通图

41．下列所示的哈斯图所对应的偏序集中能构成格的是（ C ）。

A. B. C.A. 3

C. 9

D.

B. 6

D. 18

42.设简单无向图G是一个有6个顶点的3－正则图，则G有( )条边。

43．下列式子为矛盾式的是（ ）。

A．p(pq)

C．pp

B．pp

D．

(pq)pq

44.设集合A{a,b,c}，A上的关系R{a,a,a,c,c,a}，则R是（ ）

A．自反的 B．对称的

C．传递的 D．反对称的

45．设R1,R2是集合A{a,b,c,d}上的两个关系，其中R1{a,a,b,b,

则R2 是R1b,c,d,d}，R2{a,a,b,b,c,b,b,c,d,d}，的（ ）闭包。

A．自反

C．传递

B．对称

D．自反、对称且传递闭包

B．((x)F(x)(y)G(y))H(z)

46. 下列公式是前束范式的是（ ）。

A．(x)(y)(F(z,x)G(y))

C．(x)F(x,y)(y)G(y) D．(x)(F(x,y)(y)G(x,y))

47. 设R为实数集，函数f:RR，f(x)x22x5，则f是（ ）。

A．单射而非满射

C．双射

B．满射而非单射

D．既不是单射，也不是满射

48．下列各图中既是欧拉图，又是汉密尔顿图的是（ C ）。

A． B． C． D．

49．下列四个格，是分配格的是（ C ）。

50．设集合A={a,b, c}上的关系如下，具有传递性的是（ ）。

A． R={,,,} B． R={,}

C． R={,,,} D． R={}

参考答案：（若有问题，可以到1#402或打电话问）

一、选择题

AAAAB DACAA CCDBD BCDBC ABBDC CBDDA

ACCDD BBBDB CCCBB ADCCD

二、填空题

1．命题公式(pq)的成真指派为 10 ，成假指派为_00，01，11__。

2. 命题公式(pq)p的成真指派为00 10 11，成假指派为_01__。

3．命题公式p(pq)的成真指派为00 01 11 , 成假指派为_ 10__。

4．公式(x)(y)(P(y)Q(x,z))(y)R(x,y)约束变元为 x,y ，自由变元为 x,z

。

5．公式x(P(x)yR(y))Q(x,z)约束变元为__x,y_，自由变元为_x,z_

。

6．设A{a,b,{a,b}}，B{a,b}，则BA，AB {{a,b}} 。

7．设A{1,2,3}，A上的关系R{1,2,2,1}，则对称闭包

s(R) {<1,2>,<2,1>} ，传递闭包t(R) {<1,2>,<2,1>,<1,1>,<2,2>}。

8.设*是集合S上的二元运算，若运算*满足__结合律_，并且存在__单位元_，则称S,*为独异点。

9． 设A{a,b,{a,b}}，B{a,b,c}，则AA，AB {{a,b},c} 。

10.一棵无向树的顶点数n与边数m的关系是 m=n-1 。6阶无向连通图至多有 6 棵不同构的生成树。

11．设f(x)x1，g(x)x2，则复合函数(fg)(x)=(x1)2,(gf)(x) =x21。

12.

Zn,是一个群，其中Zn{0,1,2,,n1}，xy(xy)modn，则当n=6时，在Z6,中，2的阶为___3___, 3的阶为_ 2 。 13．设是格，其中A={1, 3,4，6，8，12，24}，≤为整除关系，则1的补元是___24 __，3的补元是_8_。

14．设A=｛<1，3>，<3，5>，<4，4>｝，B=｛<1,3>,<4,5>,<5,5>｝,那么dom(AB)={1,3,4,5} ran(AB)= {3,5} 。

15. 设A={l,2,3,4},A上的二元关系R={<1,2>,<2,3>,<3,2>}，S={,<2,3>，<4，3>}，

则RS {<1,3>,<3,3>} ,(RS)1 {<3,1>,<3,3>} 。

16．设R={<1,2>,<3,4>,<3,5>}和S={<2,1>,<3,3>,<5,5>}是集合A={1,2,3,4,5}上的两个关系，则RS= {<1,1>,<3,5>} ，

S1R1= {<1,1>,<5,3>} 。

17． 设A={2, 4, 6}，A上的二元运算*定义为：a*b=max{a,b}，则在独异点中，单位元是 2 ，零元是 6 。

18．一棵无向树的顶点数n与边数m关系是 m= n-1 。设G是具有8个顶点的树，则G中增加___21 _条边才能把G变成完全图。

19．设复合函数gf是从A到C的函数，如果gf是满射，那么__ g___必是满射，如果gf是单射，那么_f _必是单射。

20．设是格，其中A={1, 3, 5, 9, 45}，≤为整除关系，则1的补元是___45___，3的补元是_ 5 _。

21．给出A={l，2}上的一个等价关系_{<1,1>,<2,2>}_，并给出其对应的划分_{{1},{2}}______。

22．设A{a,b,c,d}，A上的二元关系R{a,b,a,d,b,b}，则R的自反闭包r(R)RIA，传递闭包t(R) R

23．命题公式(pq)p的成真赋值为 01 10 11 ，成假赋值为 00 。

24．公式(pq)(pq)的成真赋值是 00,11 。成假赋值 01 10

25．公式(pq)(pq)的成真赋值是 01 11 。成假赋值 00 10

26．公式(pq)(pq)的成假赋值是 01 10 。成假赋值 00 11

27．设个体域是实数集，命题x(x3x)的真值为 1 ；命题x(x210)的真值为 0 。

28.设f∶R→R,f(x)=x+3,g∶R→R,g(x)=2x+1,则复合函数(fg)(x)(gf)(x) 2x+4 ,

2x+7 。

{<1,5>,<3,2>,<2,5>} 。

29.给定集合A={1,2,3,4,5}，在集合A上定义两种关系：R={<1,2>,<3,4>,<2,2>},

S={<4,2>,<2,5>,<3,1>,<1,3>，则RS30．设A={0，1，2，3，6}，R{x,y|x,yAxyxy(mod3)}则 domR= {0， 3，6}_ ，ranR=_{0， 3，6} ，

31． 设Z6,为模6加群，其中Z6{0,1,2,3,4,5}，则2-3= 0 ，4-2= 4 。

32．一个结点为n的无向完全图，其边的数目为n(n-1)/2 ，顶点的度为 n-1 。

33. 已知n阶无向简单图G有m条边，则G的补图G中有 m- n(n-1)/2 条边。

参考答案：

1．_10_，00，01，11

2. 00 10 11， 01_

3. _00 01 11, 10

4. _x,y ，x,z__

5. _x,y ，x,z__

6.,, {{a,b}}

7.{1,2,2,1}，{1,2,2,1,1,1,2,2}

8. 结合律 ， 单位元

9．,, {{a,b}，c}

10.n-1, 6

11.

(x1)2,,x21

12. 3 , 2

13. _24__,_8__

14. {1,3,4,5}，_{3}

15. {<1,3>,<3,3>},{<3,1>,<3,3>}

16.

{1,1,3,5}，{1,1,5,3}

17. 2 , 6

18. m= n-1, _21

19. _g , _f_

20. 45 , _5_

21.

{1,1,2,2},{{1},{2}}

22.

RIA,

R

23. 01 10 11，00

24. 00，11 ,01，10

25. 01，11 ,00，10

26. 01 10 , 00 11 27. 1 , 0

28.

2x4,2x7

29. {<1,5>,<3,2>,<2,5>}

30. {0， 3，6}, {0， 3，6}

31. 0 , 4

32. n(n-1)/2, n-1

33. m- n(n-1)/2

三、计算题（仅给出部分题目的解题思路，未给出答案自己完成）

1. 已知命题公式(pq)(pr)

（1）构造真值表

（2）求出公式的主析取范式

解题思路：（1）真值表

p q r

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

p

(pq)

pr

(pq)(pr)

1

1

1

1

0

0

0

0

0

0

1

1

1

1

1

1

0

0

0

0

0

1

0

1

1

1

0

0

0

1

0

1

（2）(pq)(pr)

(pqr)(pqr)(pqr)(pqr)

m0m1m5m72.已知命题公式(pq)(pr)

（1）构造真值表；

（2）用等值演算法求公式的主析取范式。

解：（1）真值表

p q

r

pq

pr

(pr)

(pq)(pr) 0 0

0

0 0

1

0 1

0

0 1

1

1 0

0

1 0

1

1 1

0

1 1

1

（2）主析取范式

(pq)(pr)0

0

1

1

1

1

1

1

0

1

0

1

1

1

1

1

1

0

1

0

0

0

0

0

1

1

1

0

0

0

0

0

(pq)(pr)(pq)(pr)

((pq)(rr))(p(qq)r)((pqr)(pqr)(pqr)(pqr)m0m1m23．求公式(p(rp))(qp) 的主合取范式及主析取范式。

4．构造命题公式(p∧r)∨(pq)的真值表。

5. 一棵（无向）树有2结点的度为2， 1个结点的度为3，3个结点的度为4, 其余都是叶结点，问该树有几个叶结点？

解：在一个有限图中，各结点的度数总和是边数的2倍；而树中的边数为结点数减1。

根据这两点，可知树中各结点的度数总和=2*（树中点数-1），设树叶有x个， 于是，2*2+3+3*4+x=2*（2+1+3+x-1）

得x=9。

6.一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有几个顶点？

提示：类似上题求解。

7.设f:RR,f(x)x22，g:RR,g(x)x4,h:RR,h(x)x31，

其中R表示实数集。

（1）求函数fg，gf；

（2）f,g,h哪些函数有反函数？如果有，求出这些反函数。

解：（1）gf(x)f(g(x))f(x4)(x4)22x28x14

fg(x)g(f(x))g(x22)x22

（2）g和h有反函数，g1:RR,g1(x)x4；

h1:RR,h1(x)3x1

8.设A＝{a，b，c}，R是A上的二元关系，且R＝{，}，求r(R)、s(R)和t(R)。

解：r(R)=R∪IA={,,,,}

s(R)=R∪R-1={,}

t(R)= R∪R2∪R3={，，，}

9.设A{1,2,3,4,6,9,24,54}，为整除关系。

（1）画出偏序集的哈斯图；

（2）求A中的极大元；

（3）求子集B=｛3, 6, 9｝的上确界与下确界。

解：（1）哈斯图

24

2

1

6

59

3

（2）A中的极大元为 24，54；极小元为1；最大元：无；最小元：1

（3）求子集B=｛3, 6, 9｝的上确界为54，下确界为3。

10.设有向图D如图所示，用邻接矩阵完成以下计算。

（1）v1到v4长度小于或等于4的通路数； （2）v1到自身长度小于或等于4的回路数；

（3）求出D的可达矩阵，并说明D的连通性。

有向图的邻接矩阵为

10A0010A30021010010，A20001010024310010，A4000101004231001

010001264001

010001（1）v1到v4长度小于或等于4的通路数为

ai1(i)1401348

（2）v1到自身长度小于或等于4的回路数为

ai14(i)1111114

10（3）P(D)00111111

011011由可达矩阵可知D是单向连通的。

11．设A{0,1,2}，给出幂集合P(A)对称差运算的运算表。

12．设Z6{0,1,2,3,4,5}，给出模6加运算的运算的运算表。 参看教材P167例9.4 与9.5

14. 设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。

解：r(R)=R∪IA

s(R)=R∪R-1

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

15.下图为一连通赋权图，计算该图的最小生成树和权值。

四、简答题

2,5,3,1,3,3,3,6,4,4,5,2,5,5,

1.设集合A{1，2，3，4，5，6}上的关系R{(1,1,1,3,1,6,2,2,

6,1,6,3),6,6}

（1）画出R的关系图，并写出R的关系矩阵；

（2）R是否为等价关系？若是，写出R的所有等价类。

解：（1）R的关系图为

1

6

3

4

2

5

01001001

01000010

100110（2）R的关系矩阵

100由关系图可以看出R是等价关系。等价类为：

[1][3][6]{1,3,6},[2]{2,5},[4]{4}

或写为：A/R={{1,3,6},{2,5},{4}}

2. 设R{1,3,(1,4,2,2,3,1,3,3),4,1}是A={1,2,3,4}上的二元关系。

（1）画出R的关系图；

（2）写出R的关系矩阵；

（3）讨论R的性质。

解：（1）R的关系图

1

3

4

2

011100

000000

00（2）R的关系矩阵

11（3）R非自反、非反自传、对称、非反对称 、非传递的

（4）R不是函数，不满足函数单值性的要求。

3．设A={1,2,3,4,5,6,7,8,9,10}，R是A上的二元关系，

R={|x,y∈A ∧x+y=10} 说明R具有哪些性质。

解：R={<1,9>,<2,8> ,<3,7> ,<4,6> ,<5,5> ,<9,1>,<8,2> ,<7,3> ,<6,4> }

易知 R既不是自反也不是反自反的

R是对称的

R不是反对称的

R不是传递的。

4．判断下图是否为二部图？若是，找出它的互补结点子集。它是否为哈密顿图？a若是，找出一条哈密顿回路。

bi

gc

hf

jd

e5.判断下图G是否是二部图？若是，找出它的互补结点子集。它是否为哈密顿图？若是，找出一条哈密顿回路。

v1v5v6v2v8v7v3 6.设A{1,3,5,9,45}，为A上的整除关系。

（1）A,是否为偏序集，若是，画出其哈斯图；

（2）A,是否为格？说明理由；

解：（1）A,是偏序集。哈斯图为：

四、证明题

1．用一阶逻辑的推理理论证明：

前提：x(F(x)G(x))，x(F(x)H(x))，

xH(x)

结论：

xG(x)

证明：（1）x(F(x)H(x)) 前提引入

（2）F(x)H(x) （1）

（3）xH(x) 前提引入

（4）H(x) （3）

（5）F(x) （2）（4）析取三段论 ………（4分）

（6）x(F(x)G(x)) 前提引入

（7）F(x)G(x) （6）

（8）G(x) （5）（7）假言推理

（9）G(x) （8） ………（3分）

2．设A是非空集合,F是所有从A到A的双射函数的集合, 是函数的复合运算。

证明：F,是群。

证明：由于集合A是非空的，IAF，,因此F非空 。

(1)

f,gF,因为f和g都是A到A的双射函数，故fg也是A到A的双射函数，从而集合F关于运算 是封闭的。

(2)

f,g,hF,由函数复合运算的结合律有(fg)hf(gh)，故运算 是可结合的。

49

3

1

5

（2）A,是格。因为偏序集中的任意两个元素均有上、下确界。 (3)

A上的恒等函数IA也是A到A的双射函数即IAF,且fF有IAffIA, 故IA 是F,中的幺元。

(4)

fF,因为f是双射函数，故其逆函数是存在的，也是A到A的双射函数，且有ff1f1fIA,因此f1是f的逆元

由此上知F,是群

3．设代数系统VZ6,，Z6{0,1,2,3,4,5}，为模6加法。证明：Z6关于运算构成群。

证明：集合Z6显然非空。

(1)

a,bZ6,abZ6,从而集合Z6关于运算是封闭的。

(2)

a,b,cZ6,有(ab)ca(bc)，故运算 是可结合的。

(3)

aZ6,

a0a,故0是Z6,中的幺元。

(4)

aZ6,因为a(6a)0,因此6a是a的逆元

由此上知Z6,是群

4．设A是集合，P(A)是A的幂集合，是对称差运算， 证明

>构成群。

提示：参考2、3证明题完成。

5．设A{x,y|x,y为正整数}，在A上定义二元关系R如下：x,yRu,v当且仅当xyuv。

证明：R是一个等价关系。

证明：

任取x,y

x,yAxyxyx,yRx,y

所以R自反的。

任取x,y,u,v

x,yRu,vxyuvuvxyu,vRx,y

所以R是对称的。

任取x,y,u,v,s,t

x,yRu,vu,vRs,txyuvuvst

xystx,yRs,t

所以R是传递的。 因此，R是等价关系。

6.设R是A上的关系，如果R满足以下两条件：

（1）对于任意的aR， 都有aRa，

（2）若aRb, aRc, 则有bRc，

证明：R是等价关系

证明： 任取a,b,cR

（1）由已知条件（1）得

a,aR,,所以R是自反的。

（2）由已知条件（1）、（2）得

a,bRa,aRb,aR

所以R是对称的。

（3）由已知条件（1）、（2）得

a,bRb,cRb,aRc,bR

b,cRb,aRc,aR

所以R是传递的。

五、应用题（仅给出第7题的参考答案,未给出参考答案的自己完成）

1. 构造下列推理的证明。

如果今天是星期一，则要进行英语或离散数学考试。如果英语老师有会，则不考英语。今天是星期一，英语老师有会，所以进行离散数学考试。

2. 构造下列推理的证明。

小王是理科学生，则他的数学成绩很好。如果小王不是文科学生，则他一定是理科学生。小王的数学成绩不好, 所以小王是文科学生。

3．如果甲是冠军，则乙或丙将得亚军；如果乙得亚军，则甲不能得冠军； 如果丁得亚军，丙不能得亚军；事实是甲已得冠军。因此丁不能得亚军。

参照作业：P54 17,18

4.用一阶逻辑推理证明

每个喜欢步行的人都不喜欢骑自行车，每个人或喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车，所以，有的人不喜欢步行（个体域为人类集合）

解: 令F(x):x喜欢步行,

G(x):x喜欢骑自行车,

H(x):x喜欢乘汽车

前提：x(F(x)G(x))，x(F(x)H(x))，

xH(x)

结论：

xG(x)

证明：（1）x(F(x)H(x)) 前提引入

（2）F(x)H(x) （1） （3）xH(x) 前提引入

（4）H(x) （3）

（5）F(x) （2）（4）析取三段论

（6）x(F(x)G(x)) 前提引入

（7）F(x)G(x) （6）

（8）G(x) （5）（7）假言推理

（9）G(x) （8）

5．今有于a,b,c,d,e,f7个人，已知下列事实：

a会讲英语；

b会讲英语和汉语； c会讲英语、意大利语和俄语；d 会讲日语和汉语；

e 会讲德国和意大利语；f 会讲法语、日语和俄语；

g 会讲法语和德语。

试问这七个人应如何排座位，才能使每个人都能和他身边的人交谈？

解：用结点表示人，用边表能讲同一种语言，构

在G中存在着一条哈密据这条回路安排座位，就能和他身边的人交谈。

汉

法

英

英

德英

俄

英

汉

日ag法

示连接的两个人造出图G如下：

fbe顿回路如下，根够使每个人都能cc意

da英

意

e德bgd日f

6． 一次学术会议的理事会共有20个人参加，他们之间有的互相认识但有的互相不认识。但对任意两个人，他们各自认识的人的数目之和不小于20。问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人？根据是什么？ 7.设有7个城市v1，v2，……v7，任意两个城市之间直接通信线路及通信线路预算造价如带权图所示，试给出一个设计方案，使得各城市间能够通信，而且总造价最低。写出求解过程，并计算出最低总造价。

v115v6

v23v054v035441v5422v3

v4解：带权图中边表示通信路，边上的数字表示修建该通信线路所需费用，于是求解此题便成为求权图中的最小生成树问题。

按避圈算法，对图中各边的权值按由小到大的顺序排序，

112233444555

取(v1,v2)T,(v4,v5)T，(v3,v4)T，(v0,v4)T

(v0,v2)Tv11v65，(v1,v6)T

v2v3v03v521则求解最小生成树如下图所示：

图中最小生成树的权为:

w(v1,v2)+w(v4,v5)+w(v3,v4)+w(v0,v4)+w(v0,v2)+w(v1,v6)=2v41+1+2+2+3+5=14