2005年研究生期末試題(120分鐘)《圖論及其應(yīng)用》一、填空(15分，每空1分)已知圖G有10條邊，4個(gè)度數(shù)為3的頂點(diǎn)，其余頂點(diǎn)的度數(shù)均小于2，則G中至少有個(gè)頂點(diǎn).m條邊的簡(jiǎn)單圖G中所有不同的生成子圖(包括G和空?qǐng)D)的個(gè)數(shù)為4個(gè)頂點(diǎn)的非同構(gòu)的簡(jiǎn)單圖有個(gè).圖G1的最小生成樹各邊權(quán)值之和為5、若W是圖G中一條包含所有邊的閉通道，則W在這樣的閉通道中具有最短長(zhǎng)度的充要條件是：每一條邊最多重復(fù)經(jīng)過次；在G的每一個(gè)圈上，重復(fù)經(jīng)過的邊的數(shù)目不超過圈的長(zhǎng)度的6、5階度極大非哈密爾頓圖族有.7、在圖G2中，圖的度序列為(44443322)，頻序列為(422)，獨(dú)立數(shù)為3，團(tuán)數(shù)為4，點(diǎn)色數(shù)為4，邊色數(shù)為4，直徑為3.圖圖G2二、選擇(15分)(1)下列序列中，能成為某簡(jiǎn)單圖的度序列的是(C)(A)(54221)(B)(6654332)(C)(332222)（2）已知圖G有13條邊，2個(gè)5度頂點(diǎn)，4個(gè)3度頂點(diǎn)，其余頂點(diǎn)的的度數(shù)為2，則圖G有(A)個(gè)2度點(diǎn)。(A)2(B)4(C)8(3)圖G如(a)所示，與G同構(gòu)的圖是(C)(4)下列圖中為歐拉圖的是(B),為H圖的是(AB),為偶圖的是(BC).5．下列圖中可1-因子分解的是(B)三、設(shè)和分別是圖G的最大度與最小度，求證：(10分).證明：四、正整數(shù)序列是一棵樹的度序列的充分必要條件是(10分).證明：結(jié)論顯然 設(shè)正整數(shù)序列滿足，易知它是度序列。設(shè)G是這個(gè)度序列的圖族中連通分支最少的一個(gè)圖，知m=.假設(shè)G不連通，則，且至少有一個(gè)分支含有圈C，否則，G是森林，有m=矛盾！從C中任意取出一條邊。并在另一分支中任意取出一條邊，作圖則的度序列仍然為且，這與G的選取矛盾！所以G是連通的，G是樹。即一棵樹的度序列。五、求證：在簡(jiǎn)單連通平面圖G中，至少存在一個(gè)度數(shù)小于或等于5的頂點(diǎn)(10分).證明：若不然，這與G是簡(jiǎn)單連通平面圖矛盾。六、證明：(1)若G恰有兩個(gè)奇度點(diǎn)u與v，則u與v必連通；(2)一棵樹至多只有一個(gè)完美匹配(10分).證明；(1)因?yàn)槿我庖粋€(gè)圖的奇度點(diǎn)個(gè)數(shù)必然為偶數(shù)個(gè)，若G恰有兩個(gè)奇度點(diǎn)u與v，且它們不連通，那么就會(huì)得出一個(gè)連通圖只有一個(gè)奇度點(diǎn)的矛盾結(jié)論。所以若G恰有兩個(gè)奇度點(diǎn)u與v，則u與v必連通。(2)若樹有兩個(gè)相異的完美匹配，則且中的每個(gè)頂點(diǎn)的度數(shù)為2，則中包含圈，這與是數(shù)矛盾！七、求圖G的色多項(xiàng)式(15分).圖圖G解：圖G的補(bǔ)圖如圖，則，其中，，，；，其中，，。八、求圖G中a到b的最短路(15分).vv11v463429a8v22v56b7242v3v6圖G9解1.A1={a}，t(a)=0，T1=Φ2.3.m1=1,a2=v3,t(v3)=t(a)+l(av3)=1(最小)，T2={av3}2.A2={a,v3},3.m2=1,a3=v1,t(v1)=t(a)+l(av1)=2(最小)，T3={av3,av1}2.A3={a,v3,v1},3.m3=3,a4=v4,t(v4)=t(v1)+l(v1v4)=3(最小)，T4={av3,av1,v1v4}2.A4={a,v3,v1,v4}，b1(4)=v2，b2(4)=v2，b3(4)=v2,b4(4)=v53.m4=4,a5=v5,t(v5)=t(v4)+l(v4v5)=6(最小)，T5={av3,av1,v1v4,v4v5}2.A5={a,v3,v1,v4,v5}，b1(5)=v2，b2(5)=v2，b3(5)=v2,b4(5)=v2,b5(5)=v23.m5=4,t(v2)=t(v4)+l(v4v2)=7(最小)，T6={av3,av1,v1v4,v4v5,v4v2}2.A6={a,v3,v1,v4,v5,v2},b2(6)=v6,b4(6)=b，b5(6)=v6，b6(6)=v63.m6=6,a7=v6,t(v6)=t(v2)+l(v2v6)=9(最小)，T7={av3,av1,v1v4,v4v5,v4v2,v2v6}2.A7={a,v3,v1,v4,v5,v2,v6},b4(7)=b，b5(7)=b，b7(7)=b3.m7=7,a8=b,t(b)=t(v6)+l(v6b)=11(最小)，T8={av3,av1,v1v4,v4v5,v4v2,v2v6,v6b}于是知a與b的距離d(a,b)=t(b)=11由T8導(dǎo)出的樹中a到b路就是最短路。2006研究生圖論期末試題(120分鐘)一、填空題(15分，每空1分)1、若兩個(gè)圖的頂點(diǎn)與頂點(diǎn)之間，邊與邊之間都存在對(duì)應(yīng)，而且它們的關(guān)聯(lián)關(guān)系也保持其關(guān)系，則這兩個(gè)圖同構(gòu)。2、完全圖的生成樹的數(shù)目為；階為6的不同構(gòu)的樹有棵。3、設(shè)無向圖有12條邊，已知中度為3的結(jié)點(diǎn)有6個(gè)，其余結(jié)點(diǎn)的度數(shù)均小于3，則中至少有個(gè)結(jié)點(diǎn)。4、具有5個(gè)結(jié)點(diǎn)的自補(bǔ)圖的個(gè)數(shù)有。5、已知圖的鄰接矩陣，頂點(diǎn)集合，則由到的途徑長(zhǎng)度為2的條數(shù)為。6、若為歐拉圖，則n=；若僅存在歐拉跡而不存在歐拉回路，則n=。7、無向完全圖(n為奇數(shù))，共有條沒有公共邊的哈密爾頓圈。8、設(shè)是具有二分類的偶圖，則包含飽和的每個(gè)頂點(diǎn)的匹配當(dāng)且僅當(dāng)，對(duì)所有。9、在有6個(gè)點(diǎn)。12條邊的簡(jiǎn)單連通平面圖中，每個(gè)面均由條邊組成。10、彼德森圖的點(diǎn)色數(shù)為；邊色數(shù)為；點(diǎn)獨(dú)立數(shù)為。二、單選或多選題(15分，每題3分)1、設(shè)，則圖的補(bǔ)圖是().2、在下列圖中，既是歐拉圖又是哈密爾頓圖的是(). 3、下列圖中的()圖，到是可達(dá)的。4、下列圖中，可1—因子分解的是().5、下列優(yōu)化問題中，存在好算法的是()(A)最短路問題；(B)最小生成樹問題；(C)TSP問題；(D)最優(yōu)匹配問題.三、作圖題(10分)1、分別作出滿足下列條件的圖(1)、E圖但非H圖；(2)H圖但非E圖；(3)既非H圖又非E圖；(4)既是H圖又是E圖2、畫出度序列為(3,2,2,1,1,1)的兩個(gè)非同構(gòu)的簡(jiǎn)單圖。四、求下圖的最小生成樹，并給出它的權(quán)值之和(10分)。vv11v463429a8v22v56b7242v3v6圖G9五、給出一個(gè)同構(gòu)函數(shù)證明(10分)六、若圖為自補(bǔ)圖，那么，它的階一定能夠表示為或者的形式，其中為非負(fù)整數(shù)。而且，圖的邊有條。(5分)七、設(shè)T為一棵非平凡樹，度為的頂點(diǎn)記為，則。(10分)八、證明：階數(shù)為8的簡(jiǎn)單偶圖至多有16條邊(5分)九、設(shè)圖有10個(gè)4度頂點(diǎn)和8個(gè)5度頂點(diǎn)，其余頂點(diǎn)度數(shù)均為7。求7度頂點(diǎn)的最大數(shù)量，使得保持其可平面性(10分)十、求圖的色多項(xiàng)式(10分）學(xué)號(hào)姓名學(xué)號(hào)姓名學(xué)院……密……………封……………線……………以……………內(nèi)……………答……………題……………無……………效……（考試時(shí)間：至，共_____小時(shí)）課程名稱圖論及其應(yīng)用教師學(xué)時(shí)60學(xué)分教學(xué)方式講授考核日期_2007__年___月____日成績(jī)考核方式：（學(xué)生填寫）一．填空題(每題2分，共12分)1．簡(jiǎn)單圖G=(n,m)中所有不同的生成子圖(包括G和空?qǐng)D)的個(gè)數(shù)是_____個(gè)；2．設(shè)無向圖G=(n,m)中各頂點(diǎn)度數(shù)均為3，且2n=m+3,則n=_____;m=_____；3．一棵樹有個(gè)度數(shù)為i的結(jié)點(diǎn)，i=2,3,…,k,則它有____個(gè)度數(shù)為1的結(jié)點(diǎn)；4．下邊賦權(quán)圖中，最小生成樹的權(quán)值之和為_______;5、某年級(jí)學(xué)生共選修9門課。期末考試時(shí)，必須提前將這9門課先考完，每天每人只在下午考一門課，則至少需要______天才能考完這9門課。二．單項(xiàng)選擇(每題2分，共10分)1．下面給出的序列中，不是某簡(jiǎn)單圖的度序列的是()(A)(11123);(B)(22222);(C)(3333);(D)(1333).2．下列圖中，是歐拉圖的是（）3．下列圖中，不是哈密爾頓圖的是（）4．下列圖中，是可平面圖的圖的是（）5．下列圖中，不是偶圖的是（）三、(8分)畫出具有7個(gè)頂點(diǎn)的所有非同構(gòu)的樹四，用圖論的方法證明：任何一個(gè)人群中至少有兩個(gè)人認(rèn)識(shí)的朋友數(shù)相同(10分)五．(10分)設(shè)G為n階簡(jiǎn)單無向圖，n>2且n為奇數(shù)，G與G的補(bǔ)圖中度數(shù)為奇數(shù)的頂點(diǎn)個(gè)數(shù)是否相等？證明你的結(jié)論六．(10分)設(shè)G是具有n個(gè)頂點(diǎn)的無向簡(jiǎn)單圖，其邊數(shù)，證明(1)證明G中任何兩個(gè)不相鄰頂點(diǎn)的度數(shù)之和大于等于n。(2)給出一個(gè)圖，使它具有n個(gè)頂點(diǎn)，條邊，但不是哈密爾頓圖。七、(10分)今有趙、錢、孫、李、周五位教師，要承擔(dān)語文、數(shù)學(xué)、物理、化學(xué)、英語五門課程。已知趙熟悉數(shù)學(xué)、物理、化學(xué)三門課程，錢熟悉語文、數(shù)學(xué)、物理、英語四門課程，孫、李、周都只熟悉數(shù)學(xué)和物理兩門課程。問能否安排他們5人每人只上一門自己所熟悉的課程，使得每門課程都有人教，說明理由八、(10分)設(shè)G是具有n個(gè)頂點(diǎn)，m條邊，p(個(gè)連通分支的平面圖，G的每個(gè)面至少由k（）條邊所圍成，則九．(10分)求下圖G的色多項(xiàng)式Pk(G).十、(10分)(1)、在一個(gè)只有2個(gè)奇度點(diǎn)的邊賦權(quán)圖中，如何構(gòu)造一個(gè)最優(yōu)歐拉環(huán)游？說明理由；(2)、在一個(gè)邊賦權(quán)的哈密爾頓圖中，如何估計(jì)其最優(yōu)哈密爾頓圈的權(quán)值之和的下界？學(xué)號(hào)姓名學(xué)號(hào)姓名學(xué)院……密……………封……………線……………以……………內(nèi)……………答……………題……………無……………效……（考試時(shí)間：至，共__2_小時(shí)）課程名稱圖論及其應(yīng)用教師學(xué)時(shí)50學(xué)分教學(xué)方式講授考核日期_2008__年___月____日成績(jī)考核方式：（學(xué)生填寫）一．填空題(每題2分，共20分)1．若n階單圖G的最大度是，則其補(bǔ)圖的最小度=_____；2．若圖，，則它們的聯(lián)圖的頂點(diǎn)數(shù)=_____;邊數(shù)=_____；3．G是一個(gè)完全部圖，是第i部的的頂點(diǎn)數(shù)i=1，2,3,…,。則它的邊數(shù)為____；4．下邊賦權(quán)圖中，最小生成樹的權(quán)值之和為_______;5.若,則G的譜_______;6.5個(gè)頂點(diǎn)的不同構(gòu)的樹的棵數(shù)為_______;7.5階度極大非哈密爾頓圖族是_______;8.G為具有二分類(X,Y)的偶圖，則G包含飽和X的每個(gè)頂點(diǎn)的匹配的充分必要條件是______9.3階以上的極大平面圖每個(gè)面的次數(shù)為_______;3階以上的極大外平面圖的每個(gè)內(nèi)部面的次數(shù)為_______;10.n方體的點(diǎn)色數(shù)為_______;邊色數(shù)為_______。二．單項(xiàng)選擇(每題3分，共12分)1．下面給出的序列中，不是某圖的度序列的是()(A)(33323);(B)(12222);(C)(5533);(D)(1333).2．設(shè)V(G)=，則圖的補(bǔ)圖是（）3.下列圖中，既是歐拉圖又是哈密爾頓圖的是()4.下列說法中不正確的是()(A)每個(gè)連通圖至少包含一棵生成樹；(B)k正則偶圖(k>0)一定存在完美匹配；(C)平面圖,其中表示G的對(duì)偶圖；(D)完全圖可一因子分解。三、(10分)設(shè)圖G的階為14，邊數(shù)為27，G中每個(gè)頂點(diǎn)的度只可能為3，4或5，且G有6個(gè)度為4的頂點(diǎn)。問G中有多少度為3的頂點(diǎn)？多少度為5的頂點(diǎn)？四，(10)證明：每棵非平凡樹至少有兩片樹葉(10分)五．(10分)今有a,b,c,d,e,f,g七個(gè)人圍圓桌開會(huì)，已知：a會(huì)講英語，b會(huì)講英語和漢語，c會(huì)講英語、意大利語和俄語，d會(huì)講日語和漢語，e會(huì)講德語和意大利語，f會(huì)講法語、日語和俄語，g會(huì)講法語與德語。給出一種排座方法，使每個(gè)人能夠和他身邊的人交流（用圖論方法求解）。六．(10分)設(shè)是賦權(quán)完全偶圖G=(V,E)的可行頂點(diǎn)標(biāo)號(hào)，若標(biāo)號(hào)對(duì)應(yīng)的相等子圖含完美匹配,則是G的最優(yōu)匹配。七.(10分)求證：在n階簡(jiǎn)單平面圖G中有，這里是G的面數(shù)。八、(10分)來自亞特蘭大，波士頓，芝加哥，丹佛，路易維爾，邁阿密，以及納什維爾的7支壘球隊(duì)受邀請(qǐng)參加比賽，其中每支隊(duì)都被安排與一些其它隊(duì)比賽(安排如下所示)。每支隊(duì)同一天最多進(jìn)行一場(chǎng)比賽。建立一個(gè)具有最少天數(shù)的比賽時(shí)間表。亞特蘭大：波士頓，芝加哥，邁阿密，納什維爾波士頓：亞特蘭大，芝加哥，納什維爾芝加哥：亞特蘭大，波士頓，丹佛，路易維爾丹佛：芝加哥，路易維爾，邁阿密，納什維爾路易維爾：芝加哥，丹佛，邁阿密邁阿密：亞特蘭大，丹佛，路易維爾，納什維爾納什維爾：亞特蘭大，波士頓，丹佛，邁阿密(要求用圖論方法求解)九．(8分)求下圖G的色多項(xiàng)式Pk(G).學(xué)號(hào)姓名學(xué)號(hào)姓名學(xué)院……密……………封……………線……………以……………內(nèi)……………答……………題……………無……………效……（考試時(shí)間：至，共__2_小時(shí)）課程名稱圖論及其應(yīng)用教師學(xué)時(shí)60學(xué)分教學(xué)方式講授考核日期_2009__年___月____日成績(jī)考核方式：（學(xué)生填寫）一．填空題(每題2分，共20分)1．若自補(bǔ)圖G的頂點(diǎn)數(shù)是10，則G的邊數(shù)=_____；2．若圖，，則它們的積圖的頂點(diǎn)數(shù)=_____;邊數(shù)=_____；3．具有m條邊的簡(jiǎn)單圖的子圖個(gè)數(shù)為____；4．設(shè)G=Kn,n,則其最大特征值為_______;5.設(shè)G是n階的完全l等部圖，則其邊數(shù)m(G)=_______;6.下圖G1中最小生成樹的權(quán)值為_______;11326523圖G圖G17.6階度極大非哈密爾頓圖族是_______;8.K9的2因子分解的數(shù)目是______；9.n（n≥3）階極大外平面圖內(nèi)部面?zhèn)€數(shù)為_______;3階以上的極大平面圖的邊數(shù)m和頂點(diǎn)數(shù)n的關(guān)系為_______;10.下圖G2的點(diǎn)色數(shù)為_______;邊色數(shù)為_______。GG2二．單項(xiàng)選擇(每題3分，共12分)1．下面給出的序列中，不是某圖的圖序列的是()(A)(11123);(B)(22222);(C)(3333);(D)(1333).2．下列有向圖中是強(qiáng)連通圖的是()3.關(guān)于n方體Qn(n≥3)，下面說法不正確的是()(A)Qn是正則圖；(B)Qn是偶圖；(C)Qn存在完美匹配；(D)Qn是歐拉圖。4.關(guān)于平面圖G和其幾何對(duì)偶圖G*的關(guān)系，下列說法中不正確的是()(A)平面圖G的面數(shù)等于其對(duì)偶圖的頂點(diǎn)數(shù)；(B)平面圖G的邊數(shù)等于其對(duì)偶圖的邊數(shù)；(C)平面圖,其中表示G的對(duì)偶圖；(D)平面圖的對(duì)偶圖是連通平面圖。三、(10分)設(shè)根樹T有17條邊，12片樹葉，4個(gè)4度內(nèi)點(diǎn)，1個(gè)3度內(nèi)點(diǎn)，求T的樹根的度數(shù)。四，(10分)證明：若圖G的每個(gè)頂點(diǎn)的度數(shù)為偶數(shù)，則G沒有割邊。五．(10分)設(shè)G是一個(gè)邊賦權(quán)完全圖。如何求出G的最優(yōu)哈密爾頓圈的權(quán)值的一個(gè)下界？為什么？六．(10分)求證：偶圖G存在完美匹配的充要條件是對(duì)任意的，有七.(10分)求證：若G是連通平面圖，且所有頂點(diǎn)度數(shù)不小于3，則G至少有一個(gè)面，使得。八、(10分)一家公司計(jì)劃建造一個(gè)動(dòng)物園，他們打算飼養(yǎng)下面這些動(dòng)物：狒狒(b)、狐貍(f)、山羊(g)、土狼(h)、非洲大羚羊(k)、獅子(l)、豪豬(p)、兔子(r)、鼩鼱(s)、羚羊(w)和斑馬(z)。根據(jù)經(jīng)驗(yàn)，動(dòng)物的飲食習(xí)慣為：狒狒喜歡吃山羊、非洲大羚羊(幼年)、兔子和鼩鼱；狐貍喜歡吃山羊、豪豬、兔子和鼩鼱；土狼喜歡吃山羊、非洲大羚羊、羚羊和斑馬；獅子喜歡吃山羊、非洲大羚羊、羚羊和斑馬；豪豬喜歡吃鼩鼱和兔子；而其余的則喜歡吃蟲子、蚯蚓、草或其它植物。公司將飼養(yǎng)這些動(dòng)物，希望它們能自由活動(dòng)但不能相互捕食。求這些動(dòng)物的一個(gè)分組，使得需要的圍欄數(shù)最少。(要求用圖論方法求解)九．(8分)求下圖G的色多項(xiàng)式Pk(G).學(xué)號(hào)姓名學(xué)號(hào)姓名學(xué)院……密……………封……………線……………以……………內(nèi)……………答……………題……………無……………效……（考試時(shí)間：至，共__2_小時(shí)）課程名稱圖論及其應(yīng)用教師學(xué)時(shí)60學(xué)分教學(xué)方式講授考核日期_2010__年___月____日成績(jī)考核方式：（學(xué)生填寫）一．填空題(每題2分，共20分)1．若自補(bǔ)圖G的頂點(diǎn)數(shù)是，則G的邊數(shù)=_____；2．若圖，，則它們的聯(lián)圖的頂點(diǎn)數(shù)=_____;邊數(shù)=_____；14521145213623uvG1224．設(shè)是圖G的推廣的鄰接矩陣,則(k是正整數(shù))的表示的意義為_______________________________；5.設(shè)，則G的譜=_______;6.設(shè)8階圖G中沒有三角形，則G能夠含有的最多邊數(shù)為_______;7.三角形圖的生成樹的棵數(shù)為_______;8.G2的點(diǎn)連通度與邊連通度分別為______；GG29.n=5的度極大非H圖族為_______;10.n方體()的點(diǎn)色數(shù)為_______;邊色數(shù)為_______。二．單項(xiàng)選擇(每題3分，共12分)1．下面命題正確的是()(A)任意一個(gè)非負(fù)整數(shù)序列均是某圖的度序列；(B)設(shè)非負(fù)整數(shù)序列，則是圖序列當(dāng)且僅當(dāng)為偶數(shù);(C)若非負(fù)整數(shù)序列是圖序列，則對(duì)應(yīng)的不同構(gòu)的圖一定唯一;(D)n階圖G和它的補(bǔ)圖有相同的頻序列.2．下列有向圖中是強(qiáng)連通圖的是()3.關(guān)于歐拉圖與哈密爾頓圖的關(guān)系，下面說法正確的是()(A)歐拉圖一定是哈密爾頓圖；(B)哈密爾頓圖一定是歐拉圖；(C)存在既不是歐拉圖又不是哈密爾頓圖的圖；(D)歐拉圖與哈密爾頓圖都可以進(jìn)行圈分解。4.下列說法中正確的是()(A)任意一個(gè)圖均存在完美匹配；(B)k(正則偶圖一定存在完美匹配；(C)匈牙利算法不能求出偶圖的最大匹配，只能用它求偶圖的完美匹配；(D)圖G的一個(gè)完美匹配實(shí)際上就是它的一個(gè)1因子。三、(10分)若階為25且邊數(shù)為62的圖G的每個(gè)頂點(diǎn)的度只可能為3，4，5或6，且有兩個(gè)度為4的頂點(diǎn)，11個(gè)度為6的頂點(diǎn)，求G中5度頂點(diǎn)的個(gè)數(shù)。四，(8分)求下圖的最小生成樹（不要求中間過程，只要求畫出最小生成樹,并給出T的權(quán)和）。1113114311567438五．(8分)求下圖的k色多項(xiàng)式。GG六．(8分)設(shè)G是一個(gè)邊賦權(quán)完全圖。如何求出G的最優(yōu)哈密爾頓圈的權(quán)值的一個(gè)下界？為什么？七．(8分)求證：設(shè)是賦權(quán)完全偶圖的可行頂點(diǎn)標(biāo)號(hào)對(duì)應(yīng)的相等子圖，若是的完美匹配，則它必為G的最優(yōu)匹配。八.(8分)求證：若n為偶數(shù)，且，則G中存在3因子。九、(10分)一家公司計(jì)劃建造一個(gè)動(dòng)物園，他們打算飼養(yǎng)下面這些動(dòng)物：狒狒(b)、狐貍(f)、山羊(g)、土狼(h)、非洲大羚羊(k)、獅子(l)、豪豬(p)、兔子(r)、鼩鼱(s)、羚羊(w)和斑馬(z)。根據(jù)經(jīng)驗(yàn)，動(dòng)物的飲食習(xí)慣為：狒狒喜歡吃山羊、非洲大羚羊(幼年)、兔子和鼩鼱；狐貍喜歡吃山羊、豪豬、兔子和鼩鼱；土狼喜歡吃山羊、非洲大羚羊、羚羊和斑馬；獅子喜歡吃山羊、非洲大羚羊、羚羊和斑馬；豪豬喜歡吃鼩鼱和兔子；而其余的則喜歡吃蟲子、蚯蚓、草或其它植物。公司將飼養(yǎng)這些動(dòng)物，希望它們能自由活動(dòng)但不能相互捕食。求這些動(dòng)物的一個(gè)分組，使得需要的圍欄數(shù)最少。(要求用圖論方法求解)十．(8分)求證，每個(gè)5連通簡(jiǎn)單可平面圖至少有12個(gè)頂點(diǎn)。學(xué)號(hào)姓名學(xué)號(hào)姓名學(xué)院……密……………封……………線……………以……………內(nèi)……………答……………題……………無……………效……（考試時(shí)間：至，共__2_小時(shí)）課程名稱圖論及其應(yīng)用教師學(xué)時(shí)60學(xué)分教學(xué)方式講授考核日期_2011__年___月____日成績(jī)考核方式：（學(xué)生填寫）一．填空題(每空1分，共22分)1．若n階單圖G的最小度是，則其補(bǔ)圖的最大度=_____。2．若圖，，則它們的積圖的頂點(diǎn)數(shù)=_____;邊數(shù)=_____。3．設(shè)是圖的推廣鄰接矩陣，則的行列元等于由中頂點(diǎn)到頂點(diǎn)的長(zhǎng)度為______的途徑數(shù)目。4．完全圖的鄰接矩陣的最大特征值為_______。5.不同構(gòu)的3階單圖共有_______個(gè)。6.設(shè)階圖是具有個(gè)分支的森林，則其邊數(shù)_______。7.階樹()的點(diǎn)連通度為_______；邊連通度為________；點(diǎn)色數(shù)為_______；若其最大度為，則邊色數(shù)為________。8.圖是連通的，則中任意點(diǎn)對(duì)間至少有______條內(nèi)點(diǎn)不交路。9.5階度極大非哈密爾頓圖族為______和_______。10.完全圖能夠分解為_______個(gè)邊不相交的一因子之并。11.設(shè)連通平面圖具有5個(gè)頂點(diǎn)，9條邊，則其面數(shù)為_______；()階極大平面圖的面數(shù)等于__________；()階極大外平面圖的頂點(diǎn)都在外部面邊界上時(shí)，其內(nèi)部面共有_______個(gè)。12.完全偶圖的點(diǎn)獨(dú)立數(shù)等于________,點(diǎn)覆蓋數(shù)等于______。13.完全元根樹有片樹葉，個(gè)分支點(diǎn)，則其總度數(shù)為_______。14．對(duì)具有條邊的單圖定向，能得到______個(gè)不同的定向圖。二．單項(xiàng)選擇(每題3分，共15分)1．下面給出的序列中，不是某圖的度序列的是()(A)(1,3,5,4,7);(B)(2,2,2,2,2);(C)(3,2,3,3);(D)(1,5,7,1).2．下列無向圖一定是樹的是（）(A)連通圖；(B)無回路但添加一條邊后有回路的圖；(C)每對(duì)結(jié)點(diǎn)間都有路的圖；(D)連通且。3.以下必為歐拉圖的是()(A)頂點(diǎn)度數(shù)全為偶數(shù)的連通圖；(B)奇數(shù)頂點(diǎn)只有2個(gè)的圖；(C)存在歐拉跡的圖；(D)沒有回路的連通圖。4.設(shè)是()階單圖，則其最小度是為哈密爾頓圖的()(A)必要條件；(B)充分條件；(C)充分必要條件。5.下列說法正確的是()(A)非平凡樹和方體都是偶圖；(B)任何一個(gè)3正則圖都可1-因子分解；(C)可1-因子分解的3正則圖中一定存在哈密爾頓圈；(D)平面圖的對(duì)偶圖的對(duì)偶圖與是同構(gòu)的。三、(10分)設(shè)無向圖有12條邊，且度數(shù)為3的結(jié)點(diǎn)有6個(gè)，其余結(jié)點(diǎn)的度數(shù)小于3，求G的最少結(jié)點(diǎn)個(gè)數(shù)。四，(12分)在下面邊賦權(quán)圖中求：(1)每個(gè)頂點(diǎn)到點(diǎn)的距離(只需要把距離結(jié)果標(biāo)在相應(yīng)頂點(diǎn)處，不需要寫出過程);(2)在該圖中求出一棵最小生成樹，并給出最小生成樹權(quán)值(不需要中間過程，用波浪線在圖中標(biāo)出即可).五．(10分)今有趙、錢、孫、李、周五位教師，要承擔(dān)語文、數(shù)學(xué)、物理、化學(xué)、英語五門課程。已知趙熟悉數(shù)學(xué)、物理、化學(xué)三門課程，錢熟悉語文、數(shù)學(xué)、物理、英語四門課程，孫、李、周都只熟悉數(shù)學(xué)、物理兩門課程。問能否安排他們都只上他們熟悉的一門課程，使得每門課程都有人教（用圖論方法求解）。六．(6分)設(shè)是賦權(quán)完全偶圖G=(V,E)的可行頂點(diǎn)標(biāo)號(hào)，若標(biāo)號(hào)對(duì)應(yīng)的相等子圖含完美匹配,則是G的最優(yōu)匹配。七.(6分)求證：在n階簡(jiǎn)單平面圖G中有，這里是G的最小度。八、(10分)課程安排問題：某大學(xué)數(shù)學(xué)系要為這個(gè)夏季安排課程表。所要開設(shè)的課程為：圖論(GT),統(tǒng)計(jì)學(xué)(S),線性代數(shù)(LA),高等微積分(AC),幾何學(xué)(G),和近世代數(shù)(MA)?，F(xiàn)有10名學(xué)生(學(xué)生用Ai表示，如下所示）需要選修這些課程。根據(jù)這些信息，確定開設(shè)這些課程所需要的最少時(shí)間段數(shù)，使得學(xué)生選課不會(huì)發(fā)生沖突。(要求用圖論方法求解)A1:LA,S;A2:MA,LA,G;A3:MA,G,LA;A4:G,LA,AC;A5:AC,LA,S;A6:G,AC;A7:GT,MA,LA;A8:LA,GT,S;A9:AC,S,LA;A10:GT,S。九．(9分)求下圖G的色多項(xiàng)式Pk(G).G學(xué)號(hào)G學(xué)號(hào)姓名學(xué)院……密……………封……………線……………以……………內(nèi)……………答……………題……………無……………效……2154 學(xué)號(hào)姓名學(xué)號(hào)姓名學(xué)院……密……………封……………線……………以……………內(nèi)……………答……………題……………無……………效……（考試時(shí)間：至，共__2_小時(shí)）課程名稱圖論及其應(yīng)用教師學(xué)時(shí)60學(xué)分教學(xué)方式講授考核日期_2012__年___月____日成績(jī)考核方式：（學(xué)生填寫）一、填空題（填表題每空1分，其余每題2分，共30分)1．階正則圖G的邊數(shù)=；2．3個(gè)頂點(diǎn)的不同構(gòu)的簡(jiǎn)單圖共有個(gè)；3．邊數(shù)為的簡(jiǎn)單圖的不同生成子圖的個(gè)數(shù)有個(gè)；4.圖與圖的積圖的邊數(shù)為；5.在下圖中，點(diǎn)到點(diǎn)的最短路長(zhǎng)度為；6.設(shè)簡(jiǎn)單圖的鄰接矩陣為，且，則圖的邊數(shù)為；7.設(shè)是n階簡(jiǎn)單圖，且不含完全子圖，則其邊數(shù)一定不會(huì)超過；8．的生成樹的棵數(shù)為;9.任意圖的點(diǎn)連通度、邊連通度、最小度之間的關(guān)系為；10.對(duì)下列圖，試填下表（是類圖的打〝√〞，否則打〝〞）。=1\*GB3①=2\*GB3②=3\*GB3③能一筆畫的圖Hamilton圖偶圖可平面圖=1\*GB3①√√=2\*GB3②√=3\*GB3③√√√二、單項(xiàng)選擇(每題2分，共10分)1．下面命題正確的是(B)對(duì)于序列，下列說法正確的是：(A)是簡(jiǎn)單圖的度序列；(B)是非簡(jiǎn)單圖的度序列;(C)不是任意圖的度序列;(D)是圖的唯一度序列.2．對(duì)于有向圖，下列說法不正確的是(D)(A)有向圖中任意一頂點(diǎn)只能處于的某一個(gè)強(qiáng)連通分支中；(B)有向圖中頂點(diǎn)可能處于的不同的單向分支中;(C)強(qiáng)連通圖中的所有頂點(diǎn)必然處于強(qiáng)連通圖的某一有向回路中;(D)有向連通圖中頂點(diǎn)間的單向連通關(guān)系是等價(jià)關(guān)系。3.下列無向圖可能不是偶圖的是(D)(A)非平凡的樹；(B)無奇圈的非平凡圖；(C)方體；(D)平面圖。4.下列說法中正確的是(C)(A)連通3正則圖必存在完美匹配；(B)有割邊的連通3正則圖一定不存在完美匹配；(C)存在哈密爾頓圈的3正則圖必能1因子分解；(D)所有完全圖都能作2因子分解。5.關(guān)于平面圖，下列說法錯(cuò)誤的是(B)(A)簡(jiǎn)單連通平面圖中至少有一個(gè)度數(shù)不超過5的頂點(diǎn)；(B)極大外平面圖的內(nèi)部面是三角形，外部面也是三角形；(C)存在一種方法，總可以把平面圖的任意一個(gè)內(nèi)部面轉(zhuǎn)化為外部面；(D)平面圖的對(duì)偶圖也是平面圖。三、(10分)設(shè)與其補(bǔ)圖的邊數(shù)分別為，求的階數(shù)。解：設(shè)的階數(shù)為。因…………………4分所以：……..2分得：………..4分四、(10分)求下圖的最小生成樹（不要求中間過程，只要求畫出最123v7v6v1v2v6V7小生成樹,并給出123v7v6v1v2v6V7244351665v4v3v4v5V244351665v4v3v4v5V7v6v5v4v3v2v1v4v6v7654351624123五、(10分)(1).求下圖的k色多項(xiàng)式；(2).求出的點(diǎn)色數(shù)；(3).給出一種使用種顏色的著色方法。解：(1)、圖G的補(bǔ)圖為：(2分)………………..1分對(duì)于：，所以，其伴隨多項(xiàng)式為：……..1分所以：………………1分于是色多項(xiàng)式=k(k-1)(k-2)[2+4(k-3)+(k-3)(k-4)]=k(k-1)2(k-2)22分解法22分+=(k-1)3分=(k-1)[k(k-1)(k-2)2]=k(k-1)2(k-2)22分(2)、由于，所以，點(diǎn)色數(shù)=3；……..2分(3)、點(diǎn)著色：(1分)六、(10分)5個(gè)人被邀請(qǐng)參加橋牌比賽。橋牌比賽規(guī)則是每一場(chǎng)比賽由兩個(gè)2人組進(jìn)行對(duì)決。要求每個(gè)2人組都要與其它2人組（W,Z{X,Y}）進(jìn)行對(duì)決。若每個(gè)人都要與其他任意一個(gè)人組成一個(gè)2人組，且每個(gè)組在同一天不能有多余一次的比賽，則最少安排多少天比賽（每一天可以有多場(chǎng)比賽）？請(qǐng)給出相應(yīng)的一個(gè)時(shí)間安排表。(用圖論方法求解)解：(1)、建模：5個(gè)人能夠組成10個(gè)2人組：AB,AC,AD,AE,BD,BC,BE,CD,CE,DE。以每個(gè)2人組作為頂點(diǎn)，因要求每個(gè)2人組都與其它2人組比賽，所以，得到比賽狀態(tài)圖如下：4分(2)、最少安排多少天比賽轉(zhuǎn)化為求狀態(tài)圖的邊色數(shù)。因?yàn)楸说蒙瓐D不可1因子分解，于是可推出，又可用4種色對(duì)其正常邊著色(見下圖)，所以：。所以：。2分1111222122333444(3)、安排時(shí)間表：第一天：AB---DE,AE---BC,AC---BE,AD---CE;第二天：AB---CE,AC---DE,AE---BD,AD---BC,BE---CD;第三天：AB---CD,BC---DE,BD---CE;第四天：AC---BD,AD---BE,AE---CD。4分七、(10分)由于在考試中獲得好成績(jī)，6名學(xué)生將獲得下列書籍的獎(jiǎng)勵(lì)，分別是：代數(shù)學(xué)(a)，微積分(c)，微分方程(d)，幾何學(xué)(g)，數(shù)學(xué)史(h)，規(guī)劃學(xué)(p)，拓?fù)鋵W(xué)(t)。每門科目只有1本書，而每名學(xué)生對(duì)書的喜好是：A：d,h,t；B：h,t；C：d,h；D：d,t；E：a,c,d；F:：c,d,p,g。每名學(xué)生是否都可以得到他喜歡的書？為什么？(用圖論方法求解)解：由題意,得模型圖：(4分)問題轉(zhuǎn)化為是否存在飽和A,B,C,D,E,F的匹配存在。2分取頂點(diǎn)子集合，因，所以由霍爾定理知：不存在飽和A,B,C,D,E,F的匹配。故每名學(xué)生不能都得到他喜歡的書。4分八、(10分)若為偶數(shù)，且單圖G滿足：，求證：中有3因子。證明：因單圖G滿足：，所以中存在哈密爾頓圈。2分又因?yàn)榕紨?shù)，所以，可分解為兩個(gè)1因子，它們顯然也是圖G的兩個(gè)1因子。3分考慮，則，于是，中存在哈密爾頓圈。2分作，則為G的一個(gè)3因子。3分學(xué)號(hào)姓名學(xué)號(hào)姓名學(xué)院……密……………封……………線……………以……………內(nèi)……………答……………題……………無……………效……（考試時(shí)間：至，共__2_小時(shí)）課程名稱圖論及其應(yīng)用教師學(xué)時(shí)60學(xué)分教學(xué)方式講授考核日期_2013__年_6__月__20__日成績(jī)考核方式：（學(xué)生填寫）一．填空題(每空2分，共20分)1．n階正則圖G的邊數(shù)=_____。2．4個(gè)頂點(diǎn)的不同構(gòu)單圖的個(gè)數(shù)為________。3．完全偶圖(且為偶數(shù))，則在其歐拉環(huán)游中共含____條邊。4．高為的完全2元樹至少有_______片樹葉。5.由3個(gè)連通分支組成的平面圖，則其共有_______個(gè)面。6.設(shè)圖與同胚，則至少?gòu)闹袆h掉_______條邊，才可能使其成為可平面圖。7.設(shè)為偶圖，其最小點(diǎn)覆蓋數(shù)為，則其最大匹配包含的邊數(shù)為________。8.完全圖能分解為個(gè)邊不重合的一因子之并。9.奇圈的邊色數(shù)為。10.彼得森圖的點(diǎn)色數(shù)為。二．單項(xiàng)選擇(每題3分，共15分)1．下面說法錯(cuò)誤的是()(A)圖中的一個(gè)點(diǎn)獨(dú)立集，在其補(bǔ)圖中的點(diǎn)導(dǎo)出子圖必為一個(gè)完全子圖；(B)若圖連通，則其補(bǔ)圖必連通；(C)存在5階的自補(bǔ)圖；(D)4階圖的補(bǔ)圖全是可平面圖.2．下列說法錯(cuò)誤的是（）(A)非平凡樹是偶圖；(B)超立方體圖(方體,)是偶圖；(C)存在完美匹配的圈是偶圖；(D)偶圖至少包含一條邊。3.下面說法正確的是()(A)2連通圖的連通度一定為2；(B)沒有割點(diǎn)的圖一定沒有割邊；(C)階圖是塊，則中無環(huán)，且任意兩點(diǎn)均位于同一圈上；(D)有環(huán)的圖一定不是塊。4.下列說法錯(cuò)誤的是()(A)設(shè)階單圖的最小度滿足，則其閉包一定為完全圖；(B)設(shè)階單圖的任意兩個(gè)不鄰接頂點(diǎn)與滿足，則其閉包一定為完全圖；(C)有割點(diǎn)的圖一定是非哈密爾頓圖；(D)一個(gè)簡(jiǎn)單圖是哈密爾頓圖的充要條件是它的閉包是哈密爾頓圖。5.下列說法錯(cuò)誤的是()(A)極大平面圖的每個(gè)面均是三角形；(B)極大外平面圖的每個(gè)面均是三角形；(C)可以把平面圖的任意一個(gè)內(nèi)部面轉(zhuǎn)化為外部面；(D)連通平面圖的對(duì)偶圖的對(duì)偶圖與是同構(gòu)的。三、(10分)設(shè)是個(gè)不同的正整數(shù)，求證：序列不能是簡(jiǎn)單圖的度序列。四，(15分)在下面邊賦權(quán)圖中求：(1)每個(gè)頂點(diǎn)到點(diǎn)的距離(只需要把距離結(jié)果標(biāo)在相應(yīng)頂點(diǎn)處，不需要寫出過程);(2)在該圖中求出一棵最小生成樹，并給出最小生成樹權(quán)值(不需要中間過程，用波浪線在圖中標(biāo)出即可)；(3)，構(gòu)造一條最優(yōu)歐拉環(huán)游。五．(10分)設(shè)是完全元樹，是分支點(diǎn)數(shù)，是樹葉數(shù)，求證：六.(10分)某大型公司7個(gè)不同部門有些公開職位，分別是(a):廣告設(shè)計(jì)，(b)：營(yíng)銷，(c):計(jì)算師，(d)規(guī)劃師，(e):實(shí)驗(yàn)師，(f)：財(cái)政主管，(g):客戶接待。有6名應(yīng)聘者前來申請(qǐng)這些職位，分別是：Alvin(A):a,c,f;Beverly(B):a,b,c,d,e,g;Connie(C):c,f;Donald(D):b,c,d,e,f,g;Edward(E):a,c,f:Frances(F):a,f.用偶圖為此問題建