圖論29電子科大楊春(編輯修改稿)
2025-01-20 14:05 本頁面
【文章內(nèi)容簡介】 以得： α(G) = β‵(G) .定理得到證明。(三 )、點臨界圖與邊臨界圖 定義 5 設(shè) G=(V ,E)是一個圖。 v是 G的一個頂點， e是 G的一條邊。若 β(Gv) β(G) ,稱 v是 G的 β臨界點；若 β(Ge) β(G) ,稱 e是 G的 β臨界邊。 例如：vv是 G1的 2臨界點e2是 G2的 2臨界邊 容易知道：若 v是 G的一個 β臨界點，則：12 定理 4 點 v是圖 G的 β臨界點當且僅當 v含于 G的某個最小點覆蓋中。 證明：若點 v是圖 G的 β臨界點，則： 取 Gv的一個最小點覆蓋 K。 顯然 KU {v} 是 G的一個點覆蓋。而： 表明 KU {v} 是 G的一個最小點覆蓋； 反之，若點 v含于 G的某個最小點覆蓋 K之中。顯然 Kv構(gòu)成 Gv的點覆蓋，于是有：13 注： (1) 有 β臨界邊的圖必有 β臨界點。 (2) 有 β臨界點的圖不一定有 β臨界邊。例如：G G的每個點均是 2臨界點，但它的每條邊均不是 2臨界邊。 即點 v是 G的一個 β臨界點。14 定義 6 設(shè) G=(V ,E)是一個圖。若 G的每個頂點是 G的 β臨界點，稱該圖是 β 點臨界圖；若 G的每條邊均是 G的 β臨界邊，稱該圖是 β 邊臨界圖。 注： β 邊臨界圖一定是 β 點臨界圖，反之不一定！幾個邊臨界圖(四 )、拉姆齊數(shù) r (m, n)15 在圖論問題中，極值問題是最有意義但又是最令人感到困難的問題。拉姆齊問題是極值圖論中著名問題之一。 Erdos教授是極值圖論研究的中心人物。 Bollbas教授的 《 極值圖論 》 著作是經(jīng)典著作。 值得一提的是， 97年 (Fulkerson獎 )， 98年 (Fields獎 )， 99年 (Wolf 獎 )的世界三項數(shù)學(xué)大獎均與拉姆齊問題有關(guān)。 定義 7 設(shè) m和 n是兩個正整數(shù)，如果存在最小的 r(m ,n)階的圖 G,使得 G中或者有 Km或者有 n個頂點的獨立集，則稱正整數(shù) r(m, n)為 (m, n)拉姆齊數(shù)。16 拉姆齊 ( 19031930) 英國數(shù)學(xué)家。 1920年畢業(yè)于英國曼切斯特學(xué)院，隨后獲得獎學(xué)金入劍橋三一學(xué)院研究數(shù)學(xué)， 1924年當選為該學(xué)院 fellow。 1925年，拉姆齊發(fā)表第一篇重要學(xué)術(shù)論文 “數(shù)學(xué)的基礎(chǔ)”。拉姆齊問題是他的第二篇文章中提出的。 除數(shù)學(xué)外，拉姆齊在經(jīng)濟學(xué)和哲學(xué)方面興趣很高，但主要是在哲學(xué)方面。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1