離散數(shù)學(xué)題庫

試題總匯數(shù)理邏輯部分、判斷下列句子中哪些是命題素數(shù)血是黑色的明年10月是晴天被2整這朵花多好看呀！明天下午有會嗎？請關(guān)上門！X+y>5地球外的星球上也有人、將下列命題符號化是偶數(shù)素數(shù)和偶數(shù)李芳學(xué)過英語或日語如果角A和B是對頂角，則角A等角B（5李平雖然聰明，但不用功李平不但聰明，而且用功小王是游泳冠軍或者百米賽跑冠軍小王現(xiàn)在在宿舍或者在圖書館選小王或者小李中的一人當(dāng)班長如果我上街，我就去書店看看，除非我很累（）如果明天天氣好，我們?nèi)ソ加?。否則，不去郊游（）你愛我，我就嫁給你、判斷下列命題公式是否等值

（∨）（∨）

p∨p∧

qq、驗證下列等值式→（q→）（p∧）→（p∧）∨（∧）、用等值演算法解決下面問題：A、B、、D人米競賽。觀眾甲、乙、丙預(yù)報比賽的名次為，（1甲C一B第）乙C第D第）A第，第。比賽結(jié)束后發(fā)現(xiàn)甲、乙、丙每人報告的情況都是給對一半。試問，實際名次如何？、求下面命題公式的主析取范式和主合取范式（1p∨）→）→、利用真值表求主析取范式和主合取范式（1∧q）∨r、邏輯推理證明（1前提→r，→，∨。論r∨。（2前提p∨qp→，→t，→，。結(jié)論（3前提p→（→r→p。結(jié)論：→r。（4前提p→（

（r∧）

，

s。結(jié)論：

、給定語句如下：是素數(shù)能被2除，是數(shù)你下午有會嗎？2x+3>0素數(shù)或是合數(shù)這個男孩真勇敢呀！如果，則5是數(shù)只有4是偶數(shù)，3才被2除明年5月1日是晴天圓的面積等于半徑的平方與的乘積以上10個句中，是簡單命題的為A是復(fù)合命題的為B，是真命題為C，是假命題的為D，真值待定（真值客觀存在只是現(xiàn)在不知道）的命題為E：①（1：①（）②（2：①（27（（）：①（11：①（②9）③10判斷公式類型（1∧q）→（∨）（2

）

→）∧（q）（3

（p→）∧q（∧）→（p∨）（p∨）→（q∧q）∧）（7→q）→）

（8∧q）∨（∧

）（9

（∨q∨）

（

∧

q

）（∧q）r11、定命題公式如下→）→（∨q該命題公式的主析取范式中含極小項的個數(shù)為，主合取范式中含極大項的個數(shù)為B，成真賦值個數(shù)為C，成假賦值個數(shù)為DA、、、）（）1,(3)2,(4)3,(5)412、公安人員審查一件盜竊案已知的事實如下：甲或乙盜竊了錄音機若甲盜竊了錄音機，則作案時間不能發(fā)生在午夜前若乙的證詞正確，則午夜時屋里燈光未滅若乙的證詞不正確，則作案時間發(fā)生在午夜前午夜時屋里燈光滅了推理證明，誰盜竊了錄音機。nn13、p=1，q=0，，，下列命題公式（∧）→（∧）（∧

∧r∧

s）∨→

q（∧∧r）

（

∨

s）那么）真值為）真值為）真值為；14對于下面的語句，只要4＜，就有3＞只要4＜，就有3≤只有4＜，才有3＞只有4＜，才有3≤除非4＜，否則3＞4≥僅當(dāng)3≤4＜當(dāng)且當(dāng)3＞則，他們的真值是（）（2）（）（）（5（6（）。15設(shè)A是n命題變項的公式，下面4個結(jié)論中，哪個是錯誤的？（1若A的析取范式中含2

n

