Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/45015
Title: | K2,4,n之交叉數 The Crossing Number of K2,4,n |
Authors: | Chen-Chu Su 蘇承祖 |
Advisor: | 陳文進 |
Keyword: | 交叉數,圖,完全二分圖,完全三分圖,NP完備, Crossing number,graph,complete bipartite graph,complete tripartite graph,NP-complete, |
Publication Year : | 2010 |
Degree: | 碩士 |
Abstract: | 交叉數是一個圖,在平面上所有的畫法中,可以畫出最小的交叉數。在這篇論
文,根據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 |
Fulltext Rights: | 有償授權 |
Appears in Collections: | 資訊工程學系 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ntu-99-1.pdf Restricted Access | 250.19 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.