圖論28電子科大楊春-資料下載頁(yè)
2025-01-02 13:42本頁(yè)面
【正文】 1=DA不包含有向圈的極小邊集合。又假定 D1中最長(zhǎng)有向路的長(zhǎng)度為 k。 設(shè) C=｛ 1,2,…,k+1 ｝ 是顏色集合。按如下方法給 D1中頂點(diǎn)著色： 當(dāng) D1中以 v為起點(diǎn)的最長(zhǎng)有向路的長(zhǎng)度為 i1時(shí)，則給頂點(diǎn) v著上 i色。 如此得到 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的色劃分。 首先證明： D1中任意一條有向路的兩個(gè)端點(diǎn)一定著了不同顏色。 設(shè) P是 D1中的任意一條 (u, v)路。設(shè) v著了 i色，則以 v為起點(diǎn)的最長(zhǎng)路 Q的長(zhǎng)度為 i1。因?yàn)?D1中沒(méi)有有向圈，所以， u不可能在 Q上，于是 P的長(zhǎng)度至少為 i, 這表明 u沒(méi)有著 i色。 其次證明： D中任一有向邊的端點(diǎn)著了不同顏色。 事實(shí)上：設(shè) e=uv是 D的任意一條邊。若 e是 D1中邊，則因 e是路。由前面證明， 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著了不同色。 于是， 有向圈的性質(zhì) 定理 5 設(shè) D=(V,E) 是有向圖。 (1) 若 D中存在子圖 H使得對(duì)任意的 v ∈ V(H)均有 d+(v)0 (或 d(v)0),則 D中存在有向圈。 (2) 若 D連通，且對(duì)任意的 v ∈ V(D)均有 d+(v)=1(或 d(v)=1),則D中存在唯一有向圈。 ( ) 1 ( ) 1D k k D??? ? ? ? ?27 1 0 x t 0 1 2 ?1 ? 0 1 n 定理 6 設(shè) D=(V,E) 是有向圖。 D中存在有向歐拉環(huán)游，當(dāng)且僅當(dāng) D連通且每個(gè)點(diǎn)的出度和入度相等； D中存在有向歐拉跡，當(dāng)且僅當(dāng) D連通且除了兩個(gè)點(diǎn)外，每個(gè)點(diǎn)的出度和入度相等。而這兩個(gè)點(diǎn)中，一個(gè)點(diǎn)的入度比出度大 1，另一個(gè)點(diǎn)出度比入度大 1. 在各種比賽中，循環(huán)比賽是常見(jiàn)形式，即對(duì)與對(duì)之間 都要進(jìn)行比賽。 循環(huán)比賽的結(jié)果可以用所謂的“競(jìng)賽圖”來(lái)表示。 u隊(duì)?wèi)?zhàn)勝了 v隊(duì)，則由點(diǎn) u向 v畫(huà)一條有向邊。 顯然， “競(jìng)賽圖”是完全圖的一種定向圖。 28 1 0 x t 0 1 2 ?1 ? 0 1 n n階完全圖的定向有多少不同方式？ 定理 7 競(jìng)賽圖中存在有向 H圈。 從同構(gòu)的意義上看：一階競(jìng)賽圖有 1個(gè)；二階競(jìng)賽圖有 1個(gè)；三階競(jìng)賽圖有 2個(gè)；四階競(jìng)賽圖有 4個(gè)；五階競(jìng)賽圖有 12個(gè) . 12階競(jìng)賽圖超過(guò) 1540億個(gè)。 ( 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
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1