离散数学题库及答案

数理逻辑部分

选择、填空及判断

/下列语句不是命题的（A）o

（A）你打算考硕士研究生吗？（B）太阳系以外的星球上有生物。

（0离散数学是计算机系的一门必修课。（D）雪是黑色的。

/命题公式Pf（Pv「P）的类型是（A）

（A）永真式（B）矛盾式

（C）非永真式的可满足式（D）析取范式

/A是重言式，那么A的否定式是（A）

A.矛盾式B.重言式C.可满足式D.不能确定

/以下命题公式中，为永假式的是（C）

A.p-*（pVqVr）B.（p-ip）--]pC.-]（q-*q）ApD.-]（qVnp）^（pA-ip）

/命题公式P-Q的成假赋值是（D）

A.00,11B.00,01,11C.10,11D.10

/谓词公式X/xP（无）AR（X,y）中，变元x是（B）

A.自由变元B.既是自由变元也是约束变元

C.约束变元D.既不是自由变元也不是约束变元

/命题公式Pf（Qv「Q）的类型是（A）。

（A）永真式（B）矛盾式

（0非永真式的可满足式（D）析取范式

/设B不含变元x,玉等值于（A）

A.VxA(x)TBB.3x(A(x)vB)C.3xA(x)fBD.3x(A(x)AB

/下列语句中是真命题的是（D）o

A.你是杰克吗？B.凡石头都可练成金。

C.如果2+2=4,那么雪是黑的。D.如果1+2=4,那么雪是黑的。

,从集合分类的角度看，命题公式可分为（B）

A.永真式、矛盾式B.永真式、可满足式、矛盾式

C.可满足式、矛盾式D.永真式、可满足式

/命题公式等价于（D）。

A.—'pVqB.—1（pVq）C.--pAqD.p——

/一个公式在等价意义下，下面写法唯一的是（D）。

（A）范式（B）析取范式（C）合取范式（D）主析取范式

/下列含有命题p,q,r的公式中，是主析取范式的是（D）。

（A）（pAqAr）v（-,pAq）（B）（pvqvr）A（^pAq）

(C)(pvqvr)A(—ipvqvr)(D)(pAqAr)v(「pAqAr)

/设个体域是整数集合，P代表Vx\/y((x<y)Tx-y<x)),下面描述正确的是(C)。

(A)P是真命题(B)P是假命题

(C)P是一阶逻辑公式，但不是命题(D)P不是一阶逻辑公式

,对一阶逻辑公式▼心^(尸(*/)/^以外幻)/^玉7(*/)的说法正确的是(B).

(A)x是约束的，y是约束的，2是自由的；

(B)x是约束的，y既是约束的又是自由的，z是自由的；

(C)x是约束的，y既是约束的又是自由的，2是约束的；

(D)x是约束的，y是约束的，2是约束的；

/n个命题变元可产生(D)个互不等价的布尔小项。

(A)n(B)n2(C)2n(D)2n

/命题“没有不犯错误的人”符号化为(D)。

设"(%)：》是人，尸(x)"犯错误。

(A)Vx(M(x)AP(x))(B)「(天("CO-」P(x)))

(0「(土；(/(%)△P(x)))(D)](人(闻，)人[尸(％)))

/下列命题公式等值的是(C)

(A)「尸人Pv<2(B)Af(Af3),「Af(Af3)

(C)Q-(PvQ),「QvPvQ(D)^AV(AAB),B

/给定命题公式：PV(QAR),则所有可能使它成真赋值为(B),成假赋值为(C)。

(A)111,011；000(B)111,011,100,101,110；

(C)000,010,001；(D)000,110,011,001,100o

/给定前提：Pf(QfS),Q,Pv「R,则它的有效结论为：(B)0

(A)S；(B)RfS;(C)P；(D)RTQ。

/命题：“所有的马都比某些牛跑得快”的符号化公式为：(C)。

假设：“(X)：x是马；C(x)：x是牛；F(x,y)：x比y跑得快。

(A)Vx(H(x)A3y(C(y)AF(X,y)))；(B)Vx(H(x)f3y(C(y)fF(x,y)))；

(C)Vx(〃(x)—0(C(y)A*x,y)))；(D)与Vx(〃(x)f(C(y)△F(x,y)))。

/设P：a是偶数，Q-.6是偶数.而a+6是偶数，则命题“若a是偶数，6是偶数，则a+6

也是偶数”符号化为(C).

(A)PAQAR(B)PAQOR(C)PvQfR(D)PAQ^R

/表达式\fx(P(x,y)VQ(z))ABy(R(x,y)fX/zQ(z))中Vx的辖域是(B).

(A)Plx,力(B)Plx,y)v0(z)(C)A(x,y)(D)P(x,y)人A(x,y)

