離散作業(yè)第7章

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

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