圖論29電子科大楊春-文庫吧資料
2025-01-06 14:05本頁面
【正文】 定義 7 設(shè) m和 n是兩個正整數(shù)，如果存在最小的 r(m ,n)階的圖 G,使得 G中或者有 Km或者有 n個頂點的獨立集，則稱正整數(shù) r(m, n)為 (m, n)拉姆齊數(shù)。 Bollbas教授的 《 極值圖論 》 著作是經(jīng)典著作。拉姆齊問題是極值圖論中著名問題之一。若 G的每個頂點是 G的 β臨界點，稱該圖是 β 點臨界圖；若 G的每條邊均是 G的 β臨界邊，稱該圖是 β 邊臨界圖。 即點 v是 G的一個 β臨界點。 (2) 有 β臨界點的圖不一定有 β臨界邊。而： 表明 KU {v} 是 G的一個最小點覆蓋； 反之，若點 v含于 G的某個最小點覆蓋 K之中。 證明：若點 v是圖 G的 β臨界點，則： 取 Gv的一個最小點覆蓋 K。若 β(Gv) β(G) ,稱 v是 G的 β臨界點；若 β(Ge) β(G) ,稱 e是 G的 β臨界邊。(三 )、點臨界圖與邊臨界圖 定義 5 設(shè) G=(V ,E)是一個圖。 而在 G中找出了匹配： ｛ 16， 23， 45｝，所以 α‵(G) ≥3， 所以 α‵(G) =3。10 定理 3 設(shè) G是無孤立點的偶圖，則 G中最大點獨立集包含的頂點數(shù)等于最小邊覆蓋所包含的邊數(shù)。 例 1 確定下圖 G的 α(G)， β(G)， α‵(G) ， β‵(G)。 9 從 F的每個分支中選取一條邊，可作成 G的一個匹配，所以 α‵(G) ≥ n β‵(G)。 因為，階數(shù)為 n，邊數(shù)為 nk的森林包含 k個連通分支。 所以， F中的每個連通分支必然為星圖。 所以， F中不包含長度為 3和大于 3的跡。 若不然，設(shè) F中包含長度為 3的跡。 考慮導(dǎo)出子圖 F = G[X]。 所以，余下的 n2k個頂點至多需要 n2k條邊就可以被覆蓋，于是： β‵(G)≦ k+(n2k)=nk。最小邊覆蓋包含的邊數(shù)，稱為 G的邊覆蓋數(shù)，記為 β‵(G) 。 E的一個邊子集 L 稱為 G的一個邊覆蓋 ,如果 G中的每個頂點均是 L中某條邊的端點。6 注：一個邊獨立集實際上就是圖的一個匹配，一個最大邊獨立集就是圖的一個最大匹配。 E的一個邊子集 E1稱為 G的一個邊獨立集 ,如果 E1中的邊互不鄰接； G的一個包含邊數(shù)最多的邊獨立集稱為 G的最大邊獨立集。因為 G中每條邊的端點至少有一個在 K中，所以 G中每條邊的端點至多有一個在 VK中。因為 G中每條邊的端點最多一個在 V1中，所以 G中每條邊的端點至
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1