,判断一个语句是否为命题，首先要看它是否为陈述句,然后再看它是否有唯一的真值。

/命题公式(PVQ)-R的只含联结词」和A的等值式为：

(Af5)AAn5为假言推理规则。

/在一阶逻辑中符号化命题“有会说话的机器人。”设M(x):x是机器人；S(x):x是会说话

的；上述句子可符号化为：fx)(M(x)AS(x))。

/设P：我们爬山，q：我们划船，在命题逻辑中，命题“我们不能既爬山又划船”的符号化形式

为二(pAq).

/设P：小王走路,q：小王唱歌，在命题逻辑中，命题“小王边走路边唱歌”的符号化形式为—

(p/\q).

,量词否定等值式*Y(X)。

/设F(x):x是人，H(x,y):x与y一样高，在一阶逻辑中，命题“人都不一样高”的符号化形

式为VxVy(F(x)AF(y)fH{x,y)).

/若含有n个命题变项的公式A是矛盾式，则A的主合取范式含2n个极小项。

/取个体域为全体整数的集合，给出下列各公式：

(1)(Vx)(Vy)0z)(x-y=z)(2)(Vx)(肛=x)(3)(*)(X/y)(x+y=2y)

其中公式(1)的真值为真,公式⑶的真值为假。

/若含有n个命题变项的公式A是重言式，则A的主合取范式为1或T。

/命题公式Pv(Q△R)的所有成假赋值为000,001,0成0

/谓词公式VxP(x)f玉。(无)的前束范式为Hx(-iP(x)v2(x))o

/在一阶逻辑中，将命题“没有不能表示成分数的有理数”符号化为

/-1玉:(/(%)△->G(x))或Vx(尸(x)fG(x))(设尸(x)：x是有理数；G(x)：x能表示成分数。)

/设个体域。={1,2},那么谓词公式a^(x)vVjB(j)消去量词后的等值式为

41)v42MB⑴八8(2)).

/设P,Q是两个命题，当且仅当P,Q的真值均为1时，P的值为1。(X)

/谓词公式A是「(0一/人4的代换实例，则A是重言式。(X)

/重言式的主析取范式包含了该公式的所有的极小项。(V)

/命题公式A-(B-C)与(AAB)-C等价。(V)

/设A,B,C为命题公式，若A=>3,5=>C,则A=>C。(V)

/在一阶谓词公式中，同一变元符号不能够既约束出现又自由出现。(X)

/在一阶逻辑中，公式的前束范式是唯一的。(X)

计算

/求命题公式(((pVq)Arp)-q)Ar的主析取范式。

答案：rriiVmsVmsVm?

/用等值演算法求公式(Pv(Qf的主析取范式，并由主析取范式求主合取范式。

解：主析取范式：

(Pv(QfR))入

=(Pv-iQv7?)A—iP

0(PA—iP)V(―)QA—iP)V(7?A—iP)

=(—iPA—iQA—iH)V(—iPA—iQA7?)V(—iPA-IQA7?)V(—iPAQA7?)

Om。7mx7m3

主合取范式为：M2AM4AM5AM6AM7

/求公式(PAQ)V(「PAR)的主析取范式，并由主析取范式求主合取范式。

解：(PAQ)V(「PAR)的真值表如下：

PQRPAQTAR(PAQ)V(「

PAR)

000000

001011

010000

011011

100000

101000

110101

111101

故主析取范式为：

(TA「QAR)V(fAQAR)V(PAQA-R)V(PAQAR)

主合取范式为：

(PVRVQ)A(-QVPVR)A(-PVQVR)A(-PVQV-R)

/化公式-<Vx){寺A(x,y)fBx\/y[B(x,y)AVy(A(y,x)fB{x,y))]}为前束范式。

解：原式o(3%)-1{-13yA(x,y)v3xVy[B(x,y)AVy(A(y,x)fB(x,y))])

o(3x){3yA(x,y)AVX寺[T5(X,y)v3y-(A(y,x)TB(x,y))]}

o(Hx){3yA(x,y)AVW3V[—V)V3V^->(A(W,W)—>B(u,w))]}

