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

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

English | 正體中文 | 简体中文 | Post-Print筆數 : 27 | Items with full text/Total items : 109952/140887 (78%)
Visitors : 46280735 Online Users : 1209

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

Scope

please add "double quotation mark" for query phrases to get precise results

please goto advance search for comprehansive author search

Adv. Search

Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer

Goto mobile version

政大典藏 > College of Science > Department of Mathematical Sciences > Theses > Item 140.119/32588

Please use this identifier to cite or link to this item: https://nccur.lib.nccu.edu.tw/handle/140.119/32588

Title:	完全C邊混合超圖的著色多項式 The Chromatic Polynomial of A Mixed Hypergraph with Complete C-edges
Authors:	吳仕傑
Contributors:	張宜武吳仕傑
Keywords:	混合超圖分離-收縮法循環的 mixed hypergraph splitting-contraction algorithm circular
Date:	2007
Issue Date:	2009-09-17 13:48:14 (UTC+8)
Abstract:	在這篇論文中，我們利用分離－收縮法(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.
Reference:	[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.
Description:	碩士國立政治大學應用數學研究所 94751011 96
Source URI:	http://thesis.lib.nccu.edu.tw/record/#G0094751011
Data Type:	thesis
Appears in Collections:	[Department of Mathematical Sciences] Theses

Files in This Item:

File	Description	Size	Format
101101.pdf		82Kb	Adobe PDF2	966	View/Open
101102.pdf		139Kb	Adobe PDF2	852	View/Open
101103.pdf		32Kb	Adobe PDF2	655	View/Open
101104.pdf		49Kb	Adobe PDF2	728	View/Open
101105.pdf		81Kb	Adobe PDF2	788	View/Open
101106.pdf		48Kb	Adobe PDF2	720	View/Open
101107.pdf		60Kb	Adobe PDF2	715	View/Open
101108.pdf		25Kb	Adobe PDF2	676	View/Open

All items in 政大典藏 are protected by copyright, with all rights reserved.

社群 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 © - Feedback