標題: Berge路徑分割猜測的研究
A Study of Berge's Strong Path Partition Conjecture
作者: 張雁婷
傅恆霖
應用數學系所
關鍵字: Berge路徑分割猜測;路徑分割;Berge;path partition;conjecture
公開日期: 2006
摘要: 令P是一個由路徑(path)所形成的集合。若P裡的路徑兩兩交集為空集合,而且P中所有路徑的點聯集為圖G所有的點,則P是圖G的一組路徑分割(path partition)。令k是一個正整數,則我們對任一組路徑分割P可以定義它的k範數(k-norm)。若一組路徑分割擁有最小的k範數,則此路徑分割被稱為是最優化的k範數分割。   令C^k是圖G的一組k著色,即圖G中k個由點形成的獨立集所成之集合,而且兩兩獨立集交集為空集合。若路徑分割P裡任一條路徑中有min{|P_i|,k}個點分別落在C^k裡不同的獨立集,則稱此k著色C^k正交於路徑分割P。Berge猜測對於任一組最優化的k範數分割,都可找到一組k著色正交於此最優化的k範數分割。 這個猜測至今尚未被解決,只有一些特別的情形被證明;而在這篇論文裡,我們藉由一些特殊的圖來驗證Berge的猜測是對的。
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT009422527
http://hdl.handle.net/11536/81306
顯示於類別:畢業論文


文件中的檔案:

  1. 252701.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。