oHx3y{A(x,y)AVW3V3VV[—>B(W,V)V—1(A(W,W)FB(u,w))]}

o3x3^VwBvBw{A(x,y)Av)v—1(A(w,w)fB(u,w))]}

(或<=>Bx3yVw3vBw{A(x,y)A[—,B(W,V)V(A(W,W)A—,B(W,W))]})

证明

/构造下面推理的证明：

任何自然数都是整数；存在着自然数。所以存在着整数。个体域为实数集合R。

证明：先将原子命题符号化：设F(x)：x为自然数，G(x)：x为整数。则

前提：Vx(尸(x)fG(x)),BxF(x)

结论：3xG(x)

①BxF(x)前提引入

②F(c)①ES规则

③Vx(F(x)TG(x))前提引入

④尸(c)fG(c)③US规则

⑤G(c)②④假言推理

⑥王G(x)⑤EG规则

/用自然推理系统中，证明下列推理：

(Vx)(A(x)-B(x))n((Vx)A(x)—(三x)B(x))

证明：

①(Vx)A(x)附加前提引入

②A(c)①V-

③(Vx)(A(x)-B(x))前提引入

④A(c)-B(c)③V-

⑤B(c)②④假言推理

⑥(mx)B(x)⑤三+

⑦(Vx)A(x)fGx)B(x)①⑥CP规则

所以(Vx)(A(x)-B(x))n((Vx)A(x)-Tx)B(x))

,判断下面推理是否正确，并证明你的结论。

如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过

C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机

系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。

证明：令p：他是计算机系本科生

q：他是计算机系研究生

r：他学过DELPHI语言

s:他学过C++语言

t:他会编程序

前提:(pVq)~*(rAs),(rVs)-*t

结论：p-t

证①P附加前提

②pVq①附加律

③(pVq)—(rAs)前提引入

④rAs②③假言推理

⑤r④化简律

@rVs⑤附加律

⑦(rVs)-t前提引入

⑧t⑤⑥假言推理

/在自然推理系统尸中构造下面推理的证明:

前提：pT(qTr),p,q

结论：FV5

证明：①〃f(q-＞厂)前提引入

②p前提引入

③qfr①②假言推理

④q前提引入

⑤r③④假言推理

©丫7s⑤附加律

/判断下面推理是否正确，并证明你的结论。

如果小王今天家里有事，则他不会来开会。如果小张今天看到小王，则小王今天来开会了。

小张今天看到小王。所以小王今天家里没事。

解：

设P：小王今天家里有事，q:小王来开会，r:小张今天看到小王

本题推理的形式结构是：

前提：pT-q,rTq,r

络i匕：—p

证明：1.rfq前提引入

2.r前提引入

3.q1,2假言推理

4.p—>—\Q前提引入

5.—p3,4拒取式

集合论部分

选择、填空及判断

设集合A={1,2,3,4},B={2,4,6,9},那么集合4B的对称差胸8=（C）.

网{1,3}（B）{2,4,6}（C）{1,3,6,9}（D）{1,2,3,4,6,9}

集合人={1,2,3,6},A上的小于等于关系具有的性质是（D）□

网自反的，对称的，传递的；（）反自反的，对称的，传递的；

©B