個極小項，則A是重言式若A的合取范式中含2個大項，則A是矛盾式若A的析取范式中不含任何極小項，則A主析取范式為若A的合取范式中不含任何極大項，則A主合取范式為16已知命題公式A含有3個題變項其成真賦值為000，，，。則A的析取范式為，合取范式為。17判斷下列語句是否為命題，如是命題請指出是簡單命題還是復(fù)合命題，并討論真值（1是理數(shù)被2整現(xiàn)在開會嗎？＞0這朵花真好看呀！素數(shù)當(dāng)且僅當(dāng)三角形有3邊血是黑色的當(dāng)且僅當(dāng)太陽從東方升起年月1日天氣晴朗太陽系以外的星球上有生物小李在宿舍里全體起立2的倍數(shù)或是3的數(shù)偶數(shù)且是奇數(shù)李明與王華是同學(xué)藍(lán)色和黃色可以調(diào)配成綠色18將下列命題符號化，并討論其真值如果今天是號，則明天是2號如果今天是號，則明天是3號19設(shè)AB、為意的命題公式（1已知A∨

B∨，

B嗎已知A∧B∧，B嗎？已知B問B嗎？20設(shè)一個符合如下要求的室內(nèi)照明控制線路房的門外門及床頭分別裝有控制同一個電燈的個關(guān)A、C。當(dāng)且僅當(dāng)一個開關(guān)的鍵向上或3個關(guān)的鍵都向上時電燈亮。則F邏輯關(guān)系式可化簡為。（1∨∨（2A∨∨∨（A∧B）（）∨∨（AC（4）C∨（∧）21將下列語句用謂詞表達(dá)式符號化素數(shù)且是偶數(shù)如果2大于3，則2大于凡是有理數(shù)均可表成分?jǐn)?shù)有的有理數(shù)是整數(shù)沒有不吃飯的人素數(shù)不全是奇數(shù)一切人都不一樣高有的自然數(shù)無先驅(qū)數(shù)有些人喜歡所有的花任何金屬都可以溶解在某種液體中凡是對頂角都相等22指出下列各合式公式中的指導(dǎo)變項、量詞的轄域、個體變項的自由出現(xiàn)和約束出現(xiàn)（1（F（x）→

yH（x，yF（x）∧（x，y）xy（R（，）∨L（x，y∧Hx，y）23給定解釋I下：），3}I）中特定元素I函數(shù)f）為f），f3）=2謂詞（x）為F2）=0，F(xiàn)（3；（x，y）為（ij）=1，i，j=2，；Lx，y為L22）L（3，）=1；L（23=L3，）=0在解釋I下求下列各式的值。（1（F（x）∧（x，（2

x（（fx）∧（，f））（3

yLx，）24求下列公式的前束范式（1（x）∧G）（2（x）∨G）（3（x）→G）（4

xF（x）→G（x）25設(shè)（x是Gx愛糖。有人給出語句“不是所有人都愛吃糖”的謂詞表達(dá)式：x（（x）∧G（x）x（（x）→G（x）（3

x（（x）∧Gx）（4F（x）∧G（x）正確的答案是。26給出解釋I，使下面兩個公式在釋I下為假，從而說明這兩個公式都不是永真式（1（F（x）∨Gx）→（（x）∨（x）（2

xF（x）∧

xG（x）→

x（（x）∧Gx）27取個體域為整數(shù)集，給定下列公式（1（2

y（x*y=0）y（x*y=1）（3（x*y=2（4x–=）（5x–yy+x（6xy（x*y=y）（7（x*y=x）（8

xy（x+y=2y）在上面的公式中，真命題的為A，假命題的為B。A①1③（1B①③（1集合部分、下列命題（1正確的是；誤的是。、計算一下冪集（1）（

