• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
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.

Page generated in 0.0208 seconds