組合數(shù)學及其圖論試題庫

1、組合數(shù)學及其圖論1、一個圖G是指一個有序三元組（V（G），E（G），），其中是：_.關聯(lián)函數(shù)2、是有40個點的簡單圖且 中任兩個點之間有且只有1條路，則 。 39 3、只有一個頂點所構成的圖稱為：_平凡圖4、如果H是G的子圖，其中V（H）=V（G）和E（G）=E（H）至少有一個不成立，就稱H是G的：_.真子圖5、設G是p階簡單圖，則_等號成立當且僅當G是完全圖。q(G)p(p-1)/26、如果一條途徑的_與_相同，就稱這條途徑為閉途徑。起點 終點7、如果對圖G=（V，E）的任何兩個頂點u與v，G中存在一條（u-v）路，則稱G是_否則稱為是_ 連通圖、 非連通圖8、設G是P階連通圖，則_. q(

2、G)p-19、若二分圖 有Hamilton回路，則 與 滿足 。  10、若G是2-邊連通圖，則G有強連通的_. 定向圖11、邊數(shù)最少的連通圖是 。樹12、沒有回路的連通圖稱為_. 樹13、 的圖是 圖或 圖。 平凡圖，不連通圖14、樹T的每一個非懸掛點都是T的 _. 割點15、二分圖 中若 與 滿足 ，則 必有完美對集。 16、給定一個圖G，如果圖G的一個生成子圖T是一棵樹，則稱T是G的一個 _. 生成樹17、設G是無環(huán)圖，e是G的一條邊，則(G)=_.（Ge）+(G·e)18、 是 階簡單圖，則 ，等號成立當且僅當 是 圖。 ，完全圖 2、19、_的生成樹稱為最優(yōu)生成樹

3、。連通賦權圖中具有最小權20、 的一個對集 是最大對集的充要條件是 。 中無 可擴路21、一個有向圖D，如果略去每條弧的方向時所得無向圖是一棵樹，就稱D為_.有向樹22、經(jīng)過G的每條邊的跡稱為G的Euler跡，如果這條跡是閉的，則稱這條閉跡為G的 _. Euler環(huán)游23、 是簡單圖且 ，則 。 24、若 是 -正則圖，則 。 25、簡單圖 滿足 ，則 是 圖。 不連通圖， 平凡圖26、 的圖 是 圖或 圖。 2 27、樹 恰有兩個懸掛點，則 。 連通28、 有生成樹的充要條件是 。 3029、若 是有31個點的連通圖且 中每條邊都是割邊，則 。 130、 階圖 是連通圖，則 。 ，31、若

4、是 的一個對集，則 ，等號成立當且僅當是 對集。 完美對集32、每位上的數(shù)字互異且非零的兩位數(shù)共有_個。 7233、現(xiàn)在有10雙不同的鞋。為了保證能夠有一雙鞋被選出，至少要從這20只鞋中取出_只鞋。 11 34、展開式中的系數(shù)為_。42035、序列 1, c, c2, , cn, 的生成函數(shù)是_。;36、數(shù)值函數(shù)f和g的卷積f *g的通項f *g (r) = 。.37、敘述下列概念：發(fā)點，收點，中間點。參考要點：D包含兩個特定的頂點x和y，x設有向連通圖D=（V，A）滿足：僅有出弧而沒有入弧，稱為發(fā)點；y僅有入弧而沒有出弧，稱為收點；D中其余頂點既有出弧有入弧，稱為中間點。38、在一次圍棋擂臺

5、賽中，雙方各出n名選手。規(guī)則是雙方先各自排定一個次序，設甲方排定的次序是， ，乙方排定的次序為，。與先比賽，勝的一位與對方下一位選手比賽。按這種方法直到有一方的最后一位選手出場并輸給對方，比賽結束。問最多進行幾場比賽可定勝負（假定比賽無平局）。參考要點：建立一個有向圖D=（V，A），V=，如果與之間連一條弧，其方向從勝者指向負者。則D的每一條弧對應一場比賽，D中弧的數(shù)目就是這次比賽的次數(shù)。根據(jù)規(guī)則，每一名選手至多輸一場，所以D中每個頂點的入度至多為1，但必有一個入度為1，另一個為0。 ，即至多2n-1場比賽可定勝負。39、用一些圓面覆蓋平面上取定的2n個點。試證：若每個圓面至少覆蓋n+1個點，

6、則任兩個點能由平面上的一條折線所連接，而這條折線整個地被某些圓面所覆蓋。參考答案：構造圖G=（V，E）如下：V就取平面上給定的2n 個點，兩個不同的頂點如果含在同一個圓面上，就在這兩個頂點之間連上一條邊（邊也含在這個平面上）。所得圖是一個簡單圖，而且每個頂點的度至少是n，即，由推論，G是連通圖，所以G中任兩點之間有一條路連接。由G的構造，這條路被若干個圓面覆蓋。40、在二元正則樹T中，它的分支點數(shù)和樹葉數(shù)t滿足：r=t-1。參考答案：因為正則二元樹T的弧數(shù)為r+t-1，頂點度數(shù)的總和為2+3（r-1）+t。由頂點度數(shù)與邊數(shù)的關系，有2（r+t-1）=2+3（r-1）+t得r=t-1。41、某編

7、輯部收到由n個人所寄的一些問題的解，他們發(fā)現(xiàn)每個人寄來四個不同問題的解，每個問題的解恰好由兩個人同時給出。問他們共收到幾個不同問題的解。參考答案：首先建立圖G=（V，E），G的n個頂點代表n個人。兩個不同的頂點和之間連接的邊數(shù)等于這兩個點所對應的兩個人同時給出相同問題解的個數(shù)。由條件，G的每一條邊對應一個問題的解，每個頂點的度為4。因而共收到q（G）=2n個不同問題的解。42、有十七位學者，每一位都給其余的人寫一封信，信的內(nèi)容是討論3個論文題目中的任一個，而且2個人相互通信所討論的是同1個題目。證明至少有三位學者，他們之間通信所討論的是同一個論文題目。參考答案：做一個完全子圖，它的17個頂點代

8、表17位學者，把其中的邊染成3種顏色：如果兩個學者討論的是第i個題目，就將連接相應的2個頂點的邊染上第i種顏色（i=1，2，3）。這樣就得到3色完全圖。由定理。因此，這個3色完全圖中有一個同色三角形。這個同色三角形所對應的3位學者之間通信所討論的是同一個論文題目。43、證明和是非平面圖。參考答案：含有6個頂點，9條邊，但最短回路長度為4，不滿足，因此不是平面圖。有5個頂點，10條邊，不滿足，故不是平面圖。44、在一次象棋擂臺賽中,雙方各出n名選手.比賽的規(guī)則是雙方各自排定一個次序,設甲方排定的次序為x1,x2, xn ,乙方排定的次序為y1,y2,yn . x1與y1先比賽,勝的一位與對方輸?shù)?/p>

9、下一位選手比賽.按這種方法進行比賽,直到有一方的最后一位選手出場比賽并且輸給對方,比賽就結束,問最多進行幾場比賽可定勝負(假定比賽不出現(xiàn)平局)? 參考要點：建立一個有向圖D=(V,A),V= x1,x2, xn , y1,y2,yn ,如果xi與yi進行過一場比賽,就在xi與yi之間連一條弧.其方向從勝者指向負者,則D的每一條弧對應一場比賽,D中弧的數(shù)目就是這次比賽的次數(shù).根據(jù)比賽的規(guī)則,每一名選手至多輸一場,故D中每個頂點的入度至多為1,但xn 與yn必有一個入度為1,另一個為0.因此 |A|即至多進行2n-1場比賽就可以確定勝負。45、平面上有n條線段,n3,其中任意3條都有公共端點.證明

10、這n條線段有一個公共端點。參考要點：設G是連通圖,則G中任意兩個不同的頂點與之間有一條路連接.若記這條路的長度為,顯然.則.而對于任意的,因G連通,且,則有,所以R(G)中沒有零元素.設與是G中的任意兩個不同的頂點.因為存在,則在G中有一條長為的途徑連接與.因而從與有一條路,故G是連通圖。46、證明任意六個人中有三個人互相認識，或有三個人互不認識。.證：構圖 如下：圖的頂點代表這6個人，兩個頂點相鄰當且僅當對應的兩個人互相認識。則對于圖中任意一個點 或 。不妨設 及它的3個鄰點為 。若 中有任意兩個點，不妨設為 ，相鄰，則 對應的3個人互相認識；否則， 中任意兩個點不鄰，即它們對應的3個人互不

11、認識。 47、給定圖 ：    1、給出圖 的一個生成樹；    2、給出圖 的點連通度；    3、給出圖 的最大對集；     4、給出圖 的一個最長回路； 5、給出圖 的直徑和半徑。· 答案  1、  2、3 3、 4、 5、2 ，2  48、試給出一個算法,求連通賦權圖中最大權的生成樹.   算法：1)在 中選取邊 ，使 盡可能的大；2)若已經(jīng)選定邊 ，則在 中選取邊

12、，使?jié)M足以下兩條：I.  不含回路；II.  在滿足的前提下，使 盡可能的大。3）當2)不能繼續(xù)執(zhí)行時，停止。49、設是連通簡單圖，證明中存在個頂點，使得 仍是連通圖。 證： 是連通簡單圖，設其最大度點為 。設 是 關于 的保距生成樹，則 ，故 中至少有 個懸掛點，不妨設為 ，則 連通，是 的生成子圖，即 連通。 50、對下圖 ，求一個最優(yōu)生成樹。· 答案51、證明任意六個人中有三個人互相認識，或有三個人互不認識。.證：構圖 如下：圖的頂點代表這6個人，兩個頂點相鄰當且僅當對應的兩個人互相認識。則對于圖中任意一個點 或 。不妨設 及它的3個鄰點為 。若 中有任意兩

13、個點，不妨設為 ，相鄰，則 對應的3個人互相認識；否則， 中任意兩個點不鄰，即它們對應的3個人互不認識。 52、給定圖    問：1、作圖 的一個最長回路 ；   2、給出圖 的一個生成樹；   3、給出圖 的點連通度；   4、給出圖 的最大對集；   5、作出圖 的閉包。· 答案1、 2、3、 3 4、 5、 53、試證明：如果無環(huán)圖G的任意兩頂點都被唯一的路相連，則G是樹。參考答案：證明：由于G中任意兩頂點都被唯一的路相連，故G連通。 若G含有圈C，則C上的兩點，在G中

14、存在兩條路相連，這與題設的“唯一”矛盾。故G中不含圈。由樹的定義知道：G是樹。54、有n張紙牌，每張紙牌的正反兩面都寫上1，2，.n的某一個數(shù)。證明：如果每個數(shù)字都恰好出現(xiàn)兩次，那么這些紙牌一定可以這樣攤開，使朝上的面中1，2，3n都出現(xiàn)。參考答案：證明：作一二分圖G=（X，Y；E），其中X=1，2，n,Y=y y 2 .yn表示這張牌。i與yj之間連接的邊數(shù)等于數(shù)i在紙牌yj出現(xiàn)的次數(shù)，這樣得到的圖G是一個2正則二分圖。則G中存在一個完美對集，設為M=1y 2y.ny則只要把紙牌y中的1朝上，y中的2朝下，y中的n朝上，這樣攤開的紙牌就能使朝上的面中1，2，3.n都出現(xiàn)。55、證明邊長為2的

15、正方形內(nèi)任意5個點必有兩點，其距離不超過。證：構造抽屜如圖，將5個點放在4個邊長為1小正方形內(nèi)，由抽屜原理，必有一個小正方形內(nèi)至少有兩個點，這兩個點的距離就小于或等于。 56、解：57、設數(shù)值函數(shù)f = 1,2,22,23,.，g = 1,3,32,33,.，求3f-5g的生成函數(shù)。解：數(shù)值函數(shù)f = 1,2,22,23,.和g = 1,3,32,33,.的生成函數(shù)58、設初始值h(0) = 0, h(1) = 1，h(2) = 2，求解遞推關系h(n) = h(n1)+9h(n2)9h(n3). (n = 3,4,.) 參考答案：特征方程為：x3 - x2- 9x+9 = 0解得特征根為1,

16、 3,-3.因此 h(n) = A1n + B3n+ C(-3)n為一般解，由邊界條件得解此線性方程組得唯一解 因此所求的解為 59、平面上給出25個點，其中沒有任何3個點共線。這些點能確定多少條直線？多少個三角形？解：由于沒有3個點共線，所以每對點就確定一條直線，而直線的確定與兩個點的次序無關，屬組合問題，直線的總數(shù)為每三個點確定一個三角形，因此所確定的三角形總數(shù)為60、一個面包店有6種不同類型的面包，這些面包以每打12個為單位向外出售。這個面包店能裝配成多少打不同的面包（不考慮面包的順序）？如果在每打中每種類型的面包至少有一個，那么又能裝配成多少打不同的面包？解：假設面包店每種面包都有很多

17、（每種至少12個），由于每打中的面包與順序無關，故為組合問題，能裝配成不同的面包的打數(shù)即為6種類型的多重集（無窮重數(shù)）的12-組合數(shù)，其值為種。 如果在每打中每種類型的面包至少有一個，那么能裝配成不同的面包的打數(shù)可以看成為6種類型的多重集（無窮重數(shù)）的6-組合數(shù)，其值為種。61、試用生成函數(shù)求下式之和：. 解：設 兩邊求導再乘 x 得:令 x = 1 得:.62網(wǎng)絡專業(yè)的學生選修C+ 的有38人，選修VB的有15人，選修D(zhuǎn)ELPHI的有20人，選修這三門課的同學總數(shù)為58人，且其中只有3人同時選修這三門課，試求同時選修兩門課的同學有幾人？解：設A, B, C分別為選修C+, VB, DELPH

18、I的同學的集合，則由 |AÈBÈC| = |A| + |B| + |C| - (|AÇB| + |AÇC| +|BÇC| ) + | AÇBÇC| 得 (|AÇB| + |AÇC| +|BÇC| )= |A| + |B| + |C| + | AÇBÇC| - |AÈBÈC| = 38 + 15 + 20 + 3 - 58 = 18 同時選修兩門課的同學有18人。63、設簡單圖中每個頂點的度至少是3，則含有長為偶數(shù)的回路。證明：設是的一條最長路，則的所有鄰點

19、全在內(nèi)，設的鄰點為，其中，在中取三個回路 它們的長度分別為。這三個數(shù)至少有一個是偶數(shù)。即中至少有一個是長為偶數(shù)的回路。 證畢。64、樹的每一個非懸掛點都是的割點。證明：設是階樹，是中一個非懸掛點，即。不難看出含個頂點，其邊數(shù)為 =，因而不是樹。顯然不含回路，所以非連通，即是的割點。 證畢。65、若連通圖恰好有個奇點，則在中存在條邊不交的跡，使得 。證明：設的個奇點為，在中增加條分別連接的新邊，所得圖記為，則是一個Euler圖。記的一條Euler環(huán)游為，然后在中刪除新加的條邊，就將分成段，這段即為的條邊不交的跡。 證畢。66、若階圖沒有孤立頂點，則證明：設是的最大獨立集，是的最小點覆蓋，則是的獨立集，是的點覆蓋，所以 = 因此67在一次聚會上有10位男士和10位女士。這10位女士能夠有多少種方法選擇男舞伴開始第一次跳舞？如果每個人必須換舞伴，那么第二次跳舞又有多少種選擇方法？解：對于第一次跳舞，可以對10位男士和10位女士并排排列，如果10位男士不改變次序，10位女士一個全排列就是一種配對方式，共存在10! = 3628800可能的選擇； 對于第二次跳舞，每位女士必須選擇一位不是第一次與她跳舞的男舞伴，因此可能的選擇方法數(shù)為移位排列數(shù) =