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

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

（∨）（∨）

p∨p∧

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

（r∧）

，

s。結(jié)論：

、給定語(yǔ)句如下：是素?cái)?shù)能被2除，是數(shù)你下午有會(huì)嗎？2x+3>0素?cái)?shù)或是合數(shù)這個(gè)男孩真勇敢呀！如果，則5是數(shù)只有4是偶數(shù)，3才被2除明年5月1日是晴天圓的面積等于半徑的平方與的乘積以上10個(gè)句中，是簡(jiǎn)單命題的為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該命題公式的主析取范式中含極小項(xiàng)的個(gè)數(shù)為，主合取范式中含極大項(xiàng)的個(gè)數(shù)為B，成真賦值個(gè)數(shù)為C，成假賦值個(gè)數(shù)為DA、、、）（）1,(3)2,(4)3,(5)412、公安人員審查一件盜竊案已知的事實(shí)如下：甲或乙盜竊了錄音機(jī)若甲盜竊了錄音機(jī)，則作案時(shí)間不能發(fā)生在午夜前若乙的證詞正確，則午夜時(shí)屋里燈光未滅若乙的證詞不正確，則作案時(shí)間發(fā)生在午夜前午夜時(shí)屋里燈光滅了推理證明，誰(shuí)盜竊了錄音機(jī)。nn13、p=1，q=0，，，下列命題公式（∧）→（∧）（∧

∧r∧

s）∨→

q（∧∧r）

（

∨

s）那么）真值為）真值為）真值為；14對(duì)于下面的語(yǔ)句，只要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命題變項(xiàng)的公式，下面4個(gè)結(jié)論中，哪個(gè)是錯(cuò)誤的？（1若A的析取范式中含2

n

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

B∨，

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

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

xF（x）∧

xG（x）→

x（（x）∧Gx）27取個(gè)體域?yàn)檎麛?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正確的是；誤的是。、計(jì)算一下冪集（1）（

、證明（1）∪B=A∪、化簡(jiǎn)ABC）∩（A∪B）-（A（）∩A已知：AC，證明A=B求在到1000之不能被5和6也不能被8整的數(shù)的個(gè)數(shù)某班有個(gè)學(xué)生，其中人打籃球，12會(huì)打排球人會(huì)打籃球和排球5人打籃球和網(wǎng)球還2人打三種球而個(gè)會(huì)打網(wǎng)球的人都會(huì)打另一種指球或排球不會(huì)打這三種球的人數(shù)。設(shè)表一年級(jí)大學(xué)生的集合表二年級(jí)大學(xué)生的集合表示計(jì)算機(jī)科學(xué)系學(xué)生的集合M表數(shù)學(xué)系學(xué)生的集合T表示選修離散數(shù)學(xué)的學(xué)生的集合L表愛(ài)好文學(xué)的學(xué)生的集合表愛(ài)好體運(yùn)動(dòng)的學(xué)生的集合列各句子所對(duì)應(yīng)的集合表達(dá)式分別是：（1所有計(jì)算機(jī)科學(xué)系二年級(jí)的學(xué)生都選修離散數(shù)學(xué)A數(shù)學(xué)系的學(xué)生或者愛(ài)好文學(xué)或者愛(ài)好體育運(yùn)動(dòng)B數(shù)學(xué)系一年級(jí)的學(xué)生都沒(méi)有選修離散數(shù)學(xué)只有一、二年級(jí)的學(xué)生才愛(ài)好體育運(yùn)動(dòng)D除去數(shù)學(xué)系和計(jì)算機(jī)科學(xué)系二年級(jí)的學(xué)生外都不選修離散數(shù)學(xué)A、B、、D：①M(fèi)∪）∩；②R∩ST；③（∩）∩T=④M∪；⑤F∪；-（∪R）、設(shè)S1=｛12，…，，9｛2，4，，S3=｛，3，7，9｛3，，5｛3定在以下條件下X可與S1,中哪個(gè)集合相等（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求使得以下集合等式成立時(shí)，，，c，d應(yīng)該滿足的條件：（1，｝｛，，｝｛，b，｝=｛a，｝｛，｝=｛a，b｛b｝｛a，13計(jì)算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上所有的等價(jià)關(guān)系設(shè)｛，，3，，11，12為A上整除關(guān)系，畫(huà)出哈斯圖。畫(huà)，，c哈斯圖。RX上二元關(guān)，對(duì)于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é)果都不對(duì)24設(shè)｛1，，3義S×上等價(jià)關(guān)系，

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

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

