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

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

English | 正體中文 | 简体中文 | Post-Print筆數 : 27 | Items with full text/Total items : 113318/144297 (79%)
Visitors : 51104869 Online Users : 861

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/96375

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

Title:	圖之和弦圖數與樹寬 The Chordality and Treewidth of a Graph
Authors:	游朝凱
Contributors:	張宜武游朝凱
Keywords:	和弦圖數樹寬樹分解系列平行圖 Chordality Treewidth Tree Decomposition Series Parallel Graph
Date:	2011
Issue Date:	2016-05-10 19:33:38 (UTC+8)
Abstract:	對於任何一個圖G = (V;E) ，如果我們可以找到最少的k 個弦圖(V;Ei)，使得E = E1 \\ \\ Ek ，則我們定義此圖G = (V;E) 的chordality為k ；而一個圖G = (V;E) 的樹寬則被定義為此圖所有的樹分解的寬的最小值。在這篇論文中，最主要的結論是所有圖的chordality 會小於或等於它的樹寬；更特別的是，有一些平面圖的chordality 為3，而所有系列平行圖的chordality 頂多為2。 The chordality of a graph G = (V;E) is dened as the minimum k such that we can write E = E1 \\ \\ Ek, where each (V;Ei) is a chordal graph. The treewidth of a graph G = (V;E) is dened to be the minimum width over all tree decompositions of G. In this thesis, the principal result is that the chordality of a graph is at most its treewidth. In particular, there are planar graphs with chordality 3, and series-parallel graphs have chordality at most 2. Abstract ii 中文摘要iii 1 Introduction 1 1.1 History of Chordality and Treewidth 1 1.2 The De nition of Chordality and Treewidth 2 2 The Chordality of a Graph 6 2.1 Theorems and Examples of Chordality 6 2.2 The Counter Example 14 3 The Treewidth of a Graph 15 3.1 The Treewidth of Some Classes of Graphs 15 3.2 The Chordality of K2;2;2 22 4 Chordality vs. Treewidth 23 4.1 The Weaker Inequality between Chordality and Treewidth 23 4.2 Chordality Bounded by Its Treewidth 24 4.3 The Chordality of Series{Parallel Graphs 37 References 38
Reference:	[1] L.W. Beineke and R.E. Pippert, Properties and characterizations of k-trees, Mathematika, 18 (1971), 141-151. [2] P. Bumeman, A characterization of rigid circuit graphs, Discrete Mathematics, 9 (1974), 205-212. [3] M.B. Cozzens and F.S. Roberts, On dimensional properties of graphs, Graphs and Combinatorics, 5 (1989), 29-46. [4] G.A. Dirac, A property of 4-chromatic graphs and some remarks on critical graphs, J. London Math. Soc., 27 (1952), 85-92. [5] R.J. Dun, Topology of series parallel-networks, J. Math. Anal. Appl., 10 (1965), 303-318. [6] F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, Journal of Combinatorial Theory (B), 16 (1974), 47-56. [7] Pinar Heggernes, Treewidth, partial k-trees, and chordal graphs, Delpensum INF 334- Institutt for informatikk, (2006). [8] Terry A. McKee and Edward R. Sceinerman, On the Chordality of a Graph, Journal of Graph Theory, 17 (1993), 221-232. [9] H.P. Patil, On the structure of k{trees, J. Combin. Inform. System. Sci., 11 (1986), 57-64. [10] N. Roberston and P.D. Seymour, Graph minors II: algorithmic aspects of tree width, J. of Algorithms, 7 (1986), 309-322. [11] D.J. Rose, On simple characterizations of k-trees, Discrete Math., 7 (1974), 317-322. [12] J.R. Walter, Representations of chordal graphs as subtrees of a tree, J. Graph Theory, 2 (1978), 265-267.
Description:	碩士國立政治大學應用數學系數學教學碩士在職專班 98972004
Source URI:	http://thesis.lib.nccu.edu.tw/record/#G0098972004
Data Type:	thesis
Appears in Collections:	[Department of Mathematical Sciences] Theses

Files in This Item:

File	Size	Format
index.html	0Kb	HTML2	297	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