（運籌學(xué)與控制論專業(yè)論文）局部連通圖中的同胚不可約支撐樹.pdf

一 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 華東師范大學(xué)學(xué)位論文原創(chuàng)性聲明 葉 鴿 幫重聲明 本人所呈交的學(xué)位論文 廚泖巫疊閣憫同刪粵鱔僻東師范大學(xué)攻 讀硒生 博士 請勾選 學(xué)位期間 在導(dǎo)師的指導(dǎo)下進行的研究工作及取得的研究成果 除 文中已經(jīng)注明引用的內(nèi)容外 本論文不包含其他個人已經(jīng)發(fā)表或撰寫過的研究成果 對本文 的研究做出重要貢獻的個人和集體 均已在文中作了明確說明并表示謝意 作者簽名 監(jiān)絲日期 孫1 年5 月們?nèi)?華東師范大學(xué)學(xué)位論文著作權(quán)使用聲明 范大學(xué)根據(jù)相關(guān)規(guī)定保留和使用此學(xué)位論文 并向主管部門和相關(guān)機構(gòu)如國家圖書館 中 信所和 知網(wǎng) 送交學(xué)位論文的印刷版和電子版 允許學(xué)位論文進入華東師范大學(xué)圖書館 及數(shù)據(jù)庫被查閱 借閱 同意學(xué)校將學(xué)位論文加入全國博士 碩士學(xué)位論文共建單位數(shù)據(jù) 庫進行檢索 將學(xué)位論文的標題摘要匯編出版 采用影印 縮印或其他方式合理復(fù)制學(xué)位論 文 本學(xué)位論文屬于 請勾選 1 經(jīng)過華東師范大學(xué)相關(guān)部門審查核定的 內(nèi)部 或 涉密 學(xué)位論文 于年 月日解密 解密后適用上述授權(quán) u2 不保密 適用上述授權(quán) 學(xué)位論文作者簽名 夠繹放妊導(dǎo)師簽名 嗍幽盤豳墮吼絲 汐f f 涉密 學(xué)位論文應(yīng)是已經(jīng)華東師范大學(xué)學(xué)位評定委員會辦公室或保密委員會審定過的學(xué)位論文 需附獲批的 華 東師范大學(xué)研究生申請學(xué)位論文 涉密 審批表 方為有效 未經(jīng)上述部門審定的學(xué)位論文均為公開學(xué)位論文 此聲明 欄不填寫的 默認為公開學(xué)位論文 均適用上述授權(quán) 鐔松齡碩士學(xué)位論文答辯委員會成員名單 姓名職稱單位備注 呂長虹教授華東師范大學(xué)主席 杜若霞副教授華東師范大學(xué) 郭軍偉副教授華東師范大學(xué) 摘要 如果一個連通圖的支撐樹不含有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 本文證明任何一個頂點數(shù)至少是4 的局部連通圖都含有 h i s t 作為一個推論 便得到任何一個曲面三角剖分也含有一h i s t 的論斷 關(guān)鍵詞 局部連通圖 邊收縮 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 鶴 中文摘要 英文摘要 目錄 第一章 引言及預(yù)備知識 1 1 1 引言 1 1 2 網(wǎng)的基本概念 2 1 3 樹 5 1 3 三角剖分圖 5 第二章 局部連通圖簡介 6 2 1 局部連通圖的定義 6 2 2 局部連通圖的一些性質(zhì) 7 2 3 關(guān)于局部連通圖的兩個猜想 8 2 4 缸樹和弦圖 8 第三章邊不交的支撐樹 1 0 3 1 定義及應(yīng)用 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 華東師范大學(xué) 局部連通圖中的同胚不可約支撐樹 第一章引言及預(yù)備知識 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 總可 以構(gòu)造出一個圖 使其最小度6 如 但是不含有h i s t 比如 在 a b h t 9 0 中 取r 個j 0 拷貝 對每 個坼拷貝中的r 個點 每一個都與一個一度點連接 然后 添加另外的r 個獨 立點 每一個都與已構(gòu)造圖中的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 應(yīng)用相同的技巧 可以證明 對每一個正整數(shù)d l 和 任給的常數(shù)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 網(wǎng)難的 這個問題已經(jīng)被人解決 答案是肯定的 但是截止目前 結(jié)論尚未公開 發(fā)表 將一個圖是否含有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 證明每一個環(huán)面上的三角剖 分圖都含有h i s t 本文證明任何一個頂點數(shù)至少是4 的局部連通圖都含有h i s t 作為一 個推論 便得到任何一個曲面三角剖分也含有一h i s t 的論斷 華東師范大學(xué)局部連通圖中的同胚不可約支撐樹 1 2 1 圖的定義 1 2 圖的基本概念 一個圖g 實際上就是一有序?qū)?v g e g 這個有序?qū)腥齻€因素 其一 頂點集 y g 其二 與頂點集不交的邊集e g 其三 關(guān)聯(lián)函數(shù)妒g 它將g 的每一條邊與g 的頂 點集的二元無序?qū)?有可能無序?qū)χ械膬蓚€元素相同 相對應(yīng) 如果e 是g 的 條邊 u 是g 的兩個頂點 并且有惦 e u 我們則說 e 和 t 分別關(guān)聯(lián) 同時 u t 也和e 關(guān) 聯(lián) u 與 相互鄰接 這時 t l 移被稱為e 的端點 設(shè) 也是g 的一條邊 如果讓也與 關(guān)聯(lián) 我們則說e 和 鄰接 圖g 所含頂點的個數(shù) 也就是y g 所含元素的個數(shù) 通常用l y g i 來表示 圖g 所含邊的條數(shù) 也就是e g 所含元素的個數(shù) 通常用i e g i 來表示 在如上所定義的圖中 如果我們要求g 的每一條邊與g 的頂點集的不同頂點構(gòu)成的二 元無序?qū)ο鄬?yīng) 則相應(yīng)的圖稱為簡單圖 在后文中 如無特別指出 所有的圖都是簡單圖 假設(shè)g 是一個簡單圖 并且假設(shè) 是g 的一個頂點 我們將g 中所有與u 相鄰接的頂 點集合稱為u 的鄰域 記為 g u 如果不會引起混淆 則簡記為 u 的閉鄰域 記為 m u u 與頂點u 相鄰接的點的個數(shù) 也即是與點u 相關(guān)聯(lián)的邊的條數(shù) 也即是 所含元素的個數(shù) 被稱為 的度數(shù) 記為站 u 或者d u 圖g 中所有頂點的度數(shù)中 最小的被稱為g 的最小度 記為j g 相應(yīng)地 最大度記為 g 假設(shè)g 是一個簡單圖 并且假設(shè)咖e l u l e 2 u 2 e 3 u 3 饑一l e t 毗是g 中一個點邊序列 則這 個序列稱為g 的一條長為t 的鏈 咖和u t 稱為鏈的始點和端點 如果這個鏈的所有點和邊 都互不相同 則相應(yīng)的鏈稱為g 的一條路 路上的除端點之外的點稱為是路的內(nèi)點 我們 用r 來表示含有n 個點的路 或者長為禮一1 的路 一般地 設(shè)p 是一條路 z 可是路上的兩個點 則z p 表示以z 秒為端點 以p 上位于 z 可之間的點為內(nèi)點的一條路 如果一條路的始點和端點相同 則這條路是一個圈 我們用g 來表示長為釓的圈 設(shè)g 是一個含有n 個頂點的簡單圖 如果g 的任何兩個點之間都有一條邊 則g 是一 個完全圖 記為 1 2 2 子圖 設(shè)g 是一個圖 頂點集是y g 邊集是e g 我們說圖h 是圖g 的一個子圖 如果 y 日 y g 并且e 日 e g 2 華東師范大學(xué) 局部連通圖中的同胚不可約支撐樹 給定g 的子圖h 如果我們有y 日 y g 我們則說日是g 的支撐子圖 設(shè)g 是一個恰好含有禮個頂點的圖 如果g 含有一個支撐圈 或者說長為n 的圈作為 子圖 我們則說這個圈是g 的哈密爾頓圈 此時 也說g 是哈密爾頓的 1 2 3 導(dǎo)出子圖 設(shè)g 是一個圖 頂點集是y g 邊集是e g 假設(shè)s y g 現(xiàn)在定義g 的一個子 圖日如下 iy h s le 日 u u i u s 并且u u e g 此時 我們稱日是g 的點導(dǎo)出子圖 或者是由s 導(dǎo)出的子圖 記為g 翻 如果g 鄙是一個 完全圖 我們則說s 是一個團 1 2 4 圖同構(gòu) 設(shè)g 和日是兩個圖 如果有y g y 日 e g e 日 并且妒g 妒日 則說g 與 日相等 記為g 日 通常而言 我們說兩個圖g 和日同構(gòu) 記為g 望日 如果存在雙射口 y g 一 y 日 和 e g e 日 滿足惦 e t i u 當(dāng)且僅當(dāng)妒日 e 口 u p u 此時 這一對雙射 口 咖被稱為g 和h 間的同構(gòu)映射 1 2 5 圖的幾個運算 給定圖g 設(shè)s 是y g 的一個子集 那么g s 則表示g 的一個子圖 通過刪除s 中的頂點和所有與s 中的頂點關(guān)聯(lián)的邊而得到 特別地 如果s z 則g s 簡記為 g z 給定圖g 設(shè)t 是e g 的一個子集 那么g t 則表示g 的一個子圖 與g 具有相同 的頂點集 而邊集則通過從e g 中刪除丁中的邊而得到 特別地 如果t e 則g t 簡記為g e 給定圖g 及g 的一條邊e z 我們等同頂點z 和可 將這個新點記為叫 然后構(gòu)造一 個新圖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 華東師范大學(xué)局部連通圖中的同胚不可約支撐樹 值得注意的是 即使在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 圖的連通性 假設(shè)g 是一個非平凡圖 也即是說g 含有至少兩個頂點 我們說g 是連通的 如果g 的任何兩個頂點之間都有一條路相連接 設(shè)p 和q 是g 的兩條路 我們說p 和q 內(nèi)部不交 如果p 和q 具有不同的內(nèi)點 如果g 的任何兩個頂點間都有至少兩條內(nèi)部不交的路 則g 被稱為是2 連通的 相應(yīng) 地 任意給定正整數(shù)后 可以定義 連通 設(shè)g 是一個圖 任給g 的兩個頂點 根據(jù)這兩個點之間是否有路連接可以將g 的頂點 分類 也就是說 如果z 之間有路連接 則將z y 放在同一個類中 每一個頂點類的導(dǎo)出 子圖稱為g 的一個連通分支 設(shè)g 是一個圖 o 是g 的一個頂點 e 是g 的一條邊 如果g z 的連通分支的個數(shù)比 g 的多 則稱z 為g 的一個割點 相應(yīng)地 如果g e 的連通分支的個數(shù)比g 的多 則稱e 為g 的一條割邊 定理1 設(shè)g 是一個圖 e 是g 的一條邊 如果e 在一個圈上 則e 不是g 的割邊 證明 反設(shè)e z 是g 的 條割邊 則在g e 中有兩個連通分支g 1 g 2 使得在g 中g(shù) 1 g 2 在同一個分支里并且g 1 中的任何一個點與g 2 中的任何一個點之間的路都經(jīng)過 e 特別地 和鈔之間的所有路都必須經(jīng)過e 因此 e 不在任何圈上 這是一個矛盾 從而 e 不是g 的割邊 口 4 華東師范大學(xué)局部連通圖中的同胚不可約支撐樹 1 3 樹 一個無圈的連通圖 被稱為樹 關(guān)于樹 我們有如下的定理 定理2 設(shè)t 是一棵樹并且t 恰好含有禮個頂點 則丁的邊數(shù)為n 一1 為了證明定理2 我們需要下面的引理 引理3 設(shè)g 是一個圖 如果6 g 2 則g 含有圍 證明 取g 中的一條最長路p 并且假設(shè)z 是尸的一個端點 因為j g 2 z 肯定會 和一個不同于它在j p 上的鄰點的頂點鄰接 設(shè)那個點為y 但是 p 是g 中的最長路 所以 可一定在尸上 這樣 z yuz 尸y 形成了一個圈 口 現(xiàn)在我們來證明定理2 證明 我們對丁的頂點數(shù)作歸納 當(dāng)頂點數(shù)是2 時 結(jié)論顯然成立 根據(jù)引理3 丁含 有一度點 比方說z 是丁的一個一度點 則 丁一z 仍然是一棵樹 根據(jù)歸納假設(shè) 丁一z 含有 n 一2 條邊 因此 t 含有n 一1 條邊 因為在刪除z 的同時 我們恰巧刪除了一條t 的邊 口 推論4 設(shè)g 是一個恰含有禮個頂點的連通圖 如果g 所含的邊數(shù)最小 則g 是一棵樹 證明 g 不可能含有圈 否則刪掉某個圈上的一條邊所得圖依然連通 但是具有更小 的邊數(shù) 因此g 是樹 口 定理5 設(shè)g 是一個連通圖 則g 含有一支撐樹 證明 我們對g 的邊數(shù)進行歸納 設(shè)g 具有禮個頂點 則根據(jù)推論4g 所含的邊數(shù)最 小為n 一1 如果g 不含有圈 則g 本身就是一棵樹 現(xiàn)在 假設(shè)c 是g 的一個圈 刪除c 上的一條邊 所得圖還是連通的 根據(jù)歸納假設(shè) 所得圖含有一支撐樹 那也是原圖的支撐 樹 口 1 4 1 嵌入 1 4 三角剖分圖 一個連通的2 維流形被稱為是一個曲面 給定一個曲面 和一個圖g 如果g 可以被 畫在r 上 使得g 的邊只在其端點處與別的邊相交 則說g 可以嵌入在i 上 5 華東師范大學(xué) 局部連通圖中的同胚不可約支撐樹 特別地 如果g 在平面上有一個嵌入 則稱g 是一個平面圖 設(shè)g 是一個嵌入在曲面r 上的圖 則 一g 的各個弧連通的區(qū)域被稱為嵌入圖g 的 面 其中 一g 表示從點集r 中除去在g 的邊上的那些點 1 4 2 三角剖分圖 設(shè)g 是一個嵌入在曲面r 上的圖 如果g 的各個面都是三角形 則稱g 三角剖分曲面 r 或者g 是一個曲面三角剖分圖 特別地 如果r 是一個平面 我們說g 是一個平面二角 剖分 關(guān)于三角剖分圖 我們有如下引理 引理6 r 軌廁每一個頂點數(shù)至少為彳的三角剖分圖部是局部哈密爾頓連通的俗個點的 鄰域的導(dǎo)出子圖是哈密爾頓的1 第二章局部連通圖簡介 本節(jié)所討論的圖 如無特別指出 都是連通圖 2 1 1 局部連通圖的基本概念 2 1 局部連通圖的定義 定義1 設(shè)g 是一個圖 如果g 的每一個頂點的鄰域的導(dǎo)出子圖都是連通的 則稱g 局部 連通的 根據(jù)局部連通圖的定義 局部連通圖具有如下性質(zhì) 食題1 設(shè)g 是一個至少含有3 個頂點的局部連通圖 則g 的每一條邊都在一個三角形中 證明 設(shè)e z 可是g 中任給的一條邊 因為g 含有至少三個頂點 并且g 是局部連 通的 則z 一定會和可的鄰域中的另一個點 不妨設(shè)名鄰接 因此 z 鱸形成一個三角形 口 2 1 2 關(guān)于局部連通圖的一些結(jié)論 局部連通圖的概念最早是在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 羽中提出來的 他們證明了如下結(jié)論 6 華東師范大學(xué) 局部連通圖中的同胚不可約支撐樹 1 如果g 是局部七一連通的 則g 本身是七 1 連通的 2 每一個局部3 連通圖都是非平面圖 3 如果g 是局部連通的 含有至少3 個頂點 最大度至多是4 則g 或者是哈密爾頓的或 者 一構(gòu)于k l 1 3 2 2 1 局部連通圖的一些性質(zhì) 2 2 局部連通圖的一些性質(zhì) 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 的邊數(shù)和頂點數(shù) 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 設(shè)g 是一個局部連通圖 e 是g 的一條邊 我們說e 是g 的一條可收縮邊 如果 g e 仍然是局部連通的 定理8 設(shè)g 是一個頂點數(shù)至少為2 的局部連通圖 則對于g 的任一個頂點u g 有一條 可收縮l 邊e u u 證明 取u 使得t 不是g 讓 的割點 接下來 我們將會證明t u 是g 的一 條可收縮邊 記日 g 幾u 很顯然 日是連通的 因此只需要證明日局部連通即可 設(shè)伽為日中 的通過收縮讓t 而得到的新頂點 對任意z y h 我們分如下兩種情況來證明 情形l z 刪 如果叫譬 日 z 日 z g z 因為g 小 g 0 是連通的 因此我們知道馴 日 z 是 7 華東師范大學(xué)局部連通圖中的同胚不可約支撐樹 連通的 因此我們假定硼 眥 z 如果i g z n u u i 1 那么我們有g(shù) g z 是 日 z 的支撐子圖 如果 g z 我們同樣有g(shù) g 是日 蜥 z 的支撐子 圖 無論哪種情況 我們都有何 z 是連通的 因為g f b 是連通的 情形2 z 塒 在這種情況下 蜥 砌 t t 一u u g u 一u 假設(shè)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 的頂點數(shù)至少為3 則g 的每個頂點至少與兩 條可收縮邊相關(guān)聯(lián) 2 3 1 猜想一 2 3關(guān)于局部連通圖的兩個猜想 設(shè)g 是一個連通且局部n 一連通的圖 如果g 不含導(dǎo)出的k 1 七 2 則g 是哈密爾頓的 的 參見 o s 7 9 以上猜想對七 1 的情形已經(jīng)在 o s 7 9 中證明了 2 3 2 猜想二 一個圖稱為是弱泛圈的 如果這個圖含有從其圍長 最短圈的長度 至周長 最長圈的 長度 之間的每一個長度的圈 對于局部連通圖 我們有如下猜想 連通且局部連通圖是弱泛圈的 2 4 七一樹和弦圖 在第一節(jié)中 引理6 說三角剖分圖都是局部連通圖 接下來 我們將證明七一樹和2 連 通的弦圖是局部連通的 8 華東師范大學(xué)局部連通圖中的同胚不可約支撐樹 2 4 1 關(guān)于七 樹的一些性質(zhì) 定義3 任給一個正整數(shù)七 圖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 圖 關(guān)于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 七 樹是局部連通的 證明 設(shè)g 是一缸樹 我們對g 的頂點數(shù)進行歸納 最小的七 樹是一個頂點數(shù)為 七的完全圖 顯然是局部連通的 一般地 假設(shè)u 1 晚 在g 中除 中的點 外 其他頂點的鄰域與在g 一 中相同 因此我們只需要考慮 f 各個點的局部連 通性 根據(jù)七 樹的定義 g 是一個完全圖 因此是連通的 對于珧 1 t 七 g 鼽 g g 璣 u y 1 沈 璣一l 鼽 1 鯫 是連通的 口 2 4 2 弦圖 設(shè)g 是一個圖 c 是g 的一個圈 e 是g 的一條邊 如過e 的兩個端點在c 上但是e 不 是c 的一條邊 則稱e 是g 的一條弦 一個圖g 稱為是弦圖 如果g 的每一個長度大于3 的圈都含有弦 定義4 設(shè)g 是一個圖 鈔是g 的一個頂點 那么u 被稱為是s i m p 托c i o j 的當(dāng)且僅當(dāng)g u 是一個完全圖 關(guān)于弦圖 我們有如下的著名論斷 引理1 0 眈r 鋤弦圖有一個鰣唧屁c i 口2 的頂點 2 4 3 關(guān)于弦圖的一些結(jié)論 引理1 1 設(shè)g 是一個參連通的弦圖 含有至少彳個頂點口是一個3 唧屁c i 口f 的頂點 那么 g t 是2 連通的 9 華東師范大學(xué)局部連通圖中的同胚不可約支撐樹 證明 當(dāng)u 的度至少為3 時 易于說明 因此假設(shè) 佃 可1 反設(shè)g u 不是2 連 通的 則z 之一為g 一 的割點 不失一般性 設(shè)z 是這樣一個割點 并且假定g l 和g 2 是g 一 一z 的兩個分支 因為g 含有至少4 個頂點 g l 和g 2 分別含有至少一個頂點 因 為在g 中g(shù) 1 和g 2 之間至少有兩條內(nèi)部不交的路 因此秒有鄰點在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 設(shè)g 是一個廖連通的弦圖 則g 是局糊的 證明 我們對g 的頂點數(shù)n 進行歸納 當(dāng)n 3 時g 媧 顯然是局部連通的 一般 地 根據(jù)引理1 0 設(shè) 是g 的一個s i m p l i c i a l 頂點 根據(jù)引理1 1 g u 是2 一連通的 岡為 g 一 是2 連通的弦圖 根據(jù)歸納假設(shè) g 一 是局部連通的 現(xiàn)在來討論g 的局部連通性 因為y g m 中的點的鄰域在g 中與在g u 中相同 兇此我們只需討論 m 中各個 點的鄰域的導(dǎo)出子圖是否連通 首先g f 1 是一個完全圖 是連通的 記g 7 g u 對 于z 移 g z g g u u u y b u z 是連通的 口 第三章邊不交的支撐樹 3 1 定義及應(yīng)用 設(shè)g 是一個圖 如果丑和死 是g 的兩棵支撐樹 并且噩和乃沒有公共邊 那么我們 稱互和疋是g 的邊不交的支撐樹 圖的邊不交的支撐樹在網(wǎng)絡(luò)理論中有很多應(yīng)用 關(guān)于這方面的研究可以參考 l h m r 9 8 s s p 9 6 同時 圖的邊不交的支撐樹在組合理論中也有很多應(yīng)用 例如 根據(jù) x u 0 7 9 一個 圖是上可嵌入的如果g 有一支撐樹t 使得g e t 至多只有一個奇分支 一個含有奇數(shù) 條邊的連通分支 因此 如果能夠證明g 含有兩個邊不交的支撐樹 則g 是上可嵌入的 如果g 含有兩個邊不交的支撐樹 則g 可以寫成兩個偶圖 所有頂點的度都是偶數(shù) 的圖 的并 同時 我們知道一個圖有處處非零的垂流當(dāng)且僅當(dāng)g 可以寫成兩個偶圖的并 i w 巍9 6 p 3 1 0 因此 如果g 含有兩個邊不交的支撐樹 則g 有處處非零的4 流 1 0 華東師范大學(xué)局部連通圖中的同胚不可約支撐樹 3 2局部連通圖中的邊不交支撐樹 3 2 1 邊不交支撐樹在局部連通圖中的擴張性 引理1 3 設(shè)g 是一個局考隧通圖 e 是g 的一條可收縮邊 如果g e 含有兩個邊不交的支 撐樹 則g 也含有兩個邊不交的支撐樹 證明 設(shè)e z 并且假設(shè)伽是通過收縮e 所得的g g e 中的新點 因為g z 足連通的 我們不妨設(shè)可與z 的另一個鄰點z 相鄰接 讓n 和乃是g e 的兩個邊不交的 支撐樹 我們將對n 和死進行修正 使其成為g 的邊不交的支撐樹 將伽在乃和死中都用 替換 同時刪除丑和死中的本不是g 的那些邊 這些邊對應(yīng) 于g 中一條與z 相關(guān)聯(lián)的邊 將所得圖記為躉和巧 不失一般性 設(shè)凡 最 昂為躉 的分支 吼 風(fēng)為z 的分支 進一步 假設(shè)y 所在的分支分別為只和凰 將相應(yīng) 的最 b 昂和地 風(fēng) 風(fēng)中的與刪在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 不失一般性 設(shè)在肌中2 與 不在同一個分支中 此時礙u z 耖 e 2 e 3 e p 和zu 轤 厶 厶 為g 的兩個邊不交的支撐樹 口 3 2 2 局部連通圖所含的邊數(shù) 引理1 4 設(shè)g 是一個恰有n 個頂點的局部連通圖 則g 至少含有2 n 一3 條 邊 證明 我們對n i y g l 進行歸納 當(dāng)n 1 2 時 結(jié)論顯然成立 根據(jù)定理8 我們收 縮邊 比如說z y 并將所得圖記為g 根據(jù)歸納假設(shè) g 含有至少2 n 一1 一3 條邊 并且這 2 n 1 一3 條邊在g 中都有相應(yīng)的邊與之相對應(yīng) 同時 根據(jù)命題7 在g 中 z 可在一個三 角形中 當(dāng)收縮z g 7 比g 至少減少了兩條邊 因此g 含有至少2 佗一1 一3 2 2 n 3 條邊 口 華東師范大學(xué)局部連通圖中的同胚不可約支撐樹 3 2 3 局部連通圖中的邊不交支撐樹 根據(jù)定理9 我們知道2 樹是局部連通的 同時再根據(jù)引理1 4 我們知道2 樹是同階的 局部連通中邊數(shù)最小的一個 2 樹含有恰好2 佗一3 條邊 下面的定理將要說明 如果一個 局部連通圖g 只含有 一3 條邊 那么g 是一2 樹 定理1 5 設(shè)g 是一個恰含n 個頂點的局部連通圖 則g 具有恰好2 仃一3 條 邊當(dāng)且僅當(dāng)g 是一棵2 樹 證明 根據(jù)上文的討論 我們只需要證明必要性 假設(shè)g 是一個佗個頂點2 釓一3 條邊 的局部連通圖 則g 的最小度至多為3 我們分兩種情況來證明 情形1 6 g 2 我們對n 用歸納法來處理這種情形 當(dāng)凡 2 時顯然 一般地 我們收縮與那個2 度點 關(guān)聯(lián)的一條邊 再用歸納假設(shè) 也同樣易于說明 情形2 6 g 3 設(shè)讓是一個3 度點 并且有 釷 z z 則一定有 不妨說 z z 疊e g 否則g u z 將含有至多2 m 一1 一4 條邊 因次我們假設(shè)z 名隹e g 因為6 g 3 并且z 的鄰域的導(dǎo) 出子圖是連通的 因此一定存在一個點叫與z 和可相鄰接 這樣 d y 4 因為z 名聾e g 2 點的度在收縮前后不改變 從而 當(dāng)我們收縮u z 后 g t z 中仍然沒有2 度點產(chǎn)生 因為 g 讓z 含有2 一1 一3 邊 其最小度是3 收縮與g u z 的一個3 度點關(guān)聯(lián)的邊 相同的論 證 再收縮與所得圖的一個3 度點相關(guān)聯(lián)的邊 繼續(xù)這個過程 一直到所得圖只有4 個點為 止 根據(jù)我們的論證 這個圖應(yīng)該具有最小度3 同時含有5 條邊 但是這不可能 因此 6 g 2 并且每收縮一條與2 度點關(guān)聯(lián)的邊之后在新圖中都會有2 度點產(chǎn)生 因 此 對g 的頂點數(shù)進行歸納 容易看到 g 是2 樹 口 定理1 6 設(shè)g 是一個局曹黟連通圖 如果g 含有甄細分 則g 含有兩個邊不交序爭支撐樹 證明 我們對g 的頂點數(shù)n 用數(shù)學(xué)歸納法 當(dāng)n 4 g 本身就是甄 結(jié)論顯然成立 一般地 根據(jù)定理8 設(shè)z 是g 的心細分k 之外的一個點 如果這樣的點不存在 則取z 是k 上的一個2 度點 收縮與z 關(guān)聯(lián)的一條邊 所得圖仍然含有一個托細分 根據(jù)歸納假 設(shè) 所得圖含有兩個邊不交的支撐樹 再由引理1 3 我們知道g 含有兩個邊不交的支撐樹 口 在 l 0 v 0 7 p 6 5 中說一個n 階的含有2 n 一2 條邊的簡單圖含有心細分 結(jié)合定理 1 6 我們有如下的定理 2 華東師范大學(xué)局部連通圖中的同胚不可約支撐樹 定理1 7 假設(shè)g 是一個竹階序明糊圖 則下面的條件相互等價 1 g 含有兩個邊不交的支撐樹 例i e g l 2 住一2 j 3 g 含有k 4 細分 3 2 4 兩類局部連通圖 假設(shè)g 是一個n 階的局部連通圖 則g 可以被分為兩類 一類恰好含有2 n 一3 條邊 顯然不含有兩個邊不交的支撐樹 另一類邊數(shù)至少為2 禮一2 含有兩個邊不交的支撐樹 當(dāng)g 含有2 禮一3 條邊時 根據(jù)定理1 5 我們知道g 是一棵2 樹 根據(jù)2 樹的定義 從 尬開始 每次增加一個點 兩條邊 很容易構(gòu)造出g 的一棵支撐樹和一棵具有禮一1 個頂點 的樹 利用x u o n g 的定理 x u 0 7 9 我們實際上已經(jīng)得到了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 關(guān)于局部連通圖 我們還有下面的結(jié)論 定理1 8 假設(shè)g 是一個局部連通圖 則g 有處處非零的彳 流 證明 不妨設(shè)g 恰具有n 個頂點 因為當(dāng)g 的邊數(shù)至少是2 n 一2 時g 有兩個邊不交 的支撐樹 g 可以被寫成兩個偶圖的并 根據(jù) w 西9 6 p 3 1 0 我們知道一個圖有處處非 零的4 流當(dāng)且僅當(dāng)g 可以寫成兩個偶圖的并 此時g 有處處非零的冬流 因此 我們只需 考慮g 恰有2 n 一3 條邊的情形 我們對釓使用數(shù)學(xué)歸納法 當(dāng)n 3 時 g 恐 給g 定向使得g 成一個有向的3 圈 讓每條邊的權(quán)值為1 我們得到一個g 的處處非零的垂流 一般地 設(shè)z 為g 的一個2 度 點 并且有 z z 易見g z 也還是2 樹 根據(jù)歸納假設(shè) g z 有處處非零的 垂流 不妨設(shè)班的定向是從y 到z 我們讓名z 的方向是從z 到z 讓z 可的方向是從z 到可 將妒的權(quán)值增加1 將z z 和z 擴的權(quán)值設(shè)定為1 我們得到了g 的一個處處非零的奎流 口 1 3 華東師范大學(xué)局部連通圖中的同胚不可約支撐樹 第四章局部連通圖中的同胚不可約支撐樹 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 證明每一個環(huán)面上的三角剖分圖都含有h i s t 本節(jié)我們將證明任何一個 頂點數(shù)至少是4 的局部連通圖都含有h i s t 結(jié)合引理6 便得到任何一個曲面三角剖分也 含有一h i s t 的論斷 4 2 1 弱2 樹的引入 4 2 弱2 一樹 容易觀察到 每一個頂點數(shù)至少為4 的2 一樹含有h i s t 因此如果可以證明一個圖含有 2 樹作為支撐子圖 則這個圖含有h i s t 但是 并不是所有的局部連通圖都含有2 樹作為支 撐子圖 下圖就是一個不含有2 樹作為支撐子圖的局部連通圖的例子 不含2 一樹作為支撐樹的圖 因此 我們將定義一類新圖 使得其含有h i s t 并且使得任何一個局部連通圖都含有這 類圖中的一個作為支撐子圖 4 2 2 弱2 樹的概念 設(shè)日是一個圖 仳l u 2 日是兩個不同的頂點 并且移g 日是一個新頂點 我們讓g 是通過給日添加頂點u 和邊仳1 u 2 u 以及邊讓1 t 2 如果t 1 1 牡2 譬e 日 而得到的圖 如果 1 4 華東師范大學(xué)局部連通圖中的同胚不可約支撐樹 邊u l u 2 e 日 我們稱g 是h 的與t 1 1 札2 相關(guān)的 型擴張 并且表示為風(fēng) 坳 t 如果 u l u 2 簪e 日 我們稱g 是日的與讓1 t 2 相關(guān)的 型擴張 并且表示為風(fēng) 啦 我們用 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 關(guān)于弱2 樹的一些結(jié)論 引理1 9 設(shè)g 是一個至少含有彳個頂點的弱易樹 并且假設(shè)彬 g 是一個2 度點 t 是 的礴個鄰署 那么或者g 一哪或者g 一 一伽是一個弱2 樹 在這種情況下 我們用 ge 塒表示相應(yīng)的階數(shù)少一的弱2 一樹 證明 因為d 2 因此對于任意一個弱2 樹序 訓(xùn)都可以被放在序列的最后一位 而不影響其他頂點的排序 因此我們假定存在g 的一個頂點序 使得加在這個序列中的 最后一位 那么根據(jù)定義6 引理結(jié)論顯然 口 弓 理2 q 設(shè)t 是一個至少含有4 個頂點的弱2 樹 且 是相應(yīng)的頂點穿 那么t 至少滿足 下面性質(zhì)之一 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 用數(shù)學(xué)歸納法 當(dāng)n 4 時 t 同構(gòu)于酊 甄中移去一條 邊 讓g 中的兩個2 度點為缸 u 我們知道此時g 具有性質(zhì)p 1 當(dāng)n 5 時 讓名為 中 的最后一個頂點 讓 和 為gez 中的兩個2 度點 如果 名 n z 妙 d 取z z 中 任意兩個為仳 u 得知相應(yīng)的圖滿足性質(zhì)p 1 如果 名 n z 0 比方說耖 z 讓 札 可 u z 得知相應(yīng)的圖滿足性質(zhì)p 2 1 5 華東師范大學(xué) 局部連通圖中的同胚不可約支撐樹 假定禮 6 假設(shè)頂點數(shù)小于佗的弱2 一樹滿足引理2 0 令t t 7 是頂點序 中的最后一個 頂點 并且讓r te 協(xié) 很顯然 r 是一個弱2 樹 相應(yīng)的頂點序是 那么 伽 將是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 證明 假設(shè)t 是一個至少含有4 個頂點的弱2 樹 我們將通過對丁的頂點數(shù)扎使用歸 納法來進行證明 當(dāng)n 4 那么t 蛭 丁含有h i s t 如果n 5 通過分情況討論 也易 于說明t 含有h i s t 現(xiàn)在假設(shè)n 6 根據(jù)引理2 0 令 t l y t 是t 的可移除頂點對 那么 根據(jù) 可移除頂點對的定義和定義6 我們知道丁e u u 是一個弱2 一樹 然后 根據(jù)歸納假設(shè) 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 每一個局部連通圖都含有一個弱參樹作為支撐子圖 證明 設(shè)g 是一個含有頂點數(shù)n 3 的局部連通圖 因為3 圈是弱2 樹 因 此g 含有弱2 樹作為子圖 令t g 是一個弱2 一樹使得i y t i 最大 我們將證明 1 6 華東師范大學(xué) 局部連通圖中的同胚不可約支撐樹 y 丁 y g 否則 y g 一y 丁 d 因為g 是連通的 存在頂點耖 y 丁 使得 晰 t 0 其中蜥 u 是u 在 中的鄰居 假設(shè)名是 中的一個點 因為t 是弱 2 樹 u ny 丁 2 坼 u 0 義因為g u 是連通的 假設(shè)p 是一條 u 名 路 其中 u ny 丁 現(xiàn)在 讓加是尸上的第一個不在y t 中的點 則 u u 加 導(dǎo)出一個三 角形 那么 丁 u ot t j 是一含有比丁有更多頂點的弱2 樹 因為u 叫u t 彬 e g 并且 丁 g 我們有丁 扎 o 訓(xùn) g 但是這與 l y 丁 i 最大相矛盾 口 定理2 3 每一個頂點數(shù)至少為4 的局部連通圖都含有m s t 證明 根據(jù)引理2 1 和引理2 2 定理結(jié)論顯然 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 觚礎(chǔ)唱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