Saturday, July 28, 2007

Research notes (k-almost trees)

其實 k-almost tree 就是一個擁有 n 個點與 n + k - 1 條邊的連通圖。因為 n 個點的 tree 有 n - 1 條邊,所以一個 k-almost tree 比正常的 tree 多了 k 條邊。

Got it.

4 comments:

BarrosH said...

這個名詞有點奇怪?

如果 k-almost tree 是指 almost tree(k),則定義是 `` A graph is an almost tree (k) if every biconnected component has the property that there are at most k edges not in a spanning tree of this biconnected component.''

Joseph, Chuang-Chieh Lin said...

我那定義是從某篇 paper 上看來的:

A k-almost tree is a connected graph with n vertices and n + k − 1 edges. (*)

感覺上真的是不一樣。

你提到的定義裡頭還特別指明是針對 "every biconnected component",我看的定義裡頭應該只是每個 connected component 裡頭的 spanning tree 至多擁有多餘的 k 條邊。

附註:

剛剛查了一下 biconnected component 的定義:

A connected graph that is not broken into disconnected pieces by deleting any single vertex (and incident edges).

感覺就是「連通性比較強」的連通圖。亦即任意砍掉一個點與它所連結的邊都還不足以使一個連通圖變得不連通。

(*) J. Fiala, T. Kloks, J. Kratochv\'{\i}l: Fixed-parameter complexity of $\lambda$-labelings. Discrete Applied Mathematics, 113 (2001) pp. 59-72.

BarrosH said...

嗯嗯,almost tree(k) 其實是早期另一種 測量圖的 tree-like 程度的方法。

cactus graph 就是 almost tree(1)。

我會知道這個圖也是因為 bounded treewidth.

不過後來好像就輸給 treewidth 了,很少人用這個 graph class 的樣子。

Joseph, Chuang-Chieh Lin said...

Ya... Treewidth is more common.

BTW, 你那張照片真是好玩。 :D