塊，每塊含+2++++2+++⑧1⑨，；⑩<2，2>25設(shè)｛0，1是中字符構(gòu)成的長(zhǎng)度不超過(guò)的串的集合，即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①鏈；②樹(shù)；③既不是鏈，也不是樹(shù)；B、C、：④⑤0；⑥0、⑦不存在；⑧10⑨1；⑩26設(shè)｛1，2S上定義A個(gè)不同的二元關(guān)系，其中B

個(gè)等價(jià)關(guān)系，C

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

，

是E

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

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

+

、

分別表示正實(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對(duì)于給定集合A和B構(gòu)造從A到B的射函數(shù)。B=N其中，分表示整數(shù)集和自然數(shù)；A=[，2]，B=[-11]實(shí)數(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個(gè)有序?qū)?；的關(guān)系圖中有E個(gè)。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①一棵樹(shù)；②一條鏈；③以上都不對(duì)；B、C、：

，其中④

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

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

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

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

（）=0，

（b，

（c）=0，

（d，則（）中運(yùn)算A，幺元是B

，中運(yùn)算*

；（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個(gè)代數(shù)，其中凡的真子代數(shù)有B個(gè)；含個(gè)平凡的子代數(shù)。（2積代數(shù)V1×有D個(gè)素，其幺元是E。A、B、、D①0②；③2；④3；⑤；⑥；⑦6E：⑧，5>；⑨，；⑩<36>、設(shè)S=｛a，S上以定義A個(gè)二元運(yùn)算，其中有4個(gè)算f1f2，f4，其運(yùn)算表如下：

aaa

baa

a

bbaf1

f2

a

baa

aaa

bbbf3

f4則只有滿足交換律，C滿足冪等律D有幺元E有零元A；②；③162；B、C、：⑤和；、；f3f4⑧；；；、設(shè)S=｛，2，，9，10下面定義的二元運(yùn)算*否為上的二元運(yùn)算？（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í)數(shù)集合。分別對(duì)下述小題討論

運(yùn)算是否可交換、可結(jié)合，并求幺元和所有可逆元素的逆元。、某二進(jìn)制通信編碼由個(gè)據(jù)位、x2、x3、和校驗(yàn)位、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，

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

7

(xi)

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

位。A①半群，但不是群；②群；③環(huán)，但不是域；④域；⑤前都不對(duì)；B、C、：①1②；③3；④4；⑤；⑥；⑦7⑧；、對(duì)以下定義的集合和運(yùn)算判斷它們是不是代數(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：①半群，但不是獨(dú)異點(diǎn)；②是獨(dú)異點(diǎn)，但不是群；③群；④環(huán)，但不是域；⑤域；⑥格，但不是布爾代數(shù)；⑦布爾代數(shù)；⑧代數(shù)系統(tǒng)，但不是以上7種⑨不是代數(shù)系統(tǒng)；10圖給一個(gè)格L，則L是A元；L是B；補(bǔ)元是C，a的元是D，的元是。：①；②；：③分配格；④有補(bǔ)格；⑤布爾格；⑥以上都不對(duì)；C、、E：⑦不存在；和；⑨；⑩c；、設(shè)B，∧，∨，′，01>布爾代數(shù)，，bB，公式f為b∧（a∨（′∧（∨′）在B中化簡(jiǎn)f；在B中式a∧′∨a′b）=0成立條件是什么？12以定義的集合和運(yùn)算判斷它們能否構(gòu)成代數(shù)系統(tǒng)？如果能說(shuō)是構(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：①半群，不是獨(dú)異點(diǎn)；②獨(dú)異點(diǎn)，不是群；③群；④環(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①群；②半群，不是群；：③有限；④無(wú)限；：⑤Klein群⑥置換群；循環(huán)群；D、E：⑧；⑨1和；⑩；2n2n14）L，∧，∨′，01>是布爾代數(shù)，則L的運(yùn)算∧和A，運(yùn)算∨的幺元是，零元是C，小的子布爾代數(shù)是由集合D構(gòu)；（2在布爾代數(shù)L中表達(dá)式（∧）∨（∧∧c）∨（b∧c）的等價(jià)式是E；A適合德摩律、冪等律、消去律和結(jié)合律；適合德摩律、冪等律、分配律和結(jié)合律；適合結(jié)合律、交換律、消去律和分配律；B、C④0⑤；：⑥｛1｛0，：⑧b（∨c（∧）∨（∧′（∨）∧（∨∨c）∧（∨c15下列各集合對(duì)于整除關(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)成群，其中

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

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

個(gè)；個(gè)；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é)組成員，王、李、趙、陳為生物組成員；問(wèn)在以上中情況下能否各選出3名兼職的組長(zhǎng)？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畫(huà)出完全二部圖K13，K24，K22。24完全二部圖Krs，邊數(shù)為，配數(shù)

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