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