離散作業(yè)第7章

第77-1：1，6（1證明在任何有向完全圖中所有結點入度的平方之和等于所有結點的出度平方之和。（6）證明：簡單圖的最大度小于結點數(shù)。7-2：1,2,3,4,7,9,10（1）在無向圖G中，從結點u到結點v有一條長度為偶數(shù)的通路，從結點u到結點v又有一條長度為奇數(shù)的通路，則在G中必有一條長度為奇數(shù)的回路。（2）若無向圖G中恰有兩個奇數(shù)度的結點，則這兩個結點間必有一條路。（3）若圖G是不連通的，則G的補圖G是連通的。（4）當且僅當G的一條邊e不包含在G的閉跡中時，e才是G的割邊。（7）在圖7-2.9中給出了一個有向圖，試求dv，v，dv，v及dv，v。此有向1 4 2 5 3 6圖對應的關系是否可傳遞的？如果不是可傳遞的，試求此圖的傳遞閉包。圖7-2.9（9）一個有向圖D是單側連通的，當且僅當它有一條經(jīng)過每一結點的路。（10）試證明徒弟每一個結點和每一條邊，都只包含于一個弱分圖中。7-3：1,2,3,4（1）求出圖7-3.9中有向圖的鄰接矩陣A從v到v長度為2和4的路，用計算A2，1 4A3和A4來驗證這個結論。圖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的完全關聯(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ù)和結點數(shù)。

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