請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/45015
標題: | K2,4,n之交叉數 The Crossing Number of K2,4,n |
作者: | Chen-Chu Su 蘇承祖 |
指導教授: | 陳文進 |
關鍵字: | 交叉數,圖,完全二分圖,完全三分圖,NP完備, Crossing number,graph,complete bipartite graph,complete tripartite graph,NP-complete, |
出版年 : | 2010 |
學位: | 碩士 |
摘要: | 交叉數是一個圖,在平面上所有的畫法中,可以畫出最小的交叉數。在這篇論
文,根據Kleitman證明完全二分圖的結果,我們證明了對於所有的n, K2,4,n這個 完全三分圖的交叉數。最後,我們提出了關於K2,m,n交叉數的猜想。 The crossing Number $cr(G)$ of a graph $G$ is the smallest crossing number among all drawings of $G$ in the plane. In this paper, we determine the crossing number of the tripartite graph $K_{2,4,n}$ for any integer $n$. Our proof depends on Kleitman's results for the complete bipartite graphs. At last, we propose a conjecture of the crossing number of $K_{2,m,n}$. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/45015 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf 目前未授權公開取用 | 250.19 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。