圖論例講問(wèn)題解答

1、圖論例講（問(wèn)題解答）陶平生1、設(shè)有2n 階簡(jiǎn)單圖G ，若其每個(gè)頂點(diǎn)的度數(shù)皆不小于 n ，證明：從G 中必可選出n 條邊，其端點(diǎn)互不相同證：我們最大限度地選出 k 條兩兩無(wú)公共端點(diǎn)的邊，若k = n ，則命題已得證；現(xiàn)在設(shè) k < n ，這 k 條邊記為，在剩下的其它，必須是每條邊至少有一個(gè)端點(diǎn)與 P1, P2 ， ,P2k 中的一個(gè)點(diǎn)重合，不然的話，我們又可以將這樣的一條邊添加進(jìn)去，使得這種多于 k 條，與k 的最大性！今考慮圖G 在上述端點(diǎn)集P1, P2 ， ,P2k 之外的一對(duì)頂點(diǎn) A, B ，它們本身相連，P1, P2 ， ,P2k 至少由于每個(gè)頂點(diǎn)的度數(shù)皆不小于 n ，而 n &

2、#179; k +1 ，即點(diǎn) A, B 共同發(fā)出了2k + 2 條邊（稱(chēng)這種紅邊），k 條必有一條，它的兩個(gè)端點(diǎn)關(guān)聯(lián)了至少三條紅邊（如果這 k 條的每一條邊都至多關(guān)聯(lián)兩條紅邊，那么紅邊的總條數(shù)將不超過(guò)2k ，?。〢AB現(xiàn)在設(shè)，邊 P2k -1P2k 關(guān)聯(lián)了三條紅邊，得到兩種B關(guān)聯(lián)模式，P2kP2k-1每種模式下，我們都可以去掉邊 PP 以及一條紅P2k-1P2k2k -1 2k邊，而保留兩條無(wú)公共端點(diǎn)的紅邊，這樣，圖G 中兩兩無(wú)公共端點(diǎn)的邊成為 k +1 條，又與k 的最大性！因此 k < n 的假設(shè)被2 、某地網(wǎng)球，所以 k = n ，結(jié)論得證的20 名成員舉行14 場(chǎng)單打比賽，每人至

3、少上場(chǎng)一次，證明：必有六場(chǎng)比賽，其中的12 名參賽者各不相同（1989 ）證：用20 個(gè)點(diǎn)V1,V2,V20 表示這20 名成員，如果兩名成員比賽過(guò)，則在相應(yīng)的兩點(diǎn)到圖G 之間條邊，據(jù)題意， G 有14 條邊，設(shè)頂點(diǎn)Vi 的度數(shù)為 di ，則 di ³ 1, i = 1, 2, 20 ，而 d1 + d2 + d20 = 2´14 = 28 在每個(gè)頂點(diǎn)Vi 處抹去 di -1條邊（或者說(shuō)，在每點(diǎn)Vi 所發(fā)出的取 di -1條染成紅色），由于同一條邊可能被其兩個(gè)端點(diǎn)所抹去（染紅），所以抹去的邊（紅邊）至多有(d1 -1) + (d2 -1) + (d20 -1) = 28 -

4、 20 = 8 條，因此在抹去這些邊后，所得的圖G¢ 中至少含有14 - 8 = 6 條邊，且圖G¢ 中每個(gè)頂點(diǎn)的度數(shù)至多是1 ，從而這6 條鄰接的12 個(gè)頂點(diǎn)各不相同，即這6 條對(duì)應(yīng)的6 場(chǎng)比賽，其中的12 名參賽者各不相同3 、設(shè)G 為 n 階圖，且沒(méi)有長(zhǎng)為4 的圈；證明：其q £ é n (1+4n - 3 )ù êë 4證明： 設(shè) G 的頂點(diǎn)為 V1,V2 ,×××,Vn ， 且設(shè)頂點(diǎn) Vj 的度為 aj ，úûj = 1, 2,×××,

5、 n ，則nå a j j =1= 2q 現(xiàn)考察與頂點(diǎn)Vj （j = 1, 2,×××, n ）相鄰的個(gè)頂點(diǎn)所的頂點(diǎn)對(duì)，則對(duì)1于每個(gè)頂點(diǎn)V ，這樣不同的頂點(diǎn)對(duì)有C 2 個(gè)，并且個(gè)頂點(diǎn)對(duì)互不相同（事實(shí)上，若對(duì)于Vk ,Vl k ¹ l 與Vi ,Vj 均相鄰，這樣ja ji ¹ j ，頂點(diǎn)Vi 的某頂點(diǎn)對(duì)與Vj 的某頂點(diǎn)對(duì)相同，則. ）， 而總的頂點(diǎn)對(duì)至多為 C2 個(gè)， 故VV V V 形成一個(gè)長(zhǎng)度為 4 的圈， 與題意i k j lnö2÷ø1 ænnnnn1nåC£ C ，

6、故 n - n ³a 2 - åa ³å jjç åaj- åa =(2q )2 - 2q222a jnjnèj =1j =1j =1j =1j =1即(1-4n - 3 ) £ q £(1+4n - 3 )，nn44而 q 為整數(shù)，故 q £ é n (1+4n - 3 )ù êë 4úû(n ³ 2) 個(gè)互不相等的 n 位正整數(shù)，證明：k Î1, 2, n，使得4 、任意給定 n將它們的第 k 位數(shù)字都

7、刪去后，所得到的 n 個(gè) n -1位數(shù)仍互不相等.證：設(shè)這 n 個(gè) n 位數(shù)為 a1, a2,用反證法，若對(duì)于每個(gè) k Î1, 2, an ., n，刪去這組數(shù)的第 k 位數(shù)字后，所得到的 n 個(gè) n -1, ank 中，都至少有兩個(gè)數(shù)相等，設(shè) aik = ajk ，因原來(lái)相應(yīng)的兩數(shù) ai ¹ aj ，則位數(shù) a1k , a2k ,ai , aj 被刪去的第 k 位數(shù)字必不相同，稱(chēng)這樣的一對(duì)數(shù) ai , aj 為“具有性質(zhì) Pk ”（ ai , aj 只有第 k 位數(shù)字不同，其它位置上的數(shù)字對(duì)應(yīng)相同）.今用 n 個(gè)點(diǎn) v1, v2, vn 分別表示這 n 個(gè)數(shù)，若某一對(duì)數(shù)

8、ai , aj 具有性質(zhì) Pk ，k Î1, 2, n，則令相應(yīng)的點(diǎn)vi ,vj 相鄰，n 階圖G .據(jù)反證法所設(shè)知，圖G 中至少有 n 條邊，故必有圈，不妨設(shè)此圈為v1v2vr v1 ，（否則可將這 n 個(gè)數(shù)重新編號(hào)；又對(duì)于互不相等的若干個(gè) n 位正整數(shù)，同時(shí)將每個(gè)數(shù)的第i, j 位數(shù)字對(duì)換位置，并不改變本題的性質(zhì)），那么前r 個(gè)數(shù)為：a3 x4xr -1xrxn1a2x4xr -1xrxn=a3x3 x4xr -1xrxn= y1 y2 y3a4xnr ar -1 = y1xr -1xrxnar = y1 y2 y3 y4yr -1 xrxn）的第r 位數(shù)字后，所得這里，不同的字

9、母表示不同的數(shù)字，據(jù)此知，刪去各數(shù)（自2的兩個(gè) n -1位數(shù) arr 與a1r 并不相等，其中，= y1 y2 y3 y4arryr -1xr +1xn ， a2 x3 x4xr -1xr +1xn也就是說(shuō)，圈v1v2vr v1 中的邊vr v1 并不，.因此，圖G 中不可能有圈，故圖G 中的邊至多有 n -1條，這與反證法的假設(shè)相從而結(jié)論得證.，5 、設(shè)G 為 n 階圖(n ³ 5) ，其e ³ n + 4 ，證明G 中兩個(gè)無(wú)公共邊的圈.證：對(duì) n 歸納，當(dāng) n = 5 時(shí)， e ³ 9 ，這相當(dāng)于從 k5 中至多去掉一條邊，結(jié)論顯然成立.設(shè) n < k

10、(k ³ 6) 時(shí)結(jié)論成立，當(dāng) n = k 時(shí)， k 階圖G 的點(diǎn)數(shù)，其中必有圈.e ³ k + 4 ，由于G 的³ 頂若G 中一個(gè)長(zhǎng)為3 或4 的圈C1 ，則從圖G 中刪去圈C1 上所有的邊，剩下的k 階子圖G1 中，依然滿足：³頂點(diǎn)數(shù)，其中又有圈C2 ，顯然， C1 與C2 都是G 中的圈，且無(wú)公共邊.以下假設(shè)， G 中的每個(gè)圈長(zhǎng)至少為5 .若G 中有點(diǎn)v0 ，其度數(shù) d (v0 ) £ 1，則刪去點(diǎn)v0 以及它所關(guān)聯(lián)的邊，剩下的 k -1階子圖G2 中，有 k -1個(gè)頂點(diǎn)，至少(k -1) + 4 條邊，據(jù)歸納假設(shè)，G2 中有不含公共邊的

11、兩個(gè)圈， 它們當(dāng)然也是G 中的圈.若G 中有點(diǎn)v0 ，其度數(shù) d (v0 ) = 2 ，設(shè)與v0 鄰接的兩個(gè)點(diǎn)是v1,v2 ，顯然v1, v2 不相鄰（因G 中無(wú)三角形），此時(shí)，刪去點(diǎn)v0 及其所發(fā)出的兩條邊，同時(shí)添加邊v1v2 ，所得的圖G3中，有 k -1個(gè)頂點(diǎn)，至少(k -1) + 4 條邊，據(jù)歸納假設(shè)，G3 中有不含公共邊的兩個(gè)圈C1 與C2 . 再將邊v1v2 去掉，恢復(fù)被刪去的點(diǎn)v0 及其所發(fā)出的兩條邊v0v1, v0v2 ，回到圖G ，則G中也有不含公共邊的兩個(gè)圈（這是由于，若 G3 中的這兩個(gè)圈C1 與C2 都不含邊v1v2 ，則這兩個(gè)圈C1 與C2 也是G 中的圈；若G3 中

12、的這兩個(gè)圈中有一個(gè)，例如C2 ，含有邊v1v2 ，從該圈中去掉v1v2 ，并代之以邊v0v1, v0v2 ，得到圈C0 ，則C0 與C1 是G 中不含公共邊的兩個(gè)圈）.若G 中所有的點(diǎn) vi ，其度數(shù) d (vi ) ³ 3 ， i = 1, 2, k ，如果G 的> k + 4 ，我們就從G 中刪去一些邊，使得恰好為k + 4 ，記此圖為G4 .3在圖G4 中，若G4 中有一頂點(diǎn)的度數(shù)< 3 ，則據(jù)前面的討論，結(jié)論已經(jīng)得證；³ 3k若G 中每個(gè)頂點(diǎn)的度數(shù)皆³ 3 ，則G 中各頂點(diǎn)的度數(shù)之和³ 3k ，故G中的，即4442有 k + 4 &#

13、179; 3k ，由此得， k £ 8 . 而在此時(shí)，只要能證得，在G 中必有三角形或四邊形，這42種三角形或四邊形當(dāng)然也在G 中，這將與原先的假設(shè)（ G 中的每個(gè)圈長(zhǎng)至少為5 ）相.事實(shí)上，由于G4 中的k + 4 ³ 頂點(diǎn)數(shù)k ，故G4 中必有圈，設(shè)C 為極小圈，則圈C 的；設(shè)極小圈C 的長(zhǎng)為 r ，點(diǎn)與點(diǎn)之間不能再有其它邊相連，否則圈C 將被分成更小的圈則 r £ k - 2 .(由于每個(gè)頂點(diǎn)的度數(shù)皆³ 3 ，若 r = k ，則圈C 的點(diǎn)與點(diǎn)之間將有其它邊相連，圈C 被分成更小的圈，；若 r = k -1，圈C = v1v2vrv1 上的每個(gè)點(diǎn)都

14、要與圈外的，當(dāng)k = 5 或 k = 6 時(shí)，G4 中的極小圈C一點(diǎn)v0 相鄰，的長(zhǎng) r £ 4 .到三角形v0v1v2 ，)；當(dāng) k = 7 時(shí)，有 r £ 5，若極小圈C 為五邊形v1v2v3v4v5 ，另兩點(diǎn)為u, v ，五邊形的五個(gè)頂點(diǎn)共向u, v 發(fā)出至少5 條邊，則u, v 中必有一點(diǎn)，例如u ，要向五邊形的頂點(diǎn)發(fā)出至少3 條邊，其中必有兩個(gè)相鄰頂點(diǎn)，例如v1v2 都與u 相鄰，到三角形uv1v2 （更小的圈），矛盾，因此 r £ 4 ；當(dāng)k = 8 時(shí)，有 r £ 6 ，若極小圈為六邊形v1v2v3v4v5v6 ，六個(gè)頂點(diǎn)共向圈外的兩點(diǎn)u,

15、 v 發(fā)出至少6 條邊，則其中有一點(diǎn)，例如u ，要向六邊形的頂點(diǎn)發(fā)出至少3 條邊，點(diǎn)u 要向頂點(diǎn)組v1, v3, v5, v2 , v4 , v6中的一組發(fā)出至少2 條邊，設(shè)u 與v1, v3 相鄰，則得到四邊形v1v2v3u ，；若極小圈C 為五邊形v1v2v3v4v5 ，另三點(diǎn)為u, v, w ，五邊形的五個(gè)頂點(diǎn)共向u, v, w 發(fā)出至少5 條邊，必有一點(diǎn)，例如u ，要向五邊形的頂點(diǎn)發(fā)出至少2 條邊，由于五邊形的個(gè)頂點(diǎn)，要么相鄰，要么中間只隔一個(gè)頂點(diǎn)，因此得到一個(gè)含有點(diǎn)u的三角形或者四邊形，,因此r £ 4 .綜合以上討論，可知本題結(jié)論成立.6 、若簡(jiǎn)單圖G 有2n +1 個(gè)頂

16、點(diǎn)，至少3n +1 條邊(n ³ 2) ，證明： G 中必有偶圈證：由于圖G 的不小于頂點(diǎn)數(shù)，則G 中必有圈，今逐次這樣地去掉圖中的一些邊：使得每去掉一條邊，就破壞一個(gè)圈，這樣的操作至少可以進(jìn)行 n +1次，也就是至少可以去掉 n +1條邊，破壞至少 n +1個(gè)圈，即是說(shuō)，圖G 中的圈至少有n +1個(gè)這 n +1個(gè)圈中，必有兩個(gè)圈有公共邊，事實(shí)上如果個(gè)圈都無(wú)公共邊，由于每個(gè)圈至少有3 條邊，則圖G 至少有3(n +1) = 3n + 3 條邊，！今設(shè)C1,C2 是圖G 中兩個(gè)有公共邊的圈，則C1 至少有一條邊不在C2 中，C2 至少有一條邊4不在C1 中，若C1,C2 含有公共邊e

17、的最長(zhǎng)公共道路為C0 = ( AB) ，若設(shè)道路C0 有 r 條邊，圈C1 有 r1 條邊（公共路），圈C2 有 r2 條邊（公C1共路），（即圈C1,C2 的長(zhǎng)分別是 r1 , r2 ）AB若去掉道路C0 = ( AB) 間的所有的邊（即圈C1,C2 的上述公共邊），則圈C2C ,C 的剩下部分仍可合并為一個(gè)圈，記為C * ，圈C * 的長(zhǎng)為r + r - 2r ；1212注意三個(gè)圈C ,C ,C* 長(zhǎng)的和等于2(r + r - r) ，它是一個(gè)偶數(shù)，故三個(gè)加項(xiàng)1212r1, r2 和 r1 + r2 - 2r 中必有一個(gè)是偶數(shù)，即G 中有偶圈7 、一次足球邀請(qǐng)賽共安排了 n 支球隊(duì)參加，每

18、支球隊(duì)預(yù)定的比賽場(chǎng)數(shù)分別是m1, m2 , mn ，如果支球隊(duì)之間至多安排了一場(chǎng)比賽，則稱(chēng)(m1, m2 , mn ) 是一個(gè)有效安排；證明：如果(m1, m2 , mn ) 是一個(gè)有效安排，且 m1 ³ m2 ³³ mn ，則可取掉一支球隊(duì)，并重新調(diào)整各隊(duì)之間的對(duì)局情況，使得(m2 -1, m3 -1,是一個(gè)有效安排, m-1, m, mn ) 也m +1m +211證：設(shè)預(yù)定比賽 mi 場(chǎng)的隊(duì)為 Ai ， i = 1, 2, n ；（10 ）、如果 A 的 m 場(chǎng)比賽，其對(duì)手恰好就是 A , A , A，那么，直接去掉 A （當(dāng)m1 +111231然 A1 所

19、參與的所有比賽也就被取消了），則剩下的隊(duì) A2 , A3 , An 之間的比賽，以(m2 -1, m3 -1, m-1, m, mn ) 為有效安排m +1m +211（ 20 ）、如果球隊(duì) A , A , A 中，有些隊(duì)并未安排與 A 比賽，設(shè)在 A , A , A中，m1 +123n123，第一個(gè)未安排與 A1 比賽的隊(duì)是 Aj ，由于 A1 要賽 m1 場(chǎng)，那么在 A2 , A3 , Am +11自之外必有一個(gè)隊(duì)安排了與 A1 比賽，設(shè)為 Ak , (m1 +1 < k £ n) ，由于 mj > mk ，故必有一個(gè)隊(duì) As ，它被安排了與 Aj 比賽而未安排與 A

20、k 比賽，今對(duì)原安排作如下調(diào)整：AjA1A1Aj取消 A1, Ak 兩隊(duì)間、 Aj , As 兩隊(duì)間的比賽，AsAsAkAk改為 A , A 兩隊(duì)間， A , A 兩隊(duì)間進(jìn)行比賽，1jsk其它比賽安排不變；5經(jīng)過(guò)這一次調(diào)整之后，所有球隊(duì)的比賽場(chǎng)數(shù)不變，且是一個(gè)有效安排而第一個(gè)不與 A1 比賽的隊(duì)的序號(hào)，至少后移了一個(gè)位置；故限次這樣的調(diào)整之后，就化成了情形（10 ），因此結(jié)論得證8 、十個(gè)城市之間有兩個(gè)航空公司服務(wù)，其中任意兩個(gè)城市之間間不停），所有航線之間都是可往返的證明：至少有一個(gè)航空公司可以提供兩條互不相交的環(huán)形旅行線路，其中每條線城市個(gè)數(shù)都為奇數(shù)一條直達(dá)航線（中的（與其等價(jià)的圖論說(shuō)法是

21、：10 階完全圖 K10 的邊紅藍(lán) 2- 染色，則必兩個(gè)無(wú)公共頂點(diǎn)的同色奇圈（頂點(diǎn)個(gè)數(shù)為奇數(shù)的圈，且這兩個(gè)圈的邊或者同為紅色，或者同為藍(lán)色）證：首先注意，六階完全圖的邊紅藍(lán)2- 染色，據(jù)定理，必單色三角形V1V2V3 ，除去這個(gè)三角形外，在余下的七點(diǎn)之中，又有一個(gè)單色三角形V4V5V6 ，若這兩個(gè)三角形具有相同的顏色，證明已經(jīng)完成；不然的話，若這兩個(gè)三角形，一個(gè)是紅色的，一個(gè)是藍(lán)色的， 在這兩個(gè)三角形的頂點(diǎn)之間有9 條連線，其中至少有5 條同色，設(shè)為藍(lán)色；因此，有一個(gè)紅色三角形，從它的某個(gè)頂點(diǎn)發(fā)出兩條，的端點(diǎn)是藍(lán)色三角形的兩個(gè)頂點(diǎn)；這樣，我們找到兩個(gè)三角形，其中，一個(gè)是紅色邊的，一個(gè)是藍(lán)色邊的

22、，它們具有一個(gè)公共的頂點(diǎn)，（總共佔(zhàn)用了5 個(gè)頂點(diǎn)）；今考慮剩下的5 個(gè)頂點(diǎn)：若它們組成的完全圖 K5 中含有一個(gè)單色三角形，則證明已經(jīng)完成；若此完全圖 K5 中不含單色三角形，我們來(lái)證明，此時(shí) K5 的10 條邊，必定形成一個(gè)紅A色五邊形和一個(gè)藍(lán)色五邊形這是由于， K5 中不含單色三角形，則每點(diǎn)必定都是發(fā)出兩條紅邊，兩條；因?yàn)?，若點(diǎn) A 發(fā)出三條BEAB, AC, AD ，則點(diǎn) B, C, D 之間便不能再有，到紅色三角CD形 BCD ，！現(xiàn)在設(shè)點(diǎn)發(fā)出的兩條是 AB, AE ，則邊 BE 必為紅色；而點(diǎn) B 還需再發(fā)出一條，一條紅邊，設(shè) BC 為藍(lán)，BD 為紅；由此即推得， AC 必為紅，DE

23、 必為藍(lán)；AD 為紅，CD 為藍(lán)， CE 為紅從而命題得證藍(lán)色五邊形 ABCDE 和紅色五邊形 ACEBD 9 、在一次學(xué)術(shù)講演中有五名數(shù)學(xué)家參加，會(huì)上每人均打了兩次旽，且每?jī)扇司型瑫r(shí)在打旽的時(shí)刻，證明：一定有三人，他們有同時(shí)在打旽的時(shí)刻證：以V1, V2 , V10 這10 個(gè)點(diǎn)表示五位數(shù)學(xué)家的十次打旽，當(dāng)Vi , Vj 兩個(gè)旽有共同的時(shí)刻，則Vi , Vj 相鄰，這樣我們就得到一個(gè)10 階圖G ，由于每?jī)蓚€(gè)數(shù)學(xué)家同時(shí)打至少是C2 = 10 ，而G 的頂點(diǎn)數(shù)為10 ，故G 中必有圈旽的時(shí)刻，從而圖G 的56設(shè)在此圈中，Vk 是最先結(jié)束的一個(gè)旽，與Vk 相鄰的兩個(gè)頂點(diǎn)是Vk -1,Vk +1

24、 ，因Vk -1,Vk +1 這兩個(gè)旽與Vk 有共同的時(shí)刻，故當(dāng)旽Vk 結(jié)束的前一瞬間，Vk -1,Vk +1 這兩個(gè)旽還在繼續(xù)，這表明，三個(gè)旽Vk -1,Vk ,Vk +1 有共同進(jìn)行的時(shí)刻，而這三個(gè)旽顯然是屬于三個(gè)人的（若兩個(gè)旽屬于同一個(gè)人，又有共同的時(shí)刻，只能算成一個(gè)旽，?。?n ³ 2) 矩陣 A 中，每行及每列的元素中各有一個(gè)1和一個(gè)-1，其余元素10 、n ´ n皆為 0 ；證明：可以通過(guò)有限次行與行的交換以及列與列的交換，化為矩陣 B ，使得A + B = 0 .（即 A 中的每個(gè)數(shù)都變成了其相反數(shù)）證： n = 2 時(shí)結(jié)論顯然成立;以下考慮 n ³

25、 3 時(shí)的情況.記 n ´ n 矩陣第i 行、 j 列交叉位, aij Î0,1, -1，又用Vi 表示矩陣的第i 行， e j 表示第置上的元素為 aijj 列，（Vi , ej 僅表示位置，不代表具體元素與向量），今構(gòu)作一個(gè)以V1,V2,Vn 為頂點(diǎn)， e1, e2 , en 為邊的有向圖G 如下：當(dāng)?shù)趉 列的1在第i 行， -1在第 j 行，（即= 1,= -1），則aikajk條由點(diǎn)Vi 指向點(diǎn)Vj 的有向邊ek ，于是， G 的每個(gè)頂點(diǎn)都恰好具有1個(gè)出度和1個(gè)入度（即發(fā)出一個(gè)箭頭和收到一個(gè)箭頭），因此，從圖G 的任一頂點(diǎn)出發(fā)，沿箭頭方向前進(jìn)，必將回到原出發(fā)點(diǎn)，（這

26、是由于，除出發(fā)點(diǎn)外，每經(jīng)過(guò)一個(gè)點(diǎn)，就將耗去一個(gè)入度和一個(gè)出度，因此不能回到途經(jīng)的點(diǎn)）. 這樣，圖G 或者本身是一個(gè) n 階有向圈，或者是若干個(gè)不交的有向圈的并，（其中 k 個(gè)點(diǎn)的有向圈恰有k條有向邊，k ³ 3 .當(dāng) n ³ 3 時(shí)，這種圖G 與適合條件的矩陣 A 一一對(duì)應(yīng)）. 若后者情況出現(xiàn)時(shí)，如果刪去某個(gè)圈所涉及的行和列，并不影響其余圈的狀態(tài)；或者說(shuō)，若僅對(duì)某個(gè)圈所涉及的行和列進(jìn)行所述的變換，改變其它行和列中1和-1的位置.有一個(gè)圈(即G 為 n 階圈)的情況.示例如下：V1我們僅須考慮只V2e3-1 00010æççç00101

27、-1 0000010-1 0000-1 1000 ö÷e20 ÷0 ÷÷e5對(duì)應(yīng)的圈C 為：V5VA = ç14e40 ÷-1÷çe6ç0e1ç -11÷V6V3èø我們注意到：(1). 每當(dāng)交換矩陣中的兩行位置，等價(jià)于圈中僅交換相應(yīng)兩個(gè)頂點(diǎn)的位置，（邊的位置保持不動(dòng)）；(11). 每當(dāng)交換矩陣中的兩列位置，等價(jià)于圈中僅交換相應(yīng)兩條邊的位置，（僅交換兩條邊的代號(hào)，邊的箭頭方向以及頂點(diǎn)的位置保持不動(dòng)）.，我們可先對(duì)圈C1 的頂點(diǎn)作兩兩對(duì)換，得到圈C2 ，使得

28、沿箭頭方向前進(jìn)時(shí)，所經(jīng)歷的各點(diǎn)恰與圈C1 中各點(diǎn)的方向相反（例如在圈C1 中，的順序?yàn)閂1V2V4V3V6V5V1 ；而7在圈C2 中，的順序?yàn)閂1V5V6V3V4V2V1 ）.圈C2 ：圈C3 ：V1V1V5e3V5e6e2e5ee52V6V6V2V2e4e1ee63e1e4V4V3V4V3再對(duì)圈C2 的兩兩對(duì)換，（每次僅交換一對(duì)邊的代號(hào)，邊的箭頭方向及頂點(diǎn)的位置保持不動(dòng)）.使得每條關(guān)聯(lián)的頂點(diǎn)與圈C1 中的情況相同.矩陣 B ，其每個(gè)元素恰為矩陣 A 中相應(yīng)位置上元素的相反數(shù). 因此 A + B = 0 . 即所證的結(jié)論成立到圈C3 .與圈C3 所對(duì)應(yīng)的11、有七種顏色的珍珠，共計(jì)14 顆，

29、其中每種顏色的珍珠各兩顆；今把這些珍珠分裝于七個(gè)珠盒中，使得每個(gè)珠盒中各有一對(duì)不同顏色的珍珠；(1) 、證明：不論各盒中的珍珠怎樣搭配，總可以將這七個(gè)珠盒分別放置于一個(gè)正七邊形的七個(gè)頂點(diǎn)之上，使得七邊形的個(gè)相鄰頂點(diǎn)處所放置的盒中，四顆珍珠互不同色(2) 、如將以上條件與待證結(jié)論中的“七”一律改為“五”，14 改為10 ，則情況如何？(1) 、證：用點(diǎn)v1, v2, v7 分別表示這七種顏色，如果一個(gè)vi 色的珍珠和一個(gè)vj 色的珍珠裝在同一盒中( i ¹ j )，則在點(diǎn)vi 與vj 間條邊，這樣就得到一個(gè)圖G ，（點(diǎn)vi 與vj 之間有可能連出兩條邊），由于同的珍珠有兩顆，每顆珠都需

30、與一顆其它顏色的珍珠共盒， 則圖G 的每點(diǎn)恰好發(fā)出兩條邊；自G 的任一點(diǎn) A 出發(fā)，沿一條邊走到點(diǎn) B ，再由 B 沿另一條邊走到C ，如此下去，最后必定回到出發(fā)點(diǎn) A ，（這是由于，途中經(jīng)過(guò)的每個(gè)點(diǎn) P兩條邊，若能沿一條邊進(jìn)入點(diǎn) P ，則必沿另一條邊可離開(kāi)點(diǎn) P ，而由點(diǎn) P 不能再回到途中已經(jīng)過(guò)的點(diǎn)，因?yàn)檫@種點(diǎn)所發(fā)出的兩條邊都已走過(guò)，因此只能到達(dá)新點(diǎn)或回到出發(fā)點(diǎn)，而新點(diǎn)終將逐漸耗盡，最后必定回到出發(fā)點(diǎn) A ），這樣就得到一個(gè)圈AB去掉這個(gè)圈，若剩下還有點(diǎn)，依上述，又將得到新的圈，若稱(chēng)兩點(diǎn)的圈為“兩邊形”，則圖G 的結(jié)構(gòu)只有如下四種情況：(10 ) 、一個(gè)七邊形：(20 ) 、一個(gè)五邊形，一

31、個(gè)兩邊形：v1v1v7e4e6e1eev512v2e3vv62eve56e4v3v7e5v46e7e3e7ve23v5v48(30 ) 、一個(gè)四邊形，一個(gè)三角形：(40 ) 、一個(gè)三角形，兩個(gè)兩邊形：v1e5e2v4ve15e6e6e1vvv132e3v2e7v3v6v7e3對(duì)于每種情況，我們都對(duì)相應(yīng)的形的頂點(diǎn)之上，如右圖所示因此所證結(jié)論成立出適當(dāng)編號(hào)，并將這些對(duì)應(yīng)的珠盒放置于七邊e7e1(2) 、當(dāng) 14 顆七色珠改為 10 顆五色珠后，結(jié)論不成立，例如，e2對(duì)于五色v1, v2 , v3 , v4 , v5 ，我們?nèi)魧?0 顆珠這樣裝盒：e3e5e4= (v , v ), e = (v),

32、 ee, v，112223則無(wú)論怎樣擺放于正五邊形的頂點(diǎn)上，都不能滿足條件（因?yàn)?e1, e2 , e3 中，色的珠，無(wú)論怎樣擺放于正五邊形的頂點(diǎn)上，必有兩盒相鄰）盒同12 、給定31個(gè)正整數(shù) a1, a2, a31 ，若其中至少有94 對(duì)數(shù)互質(zhì)，證明：其中必四個(gè)數(shù) a, b, c, d ，滿足： (a, b) = (b, c) = (c, d ) = (d, a) = 1 證：用點(diǎn) A1, A2 , A31 分別代表這31個(gè)正整數(shù)，若(ai , aj ) =1，則令相應(yīng)點(diǎn) Ai , Aj 相31階簡(jiǎn)單圖G ，設(shè)點(diǎn) Ai 的度數(shù)為 di ，據(jù)條件，圖G 至少有94 條邊，不妨設(shè)，鄰，圖G 恰有

33、94 條邊，否則我們就去掉其中一些邊，并不影響問(wèn)題的性質(zhì)；= di (di -1) 個(gè)“點(diǎn)對(duì)”，據(jù)條件，C2與點(diǎn) A 相鄰的點(diǎn)有 d 個(gè)，它們iidi231= åi=131= 1 å1231åd + d + d= 2´94 = 188 ；若記d -MC 2，則 M2d1231diii2i=1i=131= 1 åd 2 - 94 ，由不等式， 1331 1 (å2d )2 ， 因此，i´ 31i2i=1i=1M ³× 942 - 94 = 94 ´157 >2，31故在 A1, A2 ,31

34、D, A31 中必有兩個(gè)點(diǎn) A, C ，其所鄰接的點(diǎn)中，AC具有相同的一個(gè)“點(diǎn)對(duì)”，設(shè)為 B, D ，即 ABCD 為四邊形，從而，B(a, b) = (b, c) = (c, d ) = (d, a) = 1 913 、奧運(yùn)會(huì)排球預(yù)選賽有 n 支球隊(duì)參加，其中每?jī)申?duì)比賽一場(chǎng)，每場(chǎng)比賽必決出勝負(fù)，如果其中有 k （ 3 £ k £ n ）支球隊(duì) A1, A2 , Ak ，滿足： A1 勝 A2 ， A2 勝 A3 ， Ak -1勝 Ak ， Ak 勝 A1 ，則稱(chēng)這 k 支球隊(duì)組成一個(gè) k 階連環(huán)套；證明：若全部 n 支球隊(duì)組成一個(gè) n 階連環(huán)套，則對(duì)于每個(gè) k （ 3 &

35、#163; k £ n ）及每支球隊(duì) Ai(1 £ i £ n) ， Ai 必另外某些球隊(duì)組成一個(gè) k 階連環(huán)套., Ak 為頂點(diǎn)，如球隊(duì) Ai 勝 Aj ，則在兩點(diǎn)間有向邊： Ai ® Aj ，證明：以 A1, A2,如此得 n 階競(jìng)賽圖G 據(jù)條件， G 的 n 個(gè)頂點(diǎn)可以排成一個(gè) n 階有向圈，設(shè)為：A1 ® A2 ®® An ® A1 ，G 的可沿箭頭方向相互到達(dá)先證明，任一球隊(duì) Ai 必在某個(gè)三階連環(huán)套中，用 Si , Ti 分別表示被 Ai 擊敗了的球隊(duì)集合和擊敗了 Ai 的所有球隊(duì)集合，由于G 雙向連通

36、，必有 A j Î Si , Ak ÎTi ，使 Aj ® Ak ，于是 Ai , Aj , Ak 組成三階連環(huán)套；(3 £ k < n) ，圖中假若已證得，對(duì)于 k以 Ai 為一頂點(diǎn)的 k 階連環(huán)套C = ( A1 A2AiAk A1 ) ，圈C 之外的點(diǎn)的集合為 M ；若 M 中有一點(diǎn) P ，它所表示的球隊(duì)既擊敗了圈C 中的某個(gè)隊(duì) Ak ，又被圈C 中的另一個(gè)Ak隊(duì) A j 所擊敗，點(diǎn) Ak , Aj 把圈C 分成兩條有向路C1, C2 ，其中一條，例如C1 ，它與有向路 Aj ® P ® Ak 組成有向圈，C2C1P依次考

37、慮路 C2 ： Aj , Aj+1, Aj+2 , Ak 上各點(diǎn)與點(diǎn) P 間的鄰接情Aj® PP ® Aj+r ® Aj+r +1 ，況，必有相鄰的兩點(diǎn) Aj+r , Aj+r +1 ，滿足 Aj+r A而，今去掉邊j+r+1® P ® Aj+r+1其間，便得到一個(gè)含有頂點(diǎn) Ai 的 k +1 階連環(huán)套；而將路 Aj+r若 M 中的任一點(diǎn) P ，它所表示的球隊(duì)要么擊敗了圈C 中的每個(gè)隊(duì)，要么被圈C 中的每個(gè)隊(duì)所擊敗，則集 M 可分為兩個(gè)不交的子集 S 與T ，其中 S 中的任一隊(duì)，戰(zhàn)勝了圈C 中所有的隊(duì)，而T 中的任一隊(duì)，負(fù)于圈C 中所有的隊(duì)；

38、由于圖G 雙向連通，故在集T 中必有點(diǎn)u ， 集 S 有點(diǎn)v ，使v ® u ，今在圈C 中任意去掉一個(gè)點(diǎn) A j ，( A j ¹ Ai )，而用路v ® u 代替，便得到一個(gè)含有頂點(diǎn) Ai 的 k +1 階連環(huán)套；故結(jié)論對(duì)于 k +1 成立，由歸納法，結(jié)論成立14 、某公司有17 個(gè)人，每個(gè)人都正好認(rèn)識(shí)另外的4 個(gè)人，證明：兩個(gè)人，他們彼10此不相識(shí)且沒(méi)有共同的熟人（第 26 屆獨(dú)聯(lián)體數(shù)學(xué)）證明：以17 個(gè)點(diǎn)表示公司的17 個(gè)人，如果兩人 x, y 相識(shí)，則令其相鄰，到17 階簡(jiǎn)單圖G ；據(jù)條件，對(duì)于每個(gè)頂點(diǎn) x ， d (x) = 4 ，我們需證明，頂點(diǎn) P

39、, Q ，滿足：P, Q 不相鄰，且不同與第三頂點(diǎn)相鄰反證法，假設(shè)G 中的任意兩點(diǎn)，或者相鄰，或者同與第三點(diǎn)相鄰，今考察其中任一點(diǎn) x ， 因?yàn)?d (x) = 4 ，故有點(diǎn) A, B, C, D 與 x 相鄰，討論不同的情況：10 、如果 A, B, C, D 四點(diǎn)之間有某兩點(diǎn)相鄰，例如 AB 相鄰，因 d (x) = 4 ，與 A 相鄰的另集合 M ，"P Î M ，兩點(diǎn)是 E, F（是C, D ），此外至少有10 個(gè)點(diǎn)與 A 不相鄰，它們因 P, A 不相鄰，則由假設(shè)，它們應(yīng)同與第三點(diǎn)相鄰，但與 A 相鄰且度數(shù)尚未滿 4 的點(diǎn)只有B, E, F ，故 P 必與 B,

40、E, F 之一相鄰；因?yàn)?P 是 M 中的任意點(diǎn)，故 M中的10 個(gè)點(diǎn)必與 B, E, F 之間至少連出10 條邊，從而B(niǎo), E, F 中有一點(diǎn)至少向 M 中的點(diǎn)發(fā)出4 條邊，這樣，該點(diǎn)的度數(shù)³ 5（因該點(diǎn)也與 A 相鄰），發(fā)生！D2DDEE31FA1FyC3DAACxPC2ABBMABCPx2xA3C1MCBB31DBD220 、據(jù)10 的討論知， A, B, C, D 中的不相鄰，又若 A, B, C, D 四點(diǎn)中有某兩點(diǎn)，例如 A, B ，它們除了都與 x 相鄰?fù)?，還都與另一點(diǎn) y 相鄰，因?yàn)閐 ( A) = 4 ，與 A 相鄰的另集合 M ，"P Î M

41、， P 必與 E, F ，外兩點(diǎn)是 E, F ，此外至少有9 點(diǎn)與 A 不相鄰，它們Y 之一相鄰，但 d (Y ) = 4 ，故與Y 相鄰的點(diǎn)，除 A, B 外，至多還有 M 中的兩點(diǎn)，因此，M中至少有7 點(diǎn)要向 E, F 之一發(fā)出邊，E, F 中必有一點(diǎn)向 M 引出至少4 條邊，則該點(diǎn)的度數(shù)大于4 ，！據(jù)10 ， 20 的討論可知， A, B, C, D 四點(diǎn)之間兩兩不相鄰，且除與 x 相鄰?fù)猓鼈儍蓛?1也不同與另外的點(diǎn)相鄰，但 A, B, C, D 的度數(shù)皆為4 ，因此除與 x 外，它們各與另外三個(gè)不同的點(diǎn)相鄰，如圖二，這樣已有16 條邊，其余還有17 ´ 4 -16 = 18

42、 條邊，并且圖中已有172個(gè)頂點(diǎn)，再有另外的頂點(diǎn)，而且據(jù)與10 相同的討論可知，與 A 相鄰的四點(diǎn)（x 及另三個(gè)未標(biāo)記號(hào)的點(diǎn) A1, A2 , A3 ），彼此之間不能相鄰因此，這18 條邊的每一條，只能在 Ai , Bi ,Ci , Di 間連結(jié)，每條邊，且經(jīng)過(guò) x 的圈，這樣共得18 個(gè)圈（每圈都過(guò) x ），條，便得到一個(gè)含有5由于頂點(diǎn) x 的任意性，經(jīng)過(guò)其余16 個(gè)點(diǎn)中任一個(gè)點(diǎn)也有18 個(gè)那樣的圈（共17´18 個(gè)），每一個(gè)圈過(guò)5 個(gè)頂點(diǎn)，因此每個(gè)圈重復(fù)計(jì)算了五遍17 ´18圈的個(gè)數(shù)等于，這不可能，故所設(shè)不真，從而證得了命題515 、若8 階簡(jiǎn)單圖不含四邊形，那么，其的

43、最大值是多少？（ CMO - 92 ） 解一：右圖是具有八個(gè)頂點(diǎn)，十一條邊的簡(jiǎn)單圖，其中沒(méi)有四邊形，今證明，11便是合于條件的最大值為此，只要證，具有12 條邊的簡(jiǎn)單圖中必先指出兩個(gè)事實(shí)：四邊形10 、如果點(diǎn) A 與點(diǎn)V ,V ,V 都相鄰， B 是異于 A 的一個(gè)頂點(diǎn)12k（ B 也可以是V1,V2 ,則圖中有四邊形,Vk 中的點(diǎn)），如果在V1,V2 ,Vk 中有某一“點(diǎn)對(duì)”與 B 相鄰，20 、四個(gè)頂點(diǎn)的圖中五條邊，就必有四邊形（相當(dāng)于一個(gè)四面體中去掉一條邊）現(xiàn)在設(shè)， G 具有八個(gè)頂點(diǎn)，十二條邊的簡(jiǎn)單圖，我們來(lái)證明， G 中必有四邊形反證法，假若G 中沒(méi)有四邊形，用 d1, d2 , d8

44、 分別表示G 中八個(gè)頂點(diǎn)的度數(shù)，8注意到， å di = 2 ´12 = 24 ，則有maxd1, d2 , d8 ³ 3 討論不同的情況：i=1情形一、若maxd1, d2 , d8 = 3 ，這時(shí)G 中每個(gè)頂點(diǎn)的度數(shù)都是3 ，一個(gè)頂點(diǎn) A1 ，與 A1 有邊相鄰的頂點(diǎn)設(shè)為 A2 , A3 , A4 ，其余四個(gè)頂點(diǎn)為 B1, B2 , B3 , B4 ；0據(jù)1 及反證法假設(shè)， B , B , B , B中的點(diǎn)與 A , A , A中的點(diǎn)之間相連的邊至多只有1234234四條，而A2 , A3 , A4中的點(diǎn)相連的邊至多只有一條，所以在B1, B2 , B3 ,

45、B4 這些點(diǎn)中相連的邊至少有12 - 3 - 4 -1 = 4 條（由20 可知，也只能有四條），我們只考慮這四個(gè)頂點(diǎn)以及連結(jié)它們的4 條邊，這時(shí)其中必有某一頂點(diǎn)的度數(shù)是1（如果這四個(gè)頂點(diǎn)的度數(shù)都是2 ，12就成為一個(gè)四邊形），從而有頂點(diǎn)度數(shù)為3 ，即B1, B2 , B3, B4 中必有一點(diǎn)（不妨設(shè)為 B1 ），與其它三點(diǎn)邊相連，而B(niǎo)1, B2 , B3 , B4 中的點(diǎn)與A2 , A3 , A4中的點(diǎn)相連的為4 ，B1 必與A2 , A3 , A4中的某一點(diǎn)有邊相連，這樣，圖G 中 B1 的度數(shù)將是4 ，這與假設(shè)！情形二、 maxd1, d2 , d8 = 4 ，取一個(gè)度數(shù)為4 的頂點(diǎn) A

46、 ，設(shè)與 A 有邊相連的頂點(diǎn)為0A , A , A , A ，其余三頂點(diǎn)為 B , B , B1A , A , A , A，據(jù)及反證法假設(shè)，內(nèi)部的邊12312341234至多是 2 條，點(diǎn)集B1 , B2 , B3 與A1, A2 , A3 , A4 之間的邊至多3 條，而B(niǎo)1 , B2 , B3 內(nèi)部的顯然至多3 條，由于總的是12 條，因此上述各種恰為2, 3, 3 ；，在A1, A2 , A3 , A4 內(nèi)部的邊恰好是2 條，且這兩條邊不能有公共頂點(diǎn)（否則將出現(xiàn)四邊形），不妨設(shè)這兩條l1 = A1 A2 ，l2 = A3 A4 ；B1 , B2 , B3 中的每一點(diǎn)都與A1, A2 ,

47、A3 , A4 中的某一點(diǎn)有邊相連，這種三條，稱(chēng)為“紅邊”，A3A2且因 B B , B B , B B 都是G 的邊，這三條紅，1 21 32 3AA14必有兩條的端點(diǎn)同時(shí)落在l1, l2 兩邊之一上，設(shè)為l1 上，B3B1它收到來(lái)自 B1, B2 發(fā)來(lái)的邊；如果這兩條紅邊都關(guān)聯(lián)l1 上的同B2一點(diǎn)（例如 A1 ），那么 A1B1B2 B3四邊形；如果這兩條紅邊關(guān)聯(lián)l1 上的不同點(diǎn) A1, A2 ，那么 A1 A2 B1B2四邊形；都與所設(shè)！情形三、maxd1, d2 , d8 > 4 ，取一個(gè)度數(shù)最大的頂點(diǎn) A ，與 A 鄰接的點(diǎn)集記為 S ，其= maxd1, d2 , d8 ，

48、m = T余頂點(diǎn)集記為T(mén) ，令 k =S， S,T 之間的至多m 條，T 內(nèi)部的邊至多C2 條， S 內(nèi)部的邊至多é k ù 條，這樣，圖G 的不超過(guò)êë 2 úûmk + m + C 2 + é k ù = 7 + C 2 + é k ù ，當(dāng)k = 5, 6, 7 時(shí)，都不可能使為12 êë 2 úûêë 2 úûmm綜上，知所求的最大值為11解二、將 n (n ³ 4) 階簡(jiǎn)單圖中，沒(méi)有四邊形的圖的的

49、最大值記為 Sn ，易見(jiàn) S4 = 4 ，下面考慮 n = 5 的情況，在有5 個(gè)頂點(diǎn)，6 條邊的簡(jiǎn)單圖中，由于各頂點(diǎn)的度數(shù)之和為12 ， 必有某頂點(diǎn)的度數(shù)不大于2 ，如果其中有一個(gè)頂點(diǎn)的度數(shù)為1，則可去掉這個(gè)頂點(diǎn)，化為有134 個(gè)頂點(diǎn)以及5 條邊的圖，其中必有四邊形；所以只要考慮每個(gè)頂點(diǎn)的度數(shù)皆不小于2 的情況；如果圖中有某頂點(diǎn) A 的度數(shù)為3 ，由 A 引出的AB, AC, AD ，另一頂點(diǎn) E ，因其度數(shù)不小于2 ，則與 B, C, D 三點(diǎn)中至少兩點(diǎn)相鄰，可見(jiàn)也有四邊形，如果圖中有某頂點(diǎn) P 的度數(shù)為4 ，由 P 引出的四條PA, PB, PC, PD ，因 A, B, C, D 各點(diǎn)

50、的度數(shù)皆不小于 2 ，由于度數(shù)總和為12 ，則 A, B, C, D 各點(diǎn)的度數(shù)皆等于 2 ，這時(shí)的確可以沒(méi)有四邊形；：在 n = 5 時(shí)，如果一個(gè)圖至少有7 條邊，則必有一個(gè)頂點(diǎn)的度數(shù)不大于2 ；去掉這個(gè)頂點(diǎn)（及其所發(fā)出的邊）化為4 個(gè)點(diǎn)，至少5 條邊的情況，據(jù)前所知，其中必有四邊形；因此 S5 = 6 ，并且具有6 條邊而沒(méi)有四邊形的5 階圖只有上圖所示的情況進(jìn)而可推出， S6 = 7 ；因?yàn)樵诰哂? 個(gè)頂點(diǎn)， 8 條邊的圖中，總有一個(gè)頂點(diǎn)的度數(shù)不大于 2 ，設(shè)為 P ；若 d (P) = 1，去掉點(diǎn) P ，化為有5 個(gè)頂點(diǎn)， 7 條邊的圖，據(jù)上知，其中有四邊形；若 d (P) = 2 ，

51、去掉點(diǎn) P ，化為有5 個(gè)頂點(diǎn)， 6 條邊的圖，且在這種情況下，沒(méi)有四邊形的圖只有一種形式：（其余情況四邊形）在此基礎(chǔ)上恢復(fù)所去掉的那個(gè)頂點(diǎn)及兩條邊，這兩條邊不論如何作，也總會(huì)產(chǎn)生四邊形， 即具有6 個(gè)頂點(diǎn)， 8 條邊的圖必有四邊形；因此 S6 = 7 ；另外，具有6 個(gè)頂點(diǎn)，7 條邊而無(wú)四邊形的圖，例如，進(jìn)而可推出，S7 = 9 ；因?yàn)樵诰哂? 個(gè)頂點(diǎn)，10 條邊的圖中，總有一個(gè)頂點(diǎn)的度數(shù)不大于2 ，去掉此頂點(diǎn)，化為具有6 個(gè)頂點(diǎn)，至少8 條邊的圖，據(jù) S6 = 7 可知，其中必有四邊形，因此7 頂10 邊的圖中必有四邊形；而對(duì)于7 頂9 邊的圖，沒(méi)有四邊形的圖是因此 S7 = 9 的，例如

52、：今證明，S8 = 11，首先，具有8 個(gè)頂點(diǎn)，11條邊而無(wú)四邊形的圖再證，具有8 個(gè)頂點(diǎn)，12 條邊的圖必有四邊形反證法，若這樣的圖沒(méi)有四邊形，如果有一點(diǎn)的度數(shù)不大于2 ，去掉該點(diǎn)，化為具有7 個(gè)頂點(diǎn)，至少10 條邊的圖，據(jù)以上，其中必有四邊形；與所設(shè)，例如，因此各點(diǎn)度數(shù)不小于3 ，因?yàn)? 個(gè)頂12 邊的圖，度數(shù)總和為24 ，頂點(diǎn)度數(shù)恰為3 ，14A ，若 A 發(fā)出的三AB, AC, AD ，這時(shí)圖中必有三角形（事實(shí)上，若無(wú)三角形，則 B, C, D 間不能有邊，與 B 相鄰的另兩頂點(diǎn)將是其余的點(diǎn)，異于 A, B, C, D 的點(diǎn)集設(shè)為E = E1, E2 , E3, E4 ，即與 B 相鄰

53、的另兩頂點(diǎn)在 E 中，對(duì)于C, D 也是如此，也就是說(shuō)，集B, C, D 與集 E 間的兩條邊，設(shè)為 E1B, E1C ，B, C, D 發(fā)出了6 條，故 E 中必有一點(diǎn)，例如 E1 ，至少ABE1C 為四邊形，?。┰O(shè) ABC 是圖中的一個(gè)三角形，由于每頂點(diǎn)度數(shù)恰為3 ，則 A, B, C 每點(diǎn)各外還發(fā)出了一條邊，今去掉三角形 ABC ，總共去掉6 條邊，剩下5 頂6 邊的圖，若沒(méi)有四邊形，據(jù)前所述，只有唯一的形式：這時(shí)有一頂點(diǎn)的度數(shù)為4 ，這與圖中“每頂點(diǎn)度數(shù)恰為3 ”！故所設(shè)不真，因此8 頂12 邊的圖必有四邊形從而本題所求的最大值為1116 、10 名選手參加乒乓球賽，每?jī)蓚€(gè)選手對(duì)賽一局

54、如果選手i 勝選手 j ，選手 j 勝選手 k ，選手 k 勝選手i ，則稱(chēng)為有一個(gè)三角形設(shè)Wi 和 Li 分別表示第i 個(gè)選手勝和敗的局?jǐn)?shù)，又如果選手i 勝選手 j 時(shí)，總有 Li +Wj ³ 8 求證：這次球賽恰有40 個(gè)三角形解：用點(diǎn)v1, v2, v10 表示這10 名選手，如果vi 勝vj ，則在相應(yīng)兩點(diǎn)間條有向?。? )( )+-v ® v ，如此得10 階有向圖G ，dv= w , dv= L ，且W + L = 9, i = 1, 2,10 ijiiiiii不妨設(shè)，W1 ³ W2 ³³ W10 ，則 L1 £ L2 &

55、#163;£ L10 ；由于圖G 共有45 條邊，每條邊產(chǎn)生1010一個(gè)出度和一個(gè)入度，故åWi = å Li = 45 ，從而 W1 ³ 5, W10 £ 4 ， L1 £ 4, L10 ³ 5 i=1i=1據(jù)條件，當(dāng)vi 勝vj ，有 Li +Wj ³ 8 ，則Wi + Lj £ 10 今證明，W1,W2,W10 只在5 和4 兩個(gè)數(shù)中取值(1) 、先證明，W1 = 5 ；反證法，假若W1 ³ 6 ，則 L1 £ 3 ，若vj 是被v1 擊敗的任一人，由 L1 +Wj ³ 8 得，Wj ³