離散作業(yè)第7章

第77-1：1，6（1證明在任何有向完全圖中所有結(jié)點(diǎn)入度的平方之和等于所有結(jié)點(diǎn)的出度平方之和。（6）證明：簡(jiǎn)單圖的最大度小于結(jié)點(diǎn)數(shù)。7-2：1,2,3,4,7,9,10（1）在無(wú)向圖G中，從結(jié)點(diǎn)u到結(jié)點(diǎn)v有一條長(zhǎng)度為偶數(shù)的通路，從結(jié)點(diǎn)u到結(jié)點(diǎn)v又有一條長(zhǎng)度為奇數(shù)的通路，則在G中必有一條長(zhǎng)度為奇數(shù)的回路。（2）若無(wú)向圖G中恰有兩個(gè)奇數(shù)度的結(jié)點(diǎn)，則這兩個(gè)結(jié)點(diǎn)間必有一條路。（3）若圖G是不連通的，則G的補(bǔ)圖G是連通的。（4）當(dāng)且僅當(dāng)G的一條邊e不包含在G的閉跡中時(shí)，e才是G的割邊。（7）在圖7-2.9中給出了一個(gè)有向圖，試求dv，v，dv，v及dv，v。此有向1 4 2 5 3 6圖對(duì)應(yīng)的關(guān)系是否可傳遞的？如果不是可傳遞的，試求此圖的傳遞閉包。圖7-2.9（9）一個(gè)有向圖D是單側(cè)連通的，當(dāng)且僅當(dāng)它有一條經(jīng)過(guò)每一結(jié)點(diǎn)的路。（10）試證明徒弟每一個(gè)結(jié)點(diǎn)和每一條邊，都只包含于一個(gè)弱分圖中。7-3：1,2,3,4（1）求出圖7-3.9中有向圖的鄰接矩陣A從v到v長(zhǎng)度為2和4的路，用計(jì)算A2，1 4A3和A4來(lái)驗(yàn)證這個(gè)結(jié)論。圖7-3.9（2）對(duì)于鄰接矩陣A的簡(jiǎn)單有向圖G，它的距離矩陣定義如下：d，如果dv，vj i jd0，對(duì)所有的i,2,...,njdk，這里k是使a(k)0的最小正整數(shù)j j確定由圖7-3.所示的有向圖的距離矩陣，并指出d1是什么意義？j（3圖.10中給出了一個(gè)有向圖，試求該圖的鄰接矩陣，并求出可達(dá)性矩陣和距離矩陣。圖7-0（4圖所示的圖G的完全關(guān)聯(lián)的矩陣，并驗(yàn)證其秩是否如定理72所述。圖7-4：5,6,9（）找一種9個(gè)a，9個(gè)b，9個(gè)c的圓形排列，使由字母{a,b,c}組成的長(zhǎng)度為3的27個(gè)字的每個(gè)字出現(xiàn)一次。（6b）畫(huà)一個(gè)有一條歐拉回路，但沒(méi)有一條漢密爾頓回路的圖。c）畫(huà)一個(gè)沒(méi)有一條歐拉回路，但有一條漢密爾頓回路的圖。（9如G具有漢密爾頓路，則對(duì)于V的每一個(gè)真子集S有W(GS)S17-5：5（1）證明：若G是每一個(gè)面至少由k(k3)條邊圍成的連通平面圖，則e里e，v分別是圖G的邊數(shù)和結(jié)點(diǎn)數(shù)。

，這k(v2)，這k2（5圖58各圖的平面圖象，否則說(shuō)明它包含一個(gè)與K或K在25 3,3度結(jié)點(diǎn)內(nèi)同構(gòu)的子圖。圖7-57-6：3,4,7（3奇鮑威爾法對(duì)圖7-6.各圖著色，求圖的著色數(shù)n。（） （）6（4）證明：若圖G是自對(duì)偶的，則e2v2。（7）一個(gè)完全圖K的邊涂上紅色或藍(lán)色。證明：對(duì)任何一種隨意涂邊的方法，總有一6個(gè)完全圖K的所有邊被涂上紅色，或者一個(gè)K的所有邊被涂上藍(lán)色。3 3b）證明：六個(gè)人的人群中，或者有三個(gè)人互相認(rèn)識(shí)或者有三個(gè)人彼此陌生。c對(duì)于n各結(jié)點(diǎn)的完全圖K的邊隨意涂上紅色或藍(lán)色有6條或更多條紅色n的邊關(guān)聯(lián)于一個(gè)結(jié)點(diǎn)，則存在著一個(gè)各邊都是紅色的K或者一個(gè)藍(lán)色的K。如果有條4 3或更多條藍(lán)色的邊關(guān)聯(lián)于一個(gè)結(jié)點(diǎn)，則存在一個(gè)紅色的K或者存在一個(gè)藍(lán)色的K。4 37-7：2,3,4（為2為3為4為1的結(jié)點(diǎn)。（有n個(gè)結(jié)點(diǎn)度數(shù)為2，n個(gè)結(jié)點(diǎn)度數(shù)為3…，n個(gè)結(jié)點(diǎn)度數(shù)為k個(gè)2 3 4度數(shù)為1的結(jié)點(diǎn)。（4設(shè)T和T是連通圖G的兩棵生成樹(shù)，a是在T不在T中的一條邊，證明存在邊b，1 2 1 2它在T中但不在T中，使得(T{a})和(T){a}都是G的生成樹(shù)。2 1 1 27-8：6（5）給定權(quán)1,4,9,16,