[數學]徵求graph theory圖學高手救苦救難

[數學]徵求graph theory圖學高手救苦救難

sagen 於 星期日 十一月 13, 2005 3:14 pm


A block in a graph G is a maximal biconnected component. G is a block graph if every
block of G is a clique. G is a cactus graph if every block of G is either a cycle or an
edge. G is a block-cactus graph if every block of G is either a clique or a cycle. Answer
the following questions.
(1) How to recognize a block-cactus graph?
(2) Are block, cactus, and block-cactus graphs perfect? Note that a graph is perfect
if its chromatic number equals to its maximum clique size.
(3) Propose an algorithm to find a minimum dominating set on a block-cactus
graph.

sagen
初學者
初學者
 
文章: 1
註冊時間: 2005-11-13
來自: 台北






大學以上數學問題