反自反的，反对称的，传递的；（D）自反的，反对称的，传递的。

设

A={a,b,c},R={<a,a>,<b,b>},则R具有性质（C）.

网

自反的（B）反自反的（C）反对称的（D）等价的

设A,B,C为任意集合，下面结论正确的是（D）

A.如果>U5=AUC,则B=CB.如果>-5=0,则A=B

C.A©A=AD.A-B=AC\-^B

/设下列各式中(B)是正确的

A.domS^BB.domS^AC.ranS^AD.domSuranS=S

☆A={l,2,3,4},R={〈l,2〉，〈3,4〉,<2,2>}Ws(R)=(B)。

(A){<1,2>,<3,4>,<2,2>}(B){<1,2>,<2,1>,<3,4>,<4,3>,<2,2>}

(C){<1,2>,<3,4>,<1,1>,<2,2>,<3,3>}(D){<1,2>,<2,2>}

/设4={1,2,3},则A上的二元关系有(C)个。

(A)23(B)32(C)23x3⑻/\3Q2x2

/设集合A={1,2,3,5,6,8}A上的二元关系R={<a,b>|a,bEAAa=(bmod3)},则［2人

=（B）o

（A）{1,2}（B）{2,5,8}（C）{3,6}（D）{1}

偏序关系具有的性质是（D）

A.自反的，对称的，传递的B.反自反的，对称的，传递的

C.反自反的，反对称的，传递的D.自反的，反对称的，传递的

等价关系具有的性质是（A）。

A.自反的、对称的、传递的B.反自反的、对称的、传递的

C.反自反的、反对称的、传递的D.自反的、反对称的、传递的

集合A={1,2,…，10}上的关系R={〈x,y>|玳gO,xWA,y£A},则R的性质是(B)。

A.自反的B.对称的C.传递的、对称的D.反自反的、传递的

A={l,2,3,4,5,6},B={a,b,c,d,e},以下哪一个关系是从A到B的满射函数(B)。

A.f={<l,a>,<2,b>,<3,c>,<4,d>,<5,e>}

B.f={<l,e>,<2,d>,<3,c>,<4,b>,<5,a>,<6,e>}

C.f={<l,a>,<2,b>,<3,c>,<4,a>,<5,b>,<6,c>}

D.f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>,<l,b>}

设R是集合A={a,b,c}上的二元关系，且R={〈a,a>,〈b,b>},下面命题哪些为真？(B)

IR是自反的且是传递的

IIR是对称的且是反对称的

IIIR是A上的等价关系

A.只有IB,只有nc.I和nD.n和ni

设〈A,R>是一个偏序集，其中，A={1,2,3,4,5,6},R是整除关系，下面说法不正确的是

(C)

A.4,5,6全是A的极大元B.A没有最大元

C.6是A的上界D.1是A的最大下界

设/和g都是X上的双射函数，则(/。8尸为(C)

A./TogTB.(go/)-]C.g-'o/-'D.go/T

集合A={1,2,3}上所有的等价关系的总数是(B)

A.2B.5C.9D.取决于元素是否为数值

设乂={a3,c},y={1,2,3},/={<a]>,<"2>,<c,3>},则下面命题中唯一正确的是(D)

(A)f是从X到Y的二元关系，但不是从X到Y的函数

(B)f是从X到Y的函数，但不是满射，也不是单射

(C)f是从X到Y的满射，但不是单射

(D)f是从X到Y的双射

设X={a,b,c},R是X上的二元关系，其关系矩阵为MR=011,则传递闭包t(R)的关系图为

011

-100-

011O

011

设集合力={1,2,3,4},B={a,b,c},则|[X8|=12.

设人=匕,b,c},则A的募集P(A)={</),{a},{b},[c],{a,b},{b,c},{a,c},{a,b,c}}«

设集合A={1,2},则A上的全域关系约={〈1,1>,<2,1〉,<2,2>}。

设R是实数集合，-R,/(x)=——x+2,g:R-R,g(x)=x—3,则/。g(x)=x：—x—1