、證明（1）∪B=A∪、化簡ABC）∩（A∪B）-（A（）∩A已知：AC，證明A=B求在到1000之不能被5和6也不能被8整的數(shù)的個數(shù)某班有個學(xué)生，其中人打籃球，12會打排球人會打籃球和排球5人打籃球和網(wǎng)球還2人打三種球而個會打網(wǎng)球的人都會打另一種指球或排球不會打這三種球的人數(shù)。設(shè)表一年級大學(xué)生的集合表二年級大學(xué)生的集合表示計算機科學(xué)系學(xué)生的集合M表數(shù)學(xué)系學(xué)生的集合T表示選修離散數(shù)學(xué)的學(xué)生的集合L表愛好文學(xué)的學(xué)生的集合表愛好體運動的學(xué)生的集合列各句子所對應(yīng)的集合表達(dá)式分別是：（1所有計算機科學(xué)系二年級的學(xué)生都選修離散數(shù)學(xué)A數(shù)學(xué)系的學(xué)生或者愛好文學(xué)或者愛好體育運動B數(shù)學(xué)系一年級的學(xué)生都沒有選修離散數(shù)學(xué)只有一、二年級的學(xué)生才愛好體育運動D除去數(shù)學(xué)系和計算機科學(xué)系二年級的學(xué)生外都不選修離散數(shù)學(xué)A、B、、D：①M∪）∩；②R∩ST；③（∩）∩T=④M∪；⑤F∪；-（∪R）、設(shè)S1=｛12，…，，9｛2，4，，S3=｛，3，7，9｛3，，5｛3定在以下條件下X可與S1,中哪個集合相等（1若X∩S5=

，則A（2若XX∩S2=則B（3若XX，則（4若X-S3=

，則D（5若X

但X

，A、B、、D：①或S3②X=或者；X=S1，S2或；④X與其中何集合都不等；X=S2⑥；X=S3或；⑧或S410設(shè)ABC任意集合，判斷下述命題是否恒真，如果恒真給出證明，否則舉出反例。（1）A∪

AB=AB=A（C）（AB-（∩C（AB）∪（BA）B、設(shè)AB為合，試確定下列各式立的充分必要條件：（1）A=BA=B-AAB=AB12求使得以下集合等式成立時，，，c，d應(yīng)該滿足的條件：（1，｝｛，，｝｛，b，｝=｛a，｝｛，｝=｛a，b｛b｝｛a，13計算A∩BAB、、A

B，bB=，d｝A={{a}cb｝}｛a，（3）｛x|x∈∧B=｛x∈∧≥｝｛x|x∈∧x<1｛|x∈∧｝｛x|x∈∧x<0｛|x∈∧≥｝-1-114設(shè)A|，P（A）|，P（A∪）=256，求：||A∩B，A-B，AB設(shè)｛，：P（A）×設(shè)A、B、、D為意集合，判斷以下等式是否成立，若成立給與證明，否則，舉出反例。（AB）×C∩D=（A∩C）×（B∩D）（AB）×C∪D=（A∪C）×（B∪D）（A-）×）A-）×（D（AB）×C=AC）×BD17設(shè)、G是N上關(guān)系，其定義為：F=<x，y>|x，y∈N∧=x｛<x，y>x，∈∧y=x+1求：G、

GG

F、↑，2｛，2]設(shè)F=>，｛F，↑｛a｝]。設(shè)A=｛a，b，R=<a，b>，<b，，<bc>，<c，出R、（R（（）關(guān)系圖。設(shè)｛，，3出A上所有的等價關(guān)系設(shè)｛，，3，，11，12為A上整除關(guān)系，畫出哈斯圖。畫，，c哈斯圖。RX上二元關(guān)，對于x∈義集合：（）={y|xRy}顯然R（）。果X={-4，-3-2，-101，，，4}且令｛，y>，∈∧<y｛，y>，∈∧-1<<｛，y>，∈∧≤y則下列集合滿足R1）=AR2）=BR3）R1）=DR2-1）A、B、、D：①；｛，-3-2，｛，-1｛，0，⑤｛，｛1，23，，｛0，2，⑨｛，2，34以上結(jié)果都不對24設(shè)｛1，，3義S×上等價關(guān)系，

<a，b><c，∈有<a，b><c，d>

a+d=b+c則由產(chǎn)了S×S的一個劃分。在該劃分中共有A個劃分塊，其中最大的塊有B個素，并且含有元素C。小的劃分塊有有E個元素。A、B、D、：①1②；③3；④4；⑤；⑥；⑦9C：

塊，每塊含+2++++2+++⑧1⑨，；⑩<2，2>25設(shè)｛0，1是中字符構(gòu)成的長度不超過的串的集合，即F=

，0，1，，01…，1111中

表示空串。在F上義偏序關(guān)系R

