政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/32588

政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/32588

English | 正體中文 | 简体中文 | Post-Print筆數 : 27 | 全文筆數/總筆數 : 112881/143847 (78%)
造訪人次 : 50298087 線上人數 : 615

RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.

搜尋範圍

查詢小技巧：

您可在西文檢索詞彙前後加上"雙引號"，以獲取較精準的檢索結果

若欲以作者姓名搜尋，建議至進階搜尋限定作者欄位，可獲得較完整資料

進階搜尋

主頁 ‧ 登入 ‧ 上傳 ‧ 說明 ‧ 關於政大典藏 ‧ 管理

到手機版

政大機構典藏 > 理學院 > 應用數學系 > 學位論文 > Item 140.119/32588

請使用永久網址來引用或連結此文件: https://nccur.lib.nccu.edu.tw/handle/140.119/32588

題名:	完全C邊混合超圖的著色多項式 The Chromatic Polynomial of A Mixed Hypergraph with Complete C-edges
作者:	吳仕傑
貢獻者:	張宜武吳仕傑
關鍵詞:	混合超圖分離-收縮法循環的 mixed hypergraph splitting-contraction algorithm circular
日期:	2007
上傳時間:	2009-09-17 13:48:14 (UTC+8)
摘要:	在這篇論文中，我們利用分離－收縮法(splitting-contraction algorithm)獲得一個擁有完全C邊以及循環D邊特性的圖之著色多項式。假如一個混合超圖在點集合上有主要的循環，使得所有的C邊和D邊包含一個主循環(host cycle)的連接子圖，則稱此圖為循環的(circular)。對於每個l≧2，所有連續l個點會形成一個D邊時，我們把D記作D_l。如此一來，超圖(X,Φ,D_2)就是圖論中n個點的普通循環。我們先觀察擁有完全C邊和循環D邊的超圖，利用分離－收縮法的第一步，找到遞迴關係式並且解它。然後我們就推廣到一般完全C邊及循環D邊的超圖。 In this thesis, we obtain the chromatic polynomial of a mixed hypergraph with complete C-edges and circular D-edges by using splitting-contraction algorithm. A mixed hypergraph H=(X,C,D) is called circular if there exists a host cycle on the vertex set X such that every C-edge and every D-edge induces a connected subgraph of the host cycle. For each l≧2, we denote D by D_l if and only if every l consecutive vertices of X form a D-edge. Thus the mixed hypergraph (X,Φ,D_2) is a simple classical cycle on n vertices. We observe first a mixed hypergraph with complete C-edges and D_2. By the first step of the splitting-contraction algorithm, we can find out the recurrence relation and solve it. Then we generalize the mixed hypergraph with complete C-edges and circular D-edges.
參考文獻:	[1] Voloshin, V. (1993), The mixed hypergraphs, Comput. Sci. J. Moldova, 1, pp. 45-52. [2] Voloshin, V. and Voss, H.-J. (2000), Circular Mixed hypergraphs I: colorability and unique colorability, Congr. Numer., 144, pp. 207-219. [3] Voloshin, V. (2002), Coloring Mixed Hypergraphs: Theory, Algorithms and Applications, American Mathematical Society. [4] West, D.B. (2001), Introduction to Graph Theory, 2nd ed., Prentice Hall.
描述:	碩士國立政治大學應用數學研究所 94751011 96
資料來源:	http://thesis.lib.nccu.edu.tw/record/#G0094751011
資料類型:	thesis
顯示於類別:	[應用數學系] 學位論文

文件中的檔案:

檔案	描述	大小	格式	瀏覽次數
101101.pdf		82Kb	Adobe PDF2	966	檢視/開啟
101102.pdf		139Kb	Adobe PDF2	852	檢視/開啟
101103.pdf		32Kb	Adobe PDF2	655	檢視/開啟
101104.pdf		49Kb	Adobe PDF2	728	檢視/開啟
101105.pdf		81Kb	Adobe PDF2	788	檢視/開啟
101106.pdf		48Kb	Adobe PDF2	720	檢視/開啟
101107.pdf		60Kb	Adobe PDF2	715	檢視/開啟
101108.pdf		25Kb	Adobe PDF2	676	檢視/開啟

在政大典藏中所有的資料項目都受到原著作權保護.

社群 sharing

著作權政策宣告 Copyright Announcement

1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.

DSpace Software Copyright © 2002-2004 MIT & Hewlett-Packard / Enhanced by NTU Library IR team Copyright © - 回饋