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