设个体域D={1,2},那么谓词公式玉A(x)vX/y5(y)消去量词后的等值式为(A(l)VA(2))V(B(1)

AB(2))O

/给定集合4={2,3,4,6,8,10,12,120}和这个集合上的整除关系.在这个关系下，该集合的最小

元是不存在，而最大元是120

/设A,B,C,D为任意集合，则的充要条件为4口。,5(X)

/非空集合A上的任意关系R不是对称的就是反对称的。(X)

/关系R是反对称的当且仅当HRjRo(X).

/集合的笛卡尔积运算满足交换律。(X)

/集合A上的恒等关系是一个双射函数。(V)

/若集合A上的关系R是对称的，则Ri也是对称的。(V)

/设A,B为任意集合，如果AUB=A,那么B=0。(X)

/设A,命题“如果f是双射的，则/。广】=//'是真命题。(V)

/集合A上的全域关系是等价关系。(V)

计算

/某班有25个男生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮

球和网球，还有2人3种球都会打。已知6个会打网球的人都会打篮球或排球。求不会打球

的人数。

答案：利用包含排斥原理或文氏图可求得不会打球的有5人。

/设，={1,2,3,…,20},A上的关系R如下:

7?={<x,y>|(xeA)A(yeA)A(x=y(mod5))},

(1)证明：R是A上的等价关系；

(2)求：A上对应于R的划分。

解题要点：(1)分别说明R的自反性、对称性和传递性。

(2){{1,6,11,16},{2,7,12,17},{3,8,13,18},{4,9,14,19},{5,10,15,20}}

详细解答：(1)<x,y>eRoxmy(mod5)o%—y=5左(k为整数)

R的自反性：任意xeA,x-x=5-0,所以<x,x>eR；

R的对称性：任意若<%,丁>eR则x-y=5•左=>y-尤=5・(一左)，

所以，<y,x>eR

R的传递性：任意x,y,zeA,若<x,y>eR且<y,z>eR,

有x-y=5•4i且y-z=5-k2x-z=(x-y)+(y-z)=5-(kl+k2)

所以，<x,z>eRo

即R是A上的等价关系。

(2)[UR={1，6,11』6},⑵氏={2,7,12,17},⑶尺={3,8,13,18}

[4]={4,9,14,19}[5]R={5,10,15,20}

R，O

所以，A/R={[1]R,⑵R,[3]R,[4]R,[5]R}。

/设4={1,2,34,5,6},尺为A上的关系，尺的关系图如下图所示,

(1)求欢,尺3的集合表达式；

(2)求r(R),s(R),t(R)的集合表达式。

解：(1)7?2={<3,3>,<3,1>,<3,5>}»

R3—{<3,3>,<3,1>,<3,5>}

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

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

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

/设集合A={1,2,3},R和S是A上的两个关系，它们的关系矩阵为:

110111

111二001

MR=Ms

101000

⑴写出关系R和S的集合表达式，（2）画出R和S的关系图，⑶说明R和S满足关系的

哪些特性.

解：(1)R={(1,1),(1,2),(2,1),(2,2),(2,3),(3,1),(3,3)};

S={1,1),(1,2),(2,3),(1,3)}

(2)R和S的关系图：(2分)

11

(3)R满足自反性；S满足反对称性、传递性。

/设人={1,2,3,4,5},A上偏序关系

R={〈1,2〉，<3,2),〈4,1),〈4,2),<4,3〉，<3,5〉，<4,5〉}UIA;

(1)作出偏序关系R的哈斯图

(2)令8={1,2,3,5},求B的最大，最小元，极大、极小元，上界，下确界，下界，下确界。

答：⑴偏序关系R的哈斯图为

(2)B的最大兀：无，最小兀：无；

极大元：2,5,极小元：1,3

下界：4,下确界4；

上界：无，上确界：无

证明

/设R是集合A上的二元关系，试证明R是反对称的当且仅当尺门尺」屋，.

证明：(1)R是反对称的nRCRCu"，假定<x,y>GRnR。，则〈x,y〉GRA〈x,y〉GRCn〈x,y〉

C

©RA〈y,x>£R,因为R是反对称的，故x=y.所以〈x,y>=<x,x>GIA.即R^\R

(2)7?口7?01，0区是反对称的，若氏口氏。1，，设〈x,y〉GR并且〈y,x〉GR,则〈x,y>@R八

<x,y〉©R,=<x,y>eRnR°n<x,y>WIA,故x=y,即R是反对称的。

/如果集合A上的关系R和S是自反的、对称的和传递的，证明：HcS是A上的等价关系。

证明：(1)VaeA,7?,5自反「.<a,a>eR,<a,a>eS,

a,a>e7?nS,「・HcS自反。

(2)\/a,beA,若<a,b>eRcS,贝!Jv>£R,v>£S,

由R,S对称，所以，<b,a>eR,<b,a>eS,.\<b,a>^Rr>S,

所以HcS对称。

(3)\/a,b,ceA,若<a,b>wRcS,<b,c>eRcS,

贝!J<a,b>GR,<a,b>GS,<Z?,c>G7?,<Z?,c>GS,

由R,S传递性知，<a,c>eR,<a,c>eS,从而<a,c>eRcS,

所以，RcS传递。

综上所述，HcS是A上的等价关系。

图论部分

选择、填空及判断

/无向完全图心是（B）.

（A）欧拉图；（B）哈密顿图；（C）树；（D）非平面图。

/下列编码是前缀码的是（C）

A.{1,11,101}B.{1,001,0011}C.{1,01,001,000}D.{0,00,000}

/设T为n阶无向树，T有几条割边？（C）

A.n条B.n-2条C.n-l条D.没有

,具有4个结点的非同构的无向树的数目是（A）

A.2B.3C.4D.5

/下列编码是前缀码的是（B）

A.{0,11,1101}B.{1,01,0011}C.{1,0,01,000}D.{0,00,000）

/如下图所示各图，其中存在哈密顿回路的图是（C）o

/设A（G）是有向图6=〈V,E〉的邻接矩阵，其第i行中“1”的数目为（B）。

（A）顶点匕的度数;（B）顶点匕的出度;

（C）顶点匕的入度；（D）顶点匕的度数。

/〃阶加条边的无向连通图G,对应它的生成树丁有（A）条边。

（A）n-1（B）m-n+X（C）m-1（D）m-n-1

/有向图D如图所示，D中长度为2的通路有（D）条。

（A）8（B）9（C）10（D）11

/设连通图G有8个顶点，12条边，则G的任意一颗生成树的总边数为（A）

A.7B.8C.9D.10

/关于无向完全图k的命题中，哪个（或哪些）是真命题？（D）

IG中存在欧拉回路IIG中存在哈密顿回路

A,均不是B,只有Ic,只有nD.I和H

/设仅包含根结点的二叉树的高度为0,则高度为K的二叉树的最大结点数为（C

A.2k+1B.2k+1+1C.2k+1-1D.2k+l

/给定无向图G=<V，E>如本题图所示，下面哪个边集不是其边割集？（B）

VVV

A（%，%）,（匕，丫4）B（P4）/4^6）C.（丫4，丫7）,（丫4，%）□（匕，%）,（丫2，匕）

/一个3阶有向图的度数列是2,2,4,入度数列是2,0,2,出度数列是0,2,2

/在下图中，用避圈法构造最小生成树，边的加入顺序是AE,BC,ED,DC。

图

/无向图G有11条边，4个3度结点，其余结点均为5度结点，则G的结点数为6

/已知n个结点的无向简单图G有m条边，则G的补图中有n（n-l）/2-m条边。

/无向图G含有欧拉回路的充要条件是连通且每个结点都是偶结点。

无向图G含有欧拉通路的充要条件是连通且有且仅有两个奇结点

/无向图G的结点数n与边数m相等，2度和3度结点各2个，其余结点为悬挂点，则G的边

数m=6o

/在有向图的邻接矩阵中,第，行元素之和与第/列元素之和分别

为结点0的出度与结点切的入度

/设厂是各边带权均为。的〃阶带权图的一棵最小生成树，则W（T）=（八一1）。。

/〃阶机条边的无向连通图G,对应它的生成树T有7〃-72-1个基本回路。

（X）

/图的邻接矩阵必为对称矩阵。（X）

/当〃25时,有几个结点的完全图K”都不是欧拉图。（X）

/欧拉图中一定不存在桥；哈密顿图中一定存在割点。（X）

/有向图是强连通的，则它一定是单向连通的，也弱连通的。（V）

/哈密顿图中存在经过图中每个顶点一次且仅一次的回路。（V）

/无向图G必存在生成树。（X）

/有割点的连通图可能是哈密尔顿图。（X）

/一个n阶无向图G是二部图当且仅当G中无奇圈。（V）

计算

/已知无向简单图G有9个结点，每个结点的度数不是5就是6（注：不存在全为6度的情况）。

试讨论G的结点度数分配情况。

解题要点：由握手定理的推论知：5度结点只能是偶数个，

故度数分配情况有以下4种：

（1）2个5度结点，7个6度结点；

（2）4个5度结点，5个6度结点；

（3）6个5度结点，3个6度结点；

（4）8个5度结点，1个6度结点；

/有向图G如图1所示，问：

（1）图中v4到v3长度为2,3的路各有几条？

（2）图中vl到vl长度为3的回路有几条？

(3)该有向图是哪类连通图？

答案：(1)2,2(2)2（3）强连通图

/设有向图D如图所示，试用邻接矩阵求出求D中长度为2的通路数，并指出其中的回路数,

并判断此图属于哪种连通类型。

10001000

20103001

解：邻接矩阵A=A2=

10012010

10102001

D中长度为2的通路为11条，其中有3条是回路。该图是单向连通图，同时也是弱连通图。

/在通信中要传输字母a,b,c,d,e,f,g,它们出现的频率分别为30%,20%,15%,10%,10%,9%,6%o

设计一个传输它们的最优前缀码，并求传输100个按上述频率出现的字母所需二进制数字个数。

解题要点：以传输频率为树叶的权求最优树并分别对应前缀码即可。且传100个字母所需二进

制数字个数为W（T）=265。

/今有煤气站A,将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的

煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路

线，并求所需的总费用。

解：该问题相当于求图的最小生成树问题，此图的最小生成树为:

因此如图铺设煤气管道所需费用最小，最小费用为:

W（T）=2+2+2+2+2+2+2+3+3+4+1=25.

/世界上六大城市之间的航线距离表如下：（以100英里为一个单位）

伦敦墨西哥纽约巴黎北京东京

伦敦/553425059

墨西哥55/20577077

纽约3420/366867

巴黎25736/5160

北京50776851/13

东京5970676013/

求出连接此六个城市的最短距离的航线网。（要求给出求解过程）

解题要点：

(1)首京将本题用带权图表示(见图1)。

(2)求解此题变成为求带权图中的最小生成树问题。如选择克鲁斯卡尔算法，可给出如图2

所示的代表最短距离的航线网。

/利用Huffman算法,求带权为1,1,2,3,4,5的最优二叉树。

解答:简述Haffman算法,最优二叉树如图，W(T)=38.

证明

0100

0011

/若图G的邻接矩阵为A二，试证明图G是强连通图。

1101

1000

证明:

方法一：由图G的邻接矩阵画出图G的示意图，说明图中存在经过每个顶点至少一次的回

路，从而证明图G是强连通图。

方法二：由A,求出A2,A3,A4,进而求出可达矩阵P,也可证明图G是强连通图。

/今有6名学生要去完成3个实验，已知他们中的任何人至少与其余5个人中的三个人相互合

作。问能否将他们分成三个小组，每组两个人能相互合作，分别去完成3个实验。

解答：作无向图G=〈V,E〉,其中V由6名学生组成，E={(u,v)|u,v©V/\uWvAu与v能合作}。

则G为简单图，且由题意知6