一 j d i s s e r t a t i o nf o r m a s t e rd e g r e e 2 0 1 1 u n i v c o d e 1 0 2 6 9 s t u d e n ti d 5 1 0 8 0 6 0 1 0 7 7 h o m e o m o r p h i c a l l yi r r e d u c i b l esp a n n i n g 皿 e e si n l o c a u yc o n n e c t e dg r a p h s d e p 盯t m e n t d e p a 砒m e n to fm a t h e m a t i c s m a j o r o p e r a t i o n a lr e s e a r c ha n dc y b e r n e t i c s d i r e c t i o n t o p 0 1 0 9 i c a lg r a p ht h e o 巧 s u p e i s o r c a n d i d a t e r e nh a n s h a ns o n 9 1 i n g 華東師范大學學位論文原創性聲明 葉 鴿 幫重聲明 本人所呈交的學位論文 廚泖巫疊閣憫同刪粵鱔僻東師范大學攻 讀硒生 博士 請勾選 學位期間 在導師的指導下進行的研究工作及取得的研究成果 除 文中已經注明引用的內容外 本論文不包含其他個人已經發表或撰寫過的研究成果 對本文 的研究做出重要貢獻的個人和集體 均已在文中作了明確說明并表示謝意 作者簽名 監絲日期 孫1 年5 月們日 華東師范大學學位論文著作權使用聲明 范大學根據相關規定保留和使用此學位論文 并向主管部門和相關機構如國家圖書館 中 信所和 知網 送交學位論文的印刷版和電子版 允許學位論文進入華東師范大學圖書館 及數據庫被查閱 借閱 同意學校將學位論文加入全國博士 碩士學位論文共建單位數據 庫進行檢索 將學位論文的標題摘要匯編出版 采用影印 縮印或其他方式合理復制學位論 文 本學位論文屬于 請勾選 1 經過華東師范大學相關部門審查核定的 內部 或 涉密 學位論文 于年 月日解密 解密后適用上述授權 u2 不保密 適用上述授權 學位論文作者簽名 夠繹放妊導師簽名 嗍幽盤豳墮吼絲 汐f f 涉密 學位論文應是已經華東師范大學學位評定委員會辦公室或保密委員會審定過的學位論文 需附獲批的 華 東師范大學研究生申請學位論文 涉密 審批表 方為有效 未經上述部門審定的學位論文均為公開學位論文 此聲明 欄不填寫的 默認為公開學位論文 均適用上述授權 鐔松齡碩士學位論文答辯委員會成員名單 姓名職稱單位備注 呂長虹教授華東師范大學主席 杜若霞副教授華東師范大學 郭軍偉副教授華東師范大學 摘要 如果一個連通圖的支撐樹不含有2 度點 則這棵樹被稱為是同胚不可約支撐 樹 h o m e o m o r p h i c a l l yi r r e d u c i b l es p a n n i n gt r e e 簡記為h i s t a h i u 猜想除蠔外的 任何一個平面三角剖分都含有一h i s t j m 刪t c h 將此猜想推廣到平面近三角剖分的 情形 a 1 b e r t s o n b e r m a n h u t c h i n s o n 和t h o m 嬲s e n 證明了推廣后的猜想 并且猜測任何 一個曲面三角剖分也含有一h i s t 本文證明任何一個頂點數至少是4 的局部連通圖都含有 h i s t 作為一個推論 便得到任何一個曲面三角剖分也含有一h i s t 的論斷 關鍵詞 局部連通圖 邊收縮 2 樹 邊不交支撐樹 三角剖分 同胚不可約支撐樹 a b s t r a c t as p a n n i n gt r e ew i t h o u tv e r t i c 鶴o fd e g r e e2i 8c a u e dah o m e o m o r p h i c a u yi r r e d u c i b l e s p a i l i l i n gt r e e h i s t a h i l lc o n j e c t u r e dt h a te v e 盯t r i 趿g u l a t i o no ft h ep l a n e0 t h e rt h 眥媧 c o n t a i l 培ah i s t j m a l k e v i t c he x t e n d e dt h i 8c o n j e c t u r et oan e a 卜t r i a n g u l a t i o no ft h ep l a i l e a2 c o n n e c t e dp l a n eg r a p hw i t ha ub u ta tm 0 8 to n e f 砬e sa r et r i a n g l e 8 a l b e r t s o n b e r m a n h u t c h i n s o n a n dt h o m a 豁e nc o n 丑m e dt h ec o n j e c t u r e m o r e o v e r t h e y 蹈k e dw h e t h e re t e 阿 擁口哪 地坑d n 可口5 t 正喲c ec d n t 口i 船口腳s zi nt h i 8p 印e r w es h o wt h a te v e 巧c o n n e c t e d 趿dl o c a u yc o n n e c t e dg r a p hw i t hm o r et h a j l3v e r t i c e sc o n t a l i 璐ah i s t c o 璐e q u e n t l y e v e 可 t r i a n g u l a t i o n0 fas u r ec o n t a i 璐ah i s t k e yw o r d s 1 0 c a u yc o n n e c t e dg r 印h e d g ec o n t r a u c t i o n 2 t r e e e d g ed 蠲o i n t8 p a n n i n g t r e 鵠 t r i a l i 州a t i o n h o m e o m o r p h i c a l l yi r r e d u c i b l es p a r l n i n gt r e 鶴 中文摘要 英文摘要 目錄 第一章 引言及預備知識 1 1 1 引言 1 1 2 網的基本概念 2 1 3 樹 5 1 3 三角剖分圖 5 第二章 局部連通圖簡介 6 2 1 局部連通圖的定義 6 2 2 局部連通圖的一些性質 7 2 3 關于局部連通圖的兩個猜想 8 2 4 缸樹和弦圖 8 第三章邊不交的支撐樹 1 0 3 1 定義及應用 1 0 3 2 局部連通圖中的邊不交支撐樹 1 1 第四章 局部連通圖中的同胚不可約支撐樹 1 4 4 1 同胚不可約支撐樹 1 2 4 2 弱2 樹 1 5 4 3 局部連通圖中的m s t 1 7 參考文獻 1 8 碩士期問完成的論文 2 0 后記 2 1 華東師范大學 局部連通圖中的同胚不可約支撐樹 第一章引言及預備知識 1 1 引言 如果一個連通圖的支撐樹不含有2 度點 則這棵樹被稱為是同胚不可約支撐 樹 h o m e o m o r p h i c a u yi r r e d u c i b l e8 p a i l i l i n gt r e e 簡記為h i s t 任意給定南 0 總可 以構造出一個圖 使其最小度6 如 但是不含有h i s t 比如 在 a b h t 9 0 中 取r 個j 0 拷貝 對每 個坼拷貝中的r 個點 每一個都與一個一度點連接 然后 添加另外的r 個獨 立點 每一個都與已構造圖中的r 2 個懸掛點連接 這個圖的最小度是r 但是不含有h i s t 然而 a l b e r t s o n b e r m a n h u t c h i 璐o n 和t h o m a u s s e n 證明含有n 個點的連通圖g 如果最 小度6 g 4 鉅元 則g 含有h i s t 應用相同的技巧 可以證明 對每一個正整數d l 和 任給的常數c o 如果g 的最小度至少為c 何 則g 含有一支撐樹不含有2 3 d 度 點 他們同樣證明說如果g 不是蠔并且g 的任意兩個點之間都有一條長為2 的路 則g 含有h i s t a l b e r t s o n b e r m a n h u t c h i 璐o n 和t h o m a s s e n 同樣指出 任給一個圖g 決定 g 是否含有h i s t 是n p 困難的 緊接著 他們問 決定一個最大度為3 的圖是否含有h i s t 是不是n p 網難的 這個問題已經被人解決 答案是肯定的 但是截止目前 結論尚未公開 發表 將一個圖是否含有h i s t 的問題限制在平面圖上來考慮 a h i n h i l 7 4 猜想說除颶 外的任何一個平面三角剖分都含有一h i s t j m a l k e v i t c h m a l 7 9 將此猜想推廣到平面 近三角剖分 除至多一個面外的所有面都是三角形的平面圖 的情形 a l b e i r t s o n b e r m 齟 h u t c h i n s o n 和t h o m a s s e n a b h t 9 0 1 證明了推廣后的猜想 并且猜測任何一個曲面三角剖 分也含有一h i s t d a v i d o w h u t c h i n s o n 和h u n e k e d h h 9 5 1 證明每一個環面上的三角剖 分圖都含有h i s t 本文證明任何一個頂點數至少是4 的局部連通圖都含有h i s t 作為一 個推論 便得到任何一個曲面三角剖分也含有一h i s t 的論斷 華東師范大學局部連通圖中的同胚不可約支撐樹 1 2 1 圖的定義 1 2 圖的基本概念 一個圖g 實際上就是一有序對 v g e g 這個有序對含有三個因素 其一 頂點集 y g 其二 與頂點集不交的邊集e g 其三 關聯函數妒g 它將g 的每一條邊與g 的頂 點集的二元無序對 有可能無序對中的兩個元素相同 相對應 如果e 是g 的 條邊 u 是g 的兩個頂點 并且有惦 e u 我們則說 e 和 t 分別關聯 同時 u t 也和e 關 聯 u 與 相互鄰接 這時 t l 移被稱為e 的端點 設 也是g 的一條邊 如果讓也與 關聯 我們則說e 和 鄰接 圖g 所含頂點的個數 也就是y g 所含元素的個數 通常用l y g i 來表示 圖g 所含邊的條數 也就是e g 所含元素的個數 通常用i e g i 來表示 在如上所定義的圖中 如果我們要求g 的每一條邊與g 的頂點集的不同頂點構成的二 元無序對相對應 則相應的圖稱為簡單圖 在后文中 如無特別指出 所有的圖都是簡單圖 假設g 是一個簡單圖 并且假設 是g 的一個頂點 我們將g 中所有與u 相鄰接的頂 點集合稱為u 的鄰域 記為 g u 如果不會引起混淆 則簡記為 u 的閉鄰域 記為 m u u 與頂點u 相鄰接的點的個數 也即是與點u 相關聯的邊的條數 也即是 所含元素的個數 被稱為 的度數 記為站 u 或者d u 圖g 中所有頂點的度數中 最小的被稱為g 的最小度 記為j g 相應地 最大度記為 g 假設g 是一個簡單圖 并且假設咖e l u l e 2 u 2 e 3 u 3 饑一l e t 毗是g 中一個點邊序列 則這 個序列稱為g 的一條長為t 的鏈 咖和u t 稱為鏈的始點和端點 如果這個鏈的所有點和邊 都互不相同 則相應的鏈稱為g 的一條路 路上的除端點之外的點稱為是路的內點 我們 用r 來表示含有n 個點的路 或者長為禮一1 的路 一般地 設p 是一條路 z 可是路上的兩個點 則z p 表示以z 秒為端點 以p 上位于 z 可之間的點為內點的一條路 如果一條路的始點和端點相同 則這條路是一個圈 我們用g 來表示長為釓的圈 設g 是一個含有n 個頂點的簡單圖 如果g 的任何兩個點之間都有一條邊 則g 是一 個完全圖 記為 1 2 2 子圖 設g 是一個圖 頂點集是y g 邊集是e g 我們說圖h 是圖g 的一個子圖 如果 y 日 y g 并且e 日 e g 2 華東師范大學 局部連通圖中的同胚不可約支撐樹 給定g 的子圖h 如果我們有y 日 y g 我們則說日是g 的支撐子圖 設g 是一個恰好含有禮個頂點的圖 如果g 含有一個支撐圈 或者說長為n 的圈作為 子圖 我們則說這個圈是g 的哈密爾頓圈 此時 也說g 是哈密爾頓的 1 2 3 導出子圖 設g 是一個圖 頂點集是y g 邊集是e g 假設s y g 現在定義g 的一個子 圖日如下 iy h s le 日 u u i u s 并且u u e g 此時 我們稱日是g 的點導出子圖 或者是由s 導出的子圖 記為g 翻 如果g 鄙是一個 完全圖 我們則說s 是一個團 1 2 4 圖同構 設g 和日是兩個圖 如果有y g y 日 e g e 日 并且妒g 妒日 則說g 與 日相等 記為g 日 通常而言 我們說兩個圖g 和日同構 記為g 望日 如果存在雙射口 y g 一 y 日 和 e g e 日 滿足惦 e t i u 當且僅當妒日 e 口 u p u 此時 這一對雙射 口 咖被稱為g 和h 間的同構映射 1 2 5 圖的幾個運算 給定圖g 設s 是y g 的一個子集 那么g s 則表示g 的一個子圖 通過刪除s 中的頂點和所有與s 中的頂點關聯的邊而得到 特別地 如果s z 則g s 簡記為 g z 給定圖g 設t 是e g 的一個子集 那么g t 則表示g 的一個子圖 與g 具有相同 的頂點集 而邊集則通過從e g 中刪除丁中的邊而得到 特別地 如果t e 則g t 簡記為g e 給定圖g 及g 的一條邊e z 我們等同頂點z 和可 將這個新點記為叫 然后構造一 個新圖g 7 如下 jy g 7 y g z 暑 u 叫 le g 7 t u l t u e g t u 隹 z 暑 u z 叫i z z e g 或者矽名 e g 3 華東師范大學局部連通圖中的同胚不可約支撐樹 值得注意的是 即使在g 中我們有z 名和妒都是邊 在新圖中我們只有叫z 這一條邊 因此 g 是一個簡單圖 我們稱如上所描述的圖運算為邊收縮運算 一般地 我們用g e 來表示 g 7 給定一個圖g 如果我們將g 的某些邊用路來代替 則所得的圖稱為是原圖的一個細 分 比如說 長為8 的圈是長為4 的圈的 個細分 給定一個圖g 如果圖 可以通過收縮g 中的一些邊和刪除g 中的一些邊而得到 則 日稱為是g 的一個子式 給定圖g 和日 則gn 日 y g ny 日 e g ne 類似地 gu 日 y g u y 日 e g ue 日 1 2 6 圖的連通性 假設g 是一個非平凡圖 也即是說g 含有至少兩個頂點 我們說g 是連通的 如果g 的任何兩個頂點之間都有一條路相連接 設p 和q 是g 的兩條路 我們說p 和q 內部不交 如果p 和q 具有不同的內點 如果g 的任何兩個頂點間都有至少兩條內部不交的路 則g 被稱為是2 連通的 相應 地 任意給定正整數后 可以定義 連通 設g 是一個圖 任給g 的兩個頂點 根據這兩個點之間是否有路連接可以將g 的頂點 分類 也就是說 如果z 之間有路連接 則將z y 放在同一個類中 每一個頂點類的導出 子圖稱為g 的一個連通分支 設g 是一個圖 o 是g 的一個頂點 e 是g 的一條邊 如果g z 的連通分支的個數比 g 的多 則稱z 為g 的一個割點 相應地 如果g e 的連通分支的個數比g 的多 則稱e 為g 的一條割邊 定理1 設g 是一個圖 e 是g 的一條邊 如果e 在一個圈上 則e 不是g 的割邊 證明 反設e z 是g 的 條割邊 則在g e 中有兩個連通分支g 1 g 2 使得在g 中g 1 g 2 在同一個分支里并且g 1 中的任何一個點與g 2 中的任何一個點之間的路都經過 e 特別地 和鈔之間的所有路都必須經過e 因此 e 不在任何圈上 這是一個矛盾 從而 e 不是g 的割邊 口 4 華東師范大學局部連通圖中的同胚不可約支撐樹 1 3 樹 一個無圈的連通圖 被稱為樹 關于樹 我們有如下的定理 定理2 設t 是一棵樹并且t 恰好含有禮個頂點 則丁的邊數為n 一1 為了證明定理2 我們需要下面的引理 引理3 設g 是一個圖 如果6 g 2 則g 含有圍 證明 取g 中的一條最長路p 并且假設z 是尸的一個端點 因為j g 2 z 肯定會 和一個不同于它在j p 上的鄰點的頂點鄰接 設那個點為y 但是 p 是g 中的最長路 所以 可一定在尸上 這樣 z yuz 尸y 形成了一個圈 口 現在我們來證明定理2 證明 我們對丁的頂點數作歸納 當頂點數是2 時 結論顯然成立 根據引理3 丁含 有一度點 比方說z 是丁的一個一度點 則 丁一z 仍然是一棵樹 根據歸納假設 丁一z 含有 n 一2 條邊 因此 t 含有n 一1 條邊 因為在刪除z 的同時 我們恰巧刪除了一條t 的邊 口 推論4 設g 是一個恰含有禮個頂點的連通圖 如果g 所含的邊數最小 則g 是一棵樹 證明 g 不可能含有圈 否則刪掉某個圈上的一條邊所得圖依然連通 但是具有更小 的邊數 因此g 是樹 口 定理5 設g 是一個連通圖 則g 含有一支撐樹 證明 我們對g 的邊數進行歸納 設g 具有禮個頂點 則根據推論4g 所含的邊數最 小為n 一1 如果g 不含有圈 則g 本身就是一棵樹 現在 假設c 是g 的一個圈 刪除c 上的一條邊 所得圖還是連通的 根據歸納假設 所得圖含有一支撐樹 那也是原圖的支撐 樹 口 1 4 1 嵌入 1 4 三角剖分圖 一個連通的2 維流形被稱為是一個曲面 給定一個曲面 和一個圖g 如果g 可以被 畫在r 上 使得g 的邊只在其端點處與別的邊相交 則說g 可以嵌入在i 上 5 華東師范大學 局部連通圖中的同胚不可約支撐樹 特別地 如果g 在平面上有一個嵌入 則稱g 是一個平面圖 設g 是一個嵌入在曲面r 上的圖 則 一g 的各個弧連通的區域被稱為嵌入圖g 的 面 其中 一g 表示從點集r 中除去在g 的邊上的那些點 1 4 2 三角剖分圖 設g 是一個嵌入在曲面r 上的圖 如果g 的各個面都是三角形 則稱g 三角剖分曲面 r 或者g 是一個曲面三角剖分圖 特別地 如果r 是一個平面 我們說g 是一個平面二角 剖分 關于三角剖分圖 我們有如下引理 引理6 r 軌廁每一個頂點數至少為彳的三角剖分圖部是局部哈密爾頓連通的俗個點的 鄰域的導出子圖是哈密爾頓的1 第二章局部連通圖簡介 本節所討論的圖 如無特別指出 都是連通圖 2 1 1 局部連通圖的基本概念 2 1 局部連通圖的定義 定義1 設g 是一個圖 如果g 的每一個頂點的鄰域的導出子圖都是連通的 則稱g 局部 連通的 根據局部連通圖的定義 局部連通圖具有如下性質 食題1 設g 是一個至少含有3 個頂點的局部連通圖 則g 的每一條邊都在一個三角形中 證明 設e z 可是g 中任給的一條邊 因為g 含有至少三個頂點 并且g 是局部連 通的 則z 一定會和可的鄰域中的另一個點 不妨設名鄰接 因此 z 鱸形成一個三角形 口 2 1 2 關于局部連通圖的一些結論 局部連通圖的概念最早是在1 9 7 4 年由c h a r t r a n d 和p i p p e r t 在他們的文章二d 坳 c t d 住n e c t 耐g r 印凰 c p 7 羽中提出來的 他們證明了如下結論 6 華東師范大學 局部連通圖中的同胚不可約支撐樹 1 如果g 是局部七一連通的 則g 本身是七 1 連通的 2 每一個局部3 連通圖都是非平面圖 3 如果g 是局部連通的 含有至少3 個頂點 最大度至多是4 則g 或者是哈密爾頓的或 者 一構于k l 1 3 2 2 1 局部連通圖的一些性質 2 2 局部連通圖的一些性質 1 9 7 9 年 o b e r l y 和s u m n e r o s 7 9 證明說如果一個連通且局部連通的圖不含坼 3 則 g 是哈密爾頓的 個幽g 稱為是上可嵌入的如果g 的最大虧格為 m 一禮 1 j 其中m n 分別為g 的邊數和頂點數 n e b e s 蛐 n e b 8 1 在1 9 8 1 年證明 每一個連通且局部連通圖都是上可嵌入 的 一個n 階圖g 稱為是頂點泛圈的 如果g 的每一個頂點都在一個長度為七的圈上 對 于每一個3 七 n 1 9 8 1 年 c l a i r k c l a 8 1 證明每一個連通且局部連通的不含k l 3 的圖都 是頂點泛圈的 同時 他證明每一個連通且局部3 連通的不含坼 3 的圖是泛連通的 也即是 說 g 的任何兩個頂點u t 之間都有一條長為 的路 對于每一個3 t n 一1 2 2 2 局部連通圖的可收縮邊 定義2 設g 是一個局部連通圖 e 是g 的一條邊 我們說e 是g 的一條可收縮邊 如果 g e 仍然是局部連通的 定理8 設g 是一個頂點數至少為2 的局部連通圖 則對于g 的任一個頂點u g 有一條 可收縮l 邊e u u 證明 取u 使得t 不是g 讓 的割點 接下來 我們將會證明t u 是g 的一 條可收縮邊 記日 g 幾u 很顯然 日是連通的 因此只需要證明日局部連通即可 設伽為日中 的通過收縮讓t 而得到的新頂點 對任意z y h 我們分如下兩種情況來證明 情形l z 刪 如果叫譬 日 z 日 z g z 因為g 小 g 0 是連通的 因此我們知道馴 日 z 是 7 華東師范大學局部連通圖中的同胚不可約支撐樹 連通的 因此我們假定硼 眥 z 如果i g z n u u i 1 那么我們有g g z 是 日 z 的支撐子圖 如果 g z 我們同樣有g g 是日 蜥 z 的支撐子 圖 無論哪種情況 我們都有何 z 是連通的 因為g f b 是連通的 情形2 z 塒 在這種情況下 蜥 砌 t t 一u u g u 一u 假設g l g 2 g m 是g g u 一u 的 分支 因為g g 是連通的 對任意1 i m y g n g 一t 1 y g n g t d 因為g g u 一u 的連通性 我們知道 蜥 牡 g 一u ug lug 2 ug m 是連通 的 口 從以上證明可以看出 如果局部連通圖g 的頂點數至少為3 則g 的每個頂點至少與兩 條可收縮邊相關聯 2 3 1 猜想一 2 3關于局部連通圖的兩個猜想 設g 是一個連通且局部n 一連通的圖 如果g 不含導出的k 1 七 2 則g 是哈密爾頓的 的 參見 o s 7 9 以上猜想對七 1 的情形已經在 o s 7 9 中證明了 2 3 2 猜想二 一個圖稱為是弱泛圈的 如果這個圖含有從其圍長 最短圈的長度 至周長 最長圈的 長度 之間的每一個長度的圈 對于局部連通圖 我們有如下猜想 連通且局部連通圖是弱泛圈的 2 4 七一樹和弦圖 在第一節中 引理6 說三角剖分圖都是局部連通圖 接下來 我們將證明七一樹和2 連 通的弦圖是局部連通的 8 華東師范大學局部連通圖中的同胚不可約支撐樹 2 4 1 關于七 樹的一些性質 定義3 任給一個正整數七 圖g 稱為是一個缸樹 如果存在g 的頂點的一個排序 u l 噸 七 仇 n u 1 忱 仇一l 是一個七團 很顯然 1 樹就是通常定義的樹 h w a i l g 戤c h a r d s 和w i n t e r h r w 9 2 證明2 樹是 m 凹i m 口ls e n e s p o m f f e f 圖 關于3 樹和一般七一樹的研究可參見 a p 8 6 a c p 8 7 a p 8 9 a p c 9 0 l m n w 0 6 1 定理9 對于后 2 七 樹是局部連通的 證明 設g 是一缸樹 我們對g 的頂點數進行歸納 最小的七 樹是一個頂點數為 七的完全圖 顯然是局部連通的 一般地 假設u 1 晚 在g 中除 中的點 外 其他頂點的鄰域與在g 一 中相同 因此我們只需要考慮 f 各個點的局部連 通性 根據七 樹的定義 g 是一個完全圖 因此是連通的 對于珧 1 t 七 g 鼽 g g 璣 u y 1 沈 璣一l 鼽 1 鯫 是連通的 口 2 4 2 弦圖 設g 是一個圖 c 是g 的一個圈 e 是g 的一條邊 如過e 的兩個端點在c 上但是e 不 是c 的一條邊 則稱e 是g 的一條弦 一個圖g 稱為是弦圖 如果g 的每一個長度大于3 的圈都含有弦 定義4 設g 是一個圖 鈔是g 的一個頂點 那么u 被稱為是s i m p 托c i o j 的當且僅當g u 是一個完全圖 關于弦圖 我們有如下的著名論斷 引理1 0 眈r 鋤弦圖有一個鰣唧屁c i 口2 的頂點 2 4 3 關于弦圖的一些結論 引理1 1 設g 是一個參連通的弦圖 含有至少彳個頂點口是一個3 唧屁c i 口f 的頂點 那么 g t 是2 連通的 9 華東師范大學局部連通圖中的同胚不可約支撐樹 證明 當u 的度至少為3 時 易于說明 因此假設 佃 可1 反設g u 不是2 連 通的 則z 之一為g 一 的割點 不失一般性 設z 是這樣一個割點 并且假定g l 和g 2 是g 一 一z 的兩個分支 因為g 含有至少4 個頂點 g l 和g 2 分別含有至少一個頂點 因 為在g 中g 1 和g 2 之間至少有兩條內部不交的路 因此秒有鄰點在g 和g 2 中 但是因為 t 是一個8 i m p l i c i a l 的頂點 其鄰域中任何兩個點之間都有邊 這和g 1 和g 2 是g u z 的連通分支相矛盾 因此g u 是2 連通的 口 定理1 2 設g 是一個廖連通的弦圖 則g 是局糊的 證明 我們對g 的頂點數n 進行歸納 當n 3 時g 媧 顯然是局部連通的 一般 地 根據引理1 0 設 是g 的一個s i m p l i c i a l 頂點 根據引理1 1 g u 是2 一連通的 岡為 g 一 是2 連通的弦圖 根據歸納假設 g 一 是局部連通的 現在來討論g 的局部連通性 因為y g m 中的點的鄰域在g 中與在g u 中相同 兇此我們只需討論 m 中各個 點的鄰域的導出子圖是否連通 首先g f 1 是一個完全圖 是連通的 記g 7 g u 對 于z 移 g z g g u u u y b u z 是連通的 口 第三章邊不交的支撐樹 3 1 定義及應用 設g 是一個圖 如果丑和死 是g 的兩棵支撐樹 并且噩和乃沒有公共邊 那么我們 稱互和疋是g 的邊不交的支撐樹 圖的邊不交的支撐樹在網絡理論中有很多應用 關于這方面的研究可以參考 l h m r 9 8 s s p 9 6 同時 圖的邊不交的支撐樹在組合理論中也有很多應用 例如 根據 x u 0 7 9 一個 圖是上可嵌入的如果g 有一支撐樹t 使得g e t 至多只有一個奇分支 一個含有奇數 條邊的連通分支 因此 如果能夠證明g 含有兩個邊不交的支撐樹 則g 是上可嵌入的 如果g 含有兩個邊不交的支撐樹 則g 可以寫成兩個偶圖 所有頂點的度都是偶數 的圖 的并 同時 我們知道一個圖有處處非零的垂流當且僅當g 可以寫成兩個偶圖的并 i w 巍9 6 p 3 1 0 因此 如果g 含有兩個邊不交的支撐樹 則g 有處處非零的4 流 1 0 華東師范大學局部連通圖中的同胚不可約支撐樹 3 2局部連通圖中的邊不交支撐樹 3 2 1 邊不交支撐樹在局部連通圖中的擴張性 引理1 3 設g 是一個局考隧通圖 e 是g 的一條可收縮邊 如果g e 含有兩個邊不交的支 撐樹 則g 也含有兩個邊不交的支撐樹 證明 設e z 并且假設伽是通過收縮e 所得的g g e 中的新點 因為g z 足連通的 我們不妨設可與z 的另一個鄰點z 相鄰接 讓n 和乃是g e 的兩個邊不交的 支撐樹 我們將對n 和死進行修正 使其成為g 的邊不交的支撐樹 將伽在乃和死中都用 替換 同時刪除丑和死中的本不是g 的那些邊 這些邊對應 于g 中一條與z 相關聯的邊 將所得圖記為躉和巧 不失一般性 設凡 最 昂為躉 的分支 吼 風為z 的分支 進一步 假設y 所在的分支分別為只和凰 將相應 的最 b 昂和地 風 風中的與刪在g 中鄰接而只與z 在g 中鄰接的那些邊記 為e 2 e 3 e p 和尼 厶 因為乃和乃邊不交 e 2 e 3 e p 和如 厶 q 互不相 同 情形1 z 也在r 和皿中 此時墨u z 3 e 2 e 3 e p 和砭u z z 厶 3 厶 為g 的兩個邊不交的支撐樹 情形2 不失一般性 設在肌中2 與 不在同一個分支中 此時礙u z 耖 e 2 e 3 e p 和zu 轤 厶 厶 為g 的兩個邊不交的支撐樹 口 3 2 2 局部連通圖所含的邊數 引理1 4 設g 是一個恰有n 個頂點的局部連通圖 則g 至少含有2 n 一3 條 邊 證明 我們對n i y g l 進行歸納 當n 1 2 時 結論顯然成立 根據定理8 我們收 縮邊 比如說z y 并將所得圖記為g 根據歸納假設 g 含有至少2 n 一1 一3 條邊 并且這 2 n 1 一3 條邊在g 中都有相應的邊與之相對應 同時 根據命題7 在g 中 z 可在一個三 角形中 當收縮z g 7 比g 至少減少了兩條邊 因此g 含有至少2 佗一1 一3 2 2 n 3 條邊 口 華東師范大學局部連通圖中的同胚不可約支撐樹 3 2 3 局部連通圖中的邊不交支撐樹 根據定理9 我們知道2 樹是局部連通的 同時再根據引理1 4 我們知道2 樹是同階的 局部連通中邊數最小的一個 2 樹含有恰好2 佗一3 條邊 下面的定理將要說明 如果一個 局部連通圖g 只含有 一3 條邊 那么g 是一2 樹 定理1 5 設g 是一個恰含n 個頂點的局部連通圖 則g 具有恰好2 仃一3 條 邊當且僅當g 是一棵2 樹 證明 根據上文的討論 我們只需要證明必要性 假設g 是一個佗個頂點2 釓一3 條邊 的局部連通圖 則g 的最小度至多為3 我們分兩種情況來證明 情形1 6 g 2 我們對n 用歸納法來處理這種情形 當凡 2 時顯然 一般地 我們收縮與那個2 度點 關聯的一條邊 再用歸納假設 也同樣易于說明 情形2 6 g 3 設讓是一個3 度點 并且有 釷 z z 則一定有 不妨說 z z 疊e g 否則g u z 將含有至多2 m 一1 一4 條邊 因次我們假設z 名隹e g 因為6 g 3 并且z 的鄰域的導 出子圖是連通的 因此一定存在一個點叫與z 和可相鄰接 這樣 d y 4 因為z 名聾e g 2 點的度在收縮前后不改變 從而 當我們收縮u z 后 g t z 中仍然沒有2 度點產生 因為 g 讓z 含有2 一1 一3 邊 其最小度是3 收縮與g u z 的一個3 度點關聯的邊 相同的論 證 再收縮與所得圖的一個3 度點相關聯的邊 繼續這個過程 一直到所得圖只有4 個點為 止 根據我們的論證 這個圖應該具有最小度3 同時含有5 條邊 但是這不可能 因此 6 g 2 并且每收縮一條與2 度點關聯的邊之后在新圖中都會有2 度點產生 因 此 對g 的頂點數進行歸納 容易看到 g 是2 樹 口 定理1 6 設g 是一個局曹黟連通圖 如果g 含有甄細分 則g 含有兩個邊不交序爭支撐樹 證明 我們對g 的頂點數n 用數學歸納法 當n 4 g 本身就是甄 結論顯然成立 一般地 根據定理8 設z 是g 的心細分k 之外的一個點 如果這樣的點不存在 則取z 是k 上的一個2 度點 收縮與z 關聯的一條邊 所得圖仍然含有一個托細分 根據歸納假 設 所得圖含有兩個邊不交的支撐樹 再由引理1 3 我們知道g 含有兩個邊不交的支撐樹 口 在 l 0 v 0 7 p 6 5 中說一個n 階的含有2 n 一2 條邊的簡單圖含有心細分 結合定理 1 6 我們有如下的定理 2 華東師范大學局部連通圖中的同胚不可約支撐樹 定理1 7 假設g 是一個竹階序明糊圖 則下面的條件相互等價 1 g 含有兩個邊不交的支撐樹 例i e g l 2 住一2 j 3 g 含有k 4 細分 3 2 4 兩類局部連通圖 假設g 是一個n 階的局部連通圖 則g 可以被分為兩類 一類恰好含有2 n 一3 條邊 顯然不含有兩個邊不交的支撐樹 另一類邊數至少為2 禮一2 含有兩個邊不交的支撐樹 當g 含有2 禮一3 條邊時 根據定理1 5 我們知道g 是一棵2 樹 根據2 樹的定義 從 尬開始 每次增加一個點 兩條邊 很容易構造出g 的一棵支撐樹和一棵具有禮一1 個頂點 的樹 利用x u o n g 的定理 x u 0 7 9 我們實際上已經得到了n e b e s 塒定理 也即是說 任何一 個局部連通圖都是上可嵌入的 3 2 5 局部連通圖與七一流 定義5 我們說一個定f 句圖g 具有處處非零的七一流 如果存在映射 e g oz 七滿足如 下條件 j 以 對任意 y g 釓u 叫 j u t t u 一 口 例 對任意e e g e 0 關于局部連通圖 我們還有下面的結論 定理1 8 假設g 是一個局部連通圖 則g 有處處非零的彳 流 證明 不妨設g 恰具有n 個頂點 因為當g 的邊數至少是2 n 一2 時g 有兩個邊不交 的支撐樹 g 可以被寫成兩個偶圖的并 根據 w 西9 6 p 3 1 0 我們知道一個圖有處處非 零的4 流當且僅當g 可以寫成兩個偶圖的并 此時g 有處處非零的冬流 因此 我們只需 考慮g 恰有2 n 一3 條邊的情形 我們對釓使用數學歸納法 當n 3 時 g 恐 給g 定向使得g 成一個有向的3 圈 讓每條邊的權值為1 我們得到一個g 的處處非零的垂流 一般地 設z 為g 的一個2 度 點 并且有 z z 易見g z 也還是2 樹 根據歸納假設 g z 有處處非零的 垂流 不妨設班的定向是從y 到z 我們讓名z 的方向是從z 到z 讓z 可的方向是從z 到可 將妒的權值增加1 將z z 和z 擴的權值設定為1 我們得到了g 的一個處處非零的奎流 口 1 3 華東師范大學局部連通圖中的同胚不可約支撐樹 第四章局部連通圖中的同胚不可約支撐樹 4 1同胚不可約支撐樹 如果一個圖的支撐樹不含有2 度點 則這棵樹被稱為是同胚不可約支撐樹 h o m e o m o r p k c a l l y i r r e d u c i b l e 印a n n i n gt r e e 簡記為h i s t 將一個圖是否含有h i s t 的問題限制在平面圖 上來考慮 a h i l l 阻i 1 7 4 l 猜想說除尥外的任何一個平面三角剖分都含有一h i s t j m 舭v i t c h m a l 7 糾將此猜想推廣到平面近三角剖分 除至多一個面外的所有面都是三 角形的平面圖 的情形 a l b e r t s o n b e r m a n h u t c h i 璐o n 和t h o m a 船e n a b h t 9 0 證明了 推廣后的猜想 并且猜測任何一個曲面三角剖分也含有一h i s t d 撕d o w h u t c h i 璐o n 和 h u n e k e d h h 9 5 證明每一個環面上的三角剖分圖都含有h i s t 本節我們將證明任何一個 頂點數至少是4 的局部連通圖都含有h i s t 結合引理6 便得到任何一個曲面三角剖分也 含有一h i s t 的論斷 4 2 1 弱2 樹的引入 4 2 弱2 一樹 容易觀察到 每一個頂點數至少為4 的2 一樹含有h i s t 因此如果可以證明一個圖含有 2 樹作為支撐子圖 則這個圖含有h i s t 但是 并不是所有的局部連通圖都含有2 樹作為支 撐子圖 下圖就是一個不含有2 樹作為支撐子圖的局部連通圖的例子 不含2 一樹作為支撐樹的圖 因此 我們將定義一類新圖 使得其含有h i s t 并且使得任何一個局部連通圖都含有這 類圖中的一個作為支撐子圖 4 2 2 弱2 樹的概念 設日是一個圖 仳l u 2 日是兩個不同的頂點 并且移g 日是一個新頂點 我們讓g 是通過給日添加頂點u 和邊仳1 u 2 u 以及邊讓1 t 2 如果t 1 1 牡2 譬e 日 而得到的圖 如果 1 4 華東師范大學局部連通圖中的同胚不可約支撐樹 邊u l u 2 e 日 我們稱g 是h 的與t 1 1 札2 相關的 型擴張 并且表示為風 坳 t 如果 u l u 2 簪e 日 我們稱g 是日的與讓1 t 2 相關的 型擴張 并且表示為風 啦 我們用 h u 來表示日的任意一個通過項點u 而得到的 型擴張 用日 u 來表示日的任意一 個通過頂點u 而得到的 一型擴張 定義6 一個階為n n 3 的圖丁被稱為弱參樹 如果丁的頂點有一個排序 u 1 啦 一 u n 滿足如下條件 以 丁 u 1 忱 地 箋蠔 對任意i 3 4 n 一1 俐t u 1 忱 仇 1 竺t u l 嚨 讓 ou t l 其中0 八或者 我們將這個排寄 稱為t 的一個弱2 樹序 4 2 3 關于弱2 樹的一些結論 引理1 9 設g 是一個至少含有彳個頂點的弱易樹 并且假設彬 g 是一個2 度點 t 是 的礴個鄰署 那么或者g 一哪或者g 一 一伽是一個弱2 樹 在這種情況下 我們用 ge 塒表示相應的階數少一的弱2 一樹 證明 因為d 2 因此對于任意一個弱2 樹序 訓都可以被放在序列的最后一位 而不影響其他頂點的排序 因此我們假定存在g 的一個頂點序 使得加在這個序列中的 最后一位 那么根據定義6 引理結論顯然 口 弓 理2 q 設t 是一個至少含有4 個頂點的弱2 樹 且 是相應的頂點穿 那么t 至少滿足 下面性質之一 p f 存在u u y t 使得d u d 2 并且 u n r u d j p 2 存在u u y 丁 使得d 扣 2 亂 u 并且出e t t 2 頂點對t u y t 被稱為丁的可移除頂點對 證明 我們對佗 j y 丁 j 用數學歸納法 當n 4 時 t 同構于酊 甄中移去一條 邊 讓g 中的兩個2 度點為缸 u 我們知道此時g 具有性質p 1 當n 5 時 讓名為 中 的最后一個頂點 讓 和 為gez 中的兩個2 度點 如果 名 n z 妙 d 取z z 中 任意兩個為仳 u 得知相應的圖滿足性質p 1 如果 名 n z 0 比方說耖 z 讓 札 可 u z 得知相應的圖滿足性質p 2 1 5 華東師范大學 局部連通圖中的同胚不可約支撐樹 假定禮 6 假設頂點數小于佗的弱2 一樹滿足引理2 0 令t t 7 是頂點序 中的最后一個 頂點 并且讓r te 協 很顯然 r 是一個弱2 樹 相應的頂點序是 那么 伽 將是t 的可移除點對滿足p 2 如果 伽 n t l 口 蘭 u 并且t 滿足p l 那么 u 伽 將是丁的可移除點對滿足 p 2 如果 n 并且心和口滿足p 2 那么 移 伽 將是丁的可移除點對滿足 p 1 如果 牡 t 那么 u 叫 將是丁的可移除點對滿足p 2 口 引理2 1 至少含有彳個頂點的弱參樹含有刪z 證明 假設t 是一個至少含有4 個頂點的弱2 樹 我們將通過對丁的頂點數扎使用歸 納法來進行證明 當n 4 那么t 蛭 丁含有h i s t 如果n 5 通過分情況討論 也易 于說明t 含有h i s t 現在假設n 6 根據引理2 0 令 t l y t 是t 的可移除頂點對 那么 根據 可移除頂點對的定義和定義6 我們知道丁e u u 是一個弱2 一樹 然后 根據歸納假設 t e t u 含有h i s t 比如說r 如果t 滿足p 1 那么u 和u 在t 中有一個公共鄰點 如 果t 滿足p 2 比如說d u 2 那么 中的另外一個點將是u 和秒的公共鄰點 因此 不管哪種情形 總存在一個點塒 t n 因此 t t u 叫t 加u 是丁的一個 h i s t 口 4 3 局部連通圖中的h i s t 引理2 2 每一個局部連通圖都含有一個弱參樹作為支撐子圖 證明 設g 是一個含有頂點數n 3 的局部連通圖 因為3 圈是弱2 樹 因 此g 含有弱2 樹作為子圖 令t g 是一個弱2 一樹使得i y t i 最大 我們將證明 1 6 華東師范大學 局部連通圖中的同胚不可約支撐樹 y 丁 y g 否則 y g 一y 丁 d 因為g 是連通的 存在頂點耖 y 丁 使得 晰 t 0 其中蜥 u 是u 在 中的鄰居 假設名是 中的一個點 因為t 是弱 2 樹 u ny 丁 2 坼 u 0 義因為g u 是連通的 假設p 是一條 u 名 路 其中 u ny 丁 現在 讓加是尸上的第一個不在y t 中的點 則 u u 加 導出一個三 角形 那么 丁 u ot t j 是一含有比丁有更多頂點的弱2 樹 因為u 叫u t 彬 e g 并且 丁 g 我們有丁 扎 o 訓 g 但是這與 l y 丁 i 最大相矛盾 口 定理2 3 每一個頂點數至少為4 的局部連通圖都含有m s t 證明 根據引理2 1 和引理2 2 定理結論顯然 1 7 口 a c p 8 7 1 a p 8 6 a p 8 9 a p c 刪 c l a 8 1 c p 7 4 d h h 9 5 1 d i r 6 1 h i l 7 4 參考文獻 m i c h lo a l b e r t s o n d a v i dm b e r m 觚 j o 觚p h u t c l l i 瑚o n a i l d a 瑙t e nt h o m a 鹋e n g r a p l l 8w i t hh o m e o 珊d r p l l i c l yi r r e d u c i b l es p 觚礎唱t 嗍 zg 唧 弛 刪 1 4 2 2 4 7 2 5 8 1 9 9 0 s t e f a na r i l b o r g d e r e kg c o m e i l 8 n da n d r z e jp r o s k u r o w g k i c o m p l e 妞t yo ff i n d i n g e i n b e d d i n g bi na 如t r 跏mza 幻e 6 m i cd 婦c 他t em e 紙d 幽 8 2 2 7 7 2 8 4 1 9 8 7 s t e f a na r n b o r ga n da n d r z e jp r o s k l l r o w s k i c h a r a u c t e r i z a t i o na n d 刪t i o no fp a r t i 址 3 t r 嘲 翻m m 正a 幻e 6 m t cd 婦c 他 e 脅紈d 幽 7 2