x，y∈F，有x，y>∈

x是y的前綴。例如，是的前綴，但不是001前綴。（1偏序<F的哈斯圖是A；<FR>的小元是B；<FR>的大元是（4）G

F，｛101的小上界是D，最大下屆是E

。A①鏈；②樹；③既不是鏈，也不是樹；B、C、：④⑤0；⑥0、⑦不存在；⑧10⑨1；⑩26設(shè)｛1，2S上定義A個不同的二元關(guān)系，其中B

個等價關(guān)系，C

個偏序關(guān)系，Is是

，

是E

。A、B、：①1②；③3；④4；⑤；⑥16D、E：⑦等價關(guān)系但不是偏序關(guān)系；⑧偏序關(guān)系但不是等價關(guān)系；⑨等價關(guān)系和偏序關(guān)系；⑩既不是等價關(guān)系也不是偏序關(guān)系；27下面給定個函數(shù)，其中單射而非滿射的有A，射而非單射的有B雙射的有，既不單射，又不滿射的有。

，設(shè)R為數(shù)集合Z為數(shù)集合

+

、

分別表示正實數(shù)和正整數(shù)集合。①f：RR，f（）-x+2x-1②f：R→，fx）=lnx；③f：R→，f（x）=

，

表示不大于x最大整數(shù)；④f：RR，f（）=2x+1；⑤f：→

，f（）

x

x28對于給定集合A和B構(gòu)造從A到B的射函數(shù)。B=N其中，分表示整數(shù)集和自然數(shù)；A=[，2]，B=[-11]實數(shù)區(qū)間29）S=2為S上的二元關(guān)系，且。如果R=Is，則A的小于等于關(guān)系，則B；果R=Es則C。（2設(shè)有序?qū)Γ?>與序<，2x+y>等，則x=D，A、B、：①x與y可意選擇或；②x=1，；③x=1y=12x=y=2④，；⑤x=y=1或；x=1，；，y=1D、E：⑧3⑨；⑩30設(shè)，2，，，為上關(guān)系，其關(guān)系矩陣是

；如果R是。AA+++AA+++

，則（）的系表達(dá)式是AdomR=B；；R中D個有序?qū)?；的關(guān)系圖中有E個。A①<1，，<1，，<1，，，，<4，②｛<1，1><1，，<2，1>，<4，，，4>B、C③｛，2，34｛，2，｛，｛，，4D、E：⑦1⑧；⑨6；⑩31設(shè)S=｛，2，…，10上的整除關(guān)系，哈斯圖是A最大元是B，最小元是，最小上界是D，大下界是E。A①一棵樹；②一條鏈；③以上都不對；B、C、：

，其中④

；⑤1；；⑦，7，，10⑧6⑨0⑩不存在32設(shè)R的系如所示，試給出（（（）的關(guān)系圖。bc33畫出下列集合關(guān)于整除關(guān)系的哈斯圖。｛1，2，，4，6，8，12｝｛1，2，，8，｝34設(shè)｛，｛，1求（）和；構(gòu)造一個從（A）到B的射函數(shù)。代數(shù)系統(tǒng)部分、設(shè)Z=｛|x∈∧x>0*表示求兩個數(shù)的最小公數(shù)的運算，則（14*6=A；*Z上B；對于*算的幺元是C，零元是D；（4在

中；A24；②12B③只滿足交換率；④只滿足結(jié)合律；⑤滿足交換率、結(jié)合律和冪等律；C、：0⑦1；⑧不存在；E：⑨不存在逆元；⑩只有唯一的逆元、在有理數(shù)集合上義二元運*x*y=x+y-xy

x，y∈Q有則（）（）=A，=B。*Q上C；關(guān)于*幺元是D；Q中足E；A、B：①；②；③；：④可結(jié)合的；⑤不可結(jié)合的；：⑥；⑦；：⑧所有的元素都有逆元；⑨只有唯一的逆元；⑩x∈，x1時，有元、設(shè)V1=<S1>*>，其中S1=，，c，d，12，3}。和*由運算表1和出。

定義同態(tài)1→，

（）=0，

（b，

（c）=0，

