1 |
圖之和弦圖數與樹寬 / The Chordality and Treewidth of a Graph游朝凱 Unknown Date (has links)
對於任何一個圖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.
|
2 |
系列平行圖的長方形數與和絃圖數 / The Boxicity and Chordality of a Series-Parallel Graph周佳靜 Unknown Date (has links)
一個圖形G = (V,E),如果可以找到最小k個和弦圖,則此圖形G = (V,E)的和弦圖數是k。
在這篇論文中,我們呈現存在一個系列平行圖的boxicity是3,且和弦圖數是1或2,存在一個平面圖形的和弦圖數是3。 / The chordality of G = (V,E) is dened as the minimum k such that we can write E = E1n...nEk, where each (V,Ei) is a chordal graph.
In this thesis, we present that (1) there are series-parallel graphs with boxicity 3, (2) there are series-parallel graphs with chordality 1 or 2, and (3) there are planar graphs with chordality 3.
|
Page generated in 0.014 seconds