Return to search

圖之和弦圖數與樹寬 / The Chordality and Treewidth of a Graph

對於任何一個圖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.

Identiferoai:union.ndltd.org:CHENGCHI/G0098972004
Creators游朝凱
Publisher國立政治大學
Source SetsNational Chengchi University Libraries
Language英文
Detected LanguageEnglish
Typetext
RightsCopyright © nccu library on behalf of the copyright holders

Page generated in 0.0015 seconds