（d，則（）中運算A，幺元是B

，中運算*

；（2

是，V1在

下的同態(tài)像是E

；A、：滿足交律，不滿足結(jié)合律；②不滿足交換律，滿足結(jié)合律；③滿足交換律，滿足結(jié)合律；Ba；⑤；：⑥單同態(tài)；⑦滿同態(tài)；⑧以上兩者都不是；：⑨，*>；⑩<｛，、設(shè)V1=<｛，21>，其中xy表取x和y之較大的數(shù)V2=<56*，6>其中x*y表取x和之較小的數(shù)。（1）含A個代數(shù)，其中凡的真子代數(shù)有B個；含個平凡的子代數(shù)。（2積代數(shù)V1×有D個素，其幺元是E。A、B、、D①0②；③2；④3；⑤；⑥；⑦6E：⑧，5>；⑨，；⑩<36>、設(shè)S=｛a，S上以定義A個二元運算，其中有4個算f1f2，f4，其運算表如下：

aaa

baa

a

bbaf1

f2

a

baa

aaa

bbbf3

f4則只有滿足交換律，C滿足冪等律D有幺元E有零元A；②；③162；B、C、：⑤和；、；f3f4⑧；；；、設(shè)S=｛，2，，9，10下面定義的二元運算*否為上的二元運算？（1x*y=（，x與y的大公約數(shù)；x*y=lcmx，y與最小公倍數(shù)；x*y大于等于xy最小整數(shù)；x*y=maxx，x*y質(zhì)數(shù)P的數(shù)，其中x≤py、設(shè)V<R*

>是代數(shù)系統(tǒng)，其中為非零實數(shù)集合。分別對下述小題討論

運算是否可交換、可結(jié)合，并求幺元和所有可逆元素的逆元。、某二進(jìn)制通信編碼由個據(jù)位、x2、x3、和校驗位、x6、x7構(gòu)，它們的關(guān)系如下：；x2；x7=x1x3x4；其中為或算。（1設(shè)S為所有滿足上述關(guān)系的碼字的集合，且x，y∈S，有x

y=(x1

y1,x2

y2，…

y7)，那么<S，

>是一個。（2設(shè)x，y∈S，定義H（，）

7

(xi)

，那么當(dāng)x≠時，（，）≥。i（3使用該種碼可查出接收碼中包含的所有kC位錯誤。（4使用該種碼可糾正接收碼中包含的所有kD位錯誤。（5如果接收到，知有一位出錯，那么出錯位是第

位。A①半群，但不是群；②群；③環(huán)，但不是域；④域；⑤前都不對；B、C、：①1②；③3；④4；⑤；⑥；⑦7⑧；、對以下定義的集合和運算判斷它們是不是代數(shù)系統(tǒng)。如果是，是哪一種？（1）｛1，，1/3，，，為普通乘法，則S1是A；（2）｛，a2，，an2，aiR，i=1，…，n，

ai，aj∈，aiaj=ai則S2是B；｛，1為普通乘法，則是C；｛，2，，6為整除關(guān)系，則S4是D；｛，1、*別為模2加和乘法，則是E。A、B、、D：①半群，但不是獨異點；②是獨異點，但不是群；③群；④環(huán)，但不是域；⑤域；⑥格，但不是布爾代數(shù)；⑦布爾代數(shù)；⑧代數(shù)系統(tǒng)，但不是以上7種⑨不是代數(shù)系統(tǒng)；10圖給一個格L，則L是A元；L是B；補元是C，a的元是D，的元是。：①；②；：③分配格；④有補格；⑤布爾格；⑥以上都不對；C、、E：⑦不存在；和；⑨；⑩c；、設(shè)B，∧，∨，′，01>布爾代數(shù)，，bB，公式f為b∧（a∨（′∧（∨′）在B中化簡f；在B中式a∧′∨a′b）=0成立條件是什么？12以定義的集合和運算判斷它們能否構(gòu)成代數(shù)系統(tǒng)？如果能說是構(gòu)成哪一種代數(shù)系統(tǒng)？｛，，，…，+為通加法，則是A；｛1/20為普通乘法，則S2是B；｛，1，，，為意給定的正整數(shù)，且≥，*為模乘，加法，則S3是；｛，1，，3為于等于關(guān)系，則是D；S5=Mn（R為陣加法，則S5是；A、B、、D：①半群，不是獨異點；②獨異點，不是群；③群；④環(huán)，不一定是域；⑤域；⑥格，不是布爾代數(shù)；⑦布爾代數(shù)；⑧代數(shù)系統(tǒng)，不是以上7種⑨不是代數(shù)系統(tǒng)；

為模13）G=｛0，，2

為模乘法，則<，

>構(gòu)成A；（2若

為模加法，則<G，

是階群，且是。G中2階是D，4階是。A①群；②半群，不是群；：③有限；④無限；：⑤Klein群⑥置換群；循環(huán)群；D、E：⑧；⑨1和；⑩；2n2n14）L，∧，∨′，01>是布爾代數(shù)，則L的運算∧和A，運算∨的幺元是，零元是C，小的子布爾代數(shù)是由集合D構(gòu)；（2在布爾代數(shù)L中表達(dá)式（∧）∨（∧∧c）∨（b∧c）的等價式是E；A適合德摩律、冪等律、消去律和結(jié)合律；適合德摩律、冪等律、分配律和結(jié)合律；適合結(jié)合律、交換律、消去律和分配律；B、C④0⑤；：⑥｛1｛0，：⑧b（∨c（∧）∨（∧′（∨）∧（∨∨c）∧（∨c15下列各集合對于整除關(guān)系都構(gòu)成偏序集，判斷哪些偏序集是格？｛1，2，4，｛1，2，6，｛1，2，4，6，9，18｛1，2，，216設(shè)｛，2，3，，A

>構(gòu)成群，其中

為集合的對稱差。（1求解方程｛1｝

｛3，5（2令｛1，由B成的循環(huán)子群<B>；17設(shè)｛，2，510，22，110｝是110的因子集，>構(gòu)成偏序集，其中≤為整除關(guān)系。畫出偏序集<A的哈斯圖；說明該偏序集是否構(gòu)成布爾代數(shù)，為什么？18在圖所的個有界格中哪些元素有補元？如果有，請指出該元素的所有的補元。圖論部分，，，323，，4）能成為圖的度數(shù)序列嗎？為什么（2已知圖有10條3頂點，其余頂點的度數(shù)均小于等于，問中少有多少個頂點？為什么？）出個頂點條邊的所有可能非同構(gòu)的無向簡單；（2畫出頂點條邊的所有可能非同構(gòu)的有向簡單圖；、給定下列各圖：G1=<V1，，其中V1=（，，c，，E1={（，e}G2=<V2，，其中V2=V1，E2={（，b）}；（3）G3=<V3，E3>，其中，V3=V1E3={（，b）}（，，中，V4=V1，E4={<a，<b，，，，，<d，a>，<de>}；（5）G5=<V5，E5>，其中，V5=V1，b>，<a，，<b，<c，，<d，e>}（6）G6=<V6，E6>，其中，V6=V1，，，b>，，，c>，，d>}在以上圖中A為單圖B為重圖。A①1③（1B①4、給定下列各頂點度數(shù)序列：（2，2，，2，2（1，1，，2，3（1，1，，2，2（0，1，，3，3（1，3，，4，5以上5組中A可構(gòu)成無向簡單圖的度數(shù)序列。A①11、完全圖K4的有非同構(gòu)的生成子圖中，0條的有A個；條邊的有B個邊的有個條邊的有個；條的有個；5條的有F個；邊的有G個；A、B、、D、、：①0②；③2；④3；⑤；⑥；設(shè)G為無向圖，每個頂點的度數(shù)不是5就，證明中少有5個度頂點或者至少個頂點。畫出階條邊的所有非同構(gòu)的無向單圖。下列各組數(shù)中哪些能構(gòu)成無向圖的度數(shù)列？哪些能成無向簡單圖的度數(shù)列？，1，1，23；，2，2，22；，3，3，3，2，3，45；，3，3，3、設(shè)有向簡單圖D的數(shù)列為223，3其中入度列為00，，3，出度列為。設(shè)D是有向簡單圖，度數(shù)列為，3，，它的入度列能為11，1嗎？（能或者不能）下面各無向圖中有幾個頂點？條邊，每個頂點都是度點；條邊，4度點，其余都是度頂點；條邊，各頂點的度數(shù)是相同的；一個n≥）無向簡單圖G中為數(shù)已知G中有r個數(shù)度頂點，的補圖G中有幾個奇數(shù)度頂點？畫出K4的所有非同構(gòu)的字圖，其中有幾個是生成子圖？生成子圖中有幾個是連通圖？14出3階向完全圖所有非構(gòu)的子圖其中有幾個是生成子圖？生成子圖中又有幾個是自補圖？設(shè)G1、均為4階向簡單圖，它們有兩條邊，它們能彼此均非同構(gòu)嗎？為什么？在K6的上涂上紅色或藍(lán)色。明對于任意一種隨意的涂法，總存在紅色或藍(lán)色K3。（1）非同構(gòu)的無向的自補圖有A（2非同構(gòu)的無向的5階補圖有BA、B：①；②；③2；④；給定有向帶權(quán)圖如圖所示P175d

個；個；b

g

f圖中b到的最短路徑的權(quán)為A；b到d的短路徑的權(quán)為B；到e最短路徑的權(quán)為；到的短路徑的權(quán)為D；A、B、、D①4②；③6；④7；⑤；⑥；⑦1019某中學(xué)有課外小組：物理組、化學(xué)組、生物組。今有張王、李、趙、同。若已知：（1張、王為物理組成員，張、李、趙為化學(xué)組成員，李、趙、陳為生物組成員；（2張為物理組成員，王、李、趙為化學(xué)組成員，王、李、趙、陳為生物組成員；（3張為物理組和化學(xué)組成員，王、李、趙、陳為生物組成員；問在以上中情況下能否各選出3名兼職的組長？20在圖8-17所的各圖中，A為歐拉圖，為哈密頓圖。A、B：①（a④（b21圖所示的各圖中二部圖的為A二部圖中存在完美匹配的是B，它的匹配數(shù)是。A、B：①（a（b（（d（（f⑦（acC：①1；2；③；④422圖8-19所示的平面嵌入中，面數(shù)A，次數(shù)最高的面的次數(shù)為B，次數(shù)最低的面的次數(shù)為，次數(shù)為。A、B、：①5②；③7；④8；⑤；⑥10⑦；⑧1；D：①；②26③2823畫出完全二部圖K13，K24，K22。24完全二部圖Krs，邊數(shù)為，配數(shù)

。今有工人甲、乙、丙去完成三項任務(wù)a、b、。已知甲能勝任a、bc三任；乙能勝任、b兩任務(wù)；丙能勝任bc兩任。你能出一種安排方案，使每個工人各去完成一項他們能勝任的任務(wù)嗎？畫一個無向歐拉圖，使它具有：偶數(shù)個頂點，偶數(shù)條邊；奇數(shù)個頂點，奇數(shù)條邊；偶數(shù)個頂點，奇數(shù)條邊；奇數(shù)個頂點，偶數(shù)條邊；27畫一個無向圖，使它是：是歐拉圖，是哈密頓圖；是歐拉圖，不是哈密頓圖；不是歐拉圖，是哈密頓圖；不是歐拉圖，不是哈密頓圖；28今有、b、c、、、f、個人，已知如下事實：會講英語；：會講英語和漢語；：會講英語、意大利語和俄語；：會講日語和漢語；：會講德語和意大利語；：會講法語、日語和俄語；：會講法語和德語；試問人要圍成一圈如排座位能每人都能和他身相鄰人交談？29彼得森圖如圖所。證明它不是二部圖，也不是歐拉圖，更不是平面圖。30證明圖所圖是密頓圖，但不是平面圖。31圖8-25所示圖G為面圖，試給出它的一個平面嵌入，它是極大平面圖嗎？32）全圖Kn（≥）都是歐拉圖，個命題真值為A；完全圖Kn（≥）是哈密頓圖，這命題真值為B完全二部圖（≥，≥）都是歐拉圖