標題: | 遞增子圖分割問題的研究 |
作者: | 周俊良 ZHOU, JUN-LIANG 傅□霖 FU, HENG-LIN 應用數學系所 |
關鍵字: | 遞增子圖;分割;遞增配對子圖分割;遞增路徑子圖分割;遞增子圖分割;遞增星星子圖;輪子圖形;AS;AMD;APD;ASD;ATD;WHEEL-PICTURE;ALAVI-Y. |
公開日期: | 1987 |
摘要: | 把一個具有n (n +1)╱2個邊的圖分割成n 個遞增子圖的問題,最早是由Y.Ala- vi等五人所提出來的,實際上他們有下列的臆測。 臆測:一個有n (n +1)╱2邊的圖可被分割成n 個遞增子圖,而且子圖的邊數恰 為1,2,……,n 。 一個圖可被分割成像臆測中所說的一樣,則說它有遞增子圖分割(ASD ),如果它的 子圖是配對(matching)則為遞增配對子圖分割(AMD ),子圖是路徑(path)則為 遞增路徑子圖分割(APD ),如子圖是星星(star)則為遞增星星子圖分割(ATD ) 。 在本文中,最主要的目的是研究遞增子圖分割的問題。在第二章,我們研究遞增子圖 分割,先回顧一些已知結果,然後證明類似星星(star-like )圖有遞增子圖分割。 接著,在第三章和第四章我們討論一些子圖為配對,路徑和星星的特殊分割。最後, 在第五章中我們證明臆測在輪子(wheel )圖形中是正確的。 |
URI: | http://140.113.39.130/cdrfb3/record/nctu/#NT762507010 http://hdl.handle.net/11536/53539 |
顯示於類別: | 畢業論文 |