圖論28電子科大楊春(參考版)
2025-01-04 13:42本頁(yè)面
【正文】 ( 1 )22nn ?29 1 0 x t 0 1 2 ?1 ? 0 1 n 作業(yè) P256259 習(xí)題 9 ： 1 ， 2， 5， 7， 8， 11， 12， 13 30 1 0 x t 0 1 2 ?1 ? 0 1 n Thank You ! 31 1 0 x t 0 1 2 ?1 ? 0 1 n 謝謝觀看 /歡迎下載 BY FAITH I MEAN A VISION OF GOOD ONE CHERISHES AND THE ENTHUSIASM THAT PUSHES ONE TO SEEK ITS FULFILLMENT REGARDLESS OF OBSTACLES. BY FAITH I BY FAITH 。 28 1 0 x t 0 1 2 ?1 ? 0 1 n n階完全圖的定向有多少不同方式？ 定理 7 競(jìng)賽圖中存在有向 H圈。 u隊(duì)?wèi)?zhàn)勝了 v隊(duì)，則由點(diǎn) u向 v畫一條有向邊。而這兩個(gè)點(diǎn)中，一個(gè)點(diǎn)的入度比出度大 1，另一個(gè)點(diǎn)出度比入度大 1. 在各種比賽中，循環(huán)比賽是常見形式，即對(duì)與對(duì)之間 都要進(jìn)行比賽。 ( ) 1 ( ) 1D k k D??? ? ? ? ?27 1 0 x t 0 1 2 ?1 ? 0 1 n 定理 6 設(shè) D=(V,E) 是有向圖。 (1) 若 D中存在子圖 H使得對(duì)任意的 v ∈ V(H)均有 d+(v)0 (或 d(v)0),則 D中存在有向圈。由前面證明， e的端點(diǎn)著了不同色； 26 1 0 x t 0 1 2 ?1 ? 0 1 n 若 e不是 D1中邊，則因 A的極小性， D1+uv必然有唯一圈 C， 顯然， Cuv是 D1中的一條 (u, v)路，所以， u與 v著了不同色。 事實(shí)上：設(shè) e=uv是 D的任意一條邊。因?yàn)?D1中沒(méi)有有向圈，所以， u不可能在 Q上，于是 P的長(zhǎng)度至少為 i, 這表明 u沒(méi)有著 i色。 設(shè) P是 D1中的任意一條 (u, v)路。 如此得到 D1的 k+1個(gè)頂點(diǎn)子集： ｛ V1,V2,…,V k+1｝ 25 1 0 x t 0 1 2 ?1 ? 0 1 n 下面證明： ｛ V1,V2,…,V k+1｝ 構(gòu)成 D的色劃分。 設(shè) C=｛ 1,2,…,k+1 ｝ 是顏色集合。 G v2(5) v1(1) V6(3) v5(4) v4(7) v3(6) v7(2) 24 1 0 x t 0 1 2 ?1 ? 0 1 n 有向路的性質(zhì) (四 )、有向路與有向圈 定理 4 (加萊， 1968)有向圖 D中最長(zhǎng)有向路長(zhǎng)度下界是 ( )1D? 證明：設(shè) A是 D中使得 D1=DA不包含有向圈的極小邊集合。令 l (v3)=l (v2)+1=6, L =｛ v1,v7,v6,v5,v2,v3｝ , U=｛ v4｝ , A=｛ v1, v7, v7, v6 , v6, v5 , v4, v2, v2, v3 ｝ G v2(5) v1(1) V6(3) v5(4) v4 v3(6) v7(2) 23 1 0 x t 0 1 2 ?1 ? 0 1 n (2) 在 L中取 v3
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1