毛毛虫树三角和四边形变换下的割宽不变性.pdf

37 4 ( ) Vo.l 37 No. 4 2009 8 Journal of Fuzhou Un iversity( Natural Science E ition) Aug. 2009 : 1000- 2243( 2009) 04- 0482- 04 (, 350002) : , NP , . , . : ; ; ; : 0157. 5 : A Cu tw id th of caterp illa r under triangle tran sform ation and quadrangle tran sfo rm ation FANG Kan ( Zhicheng College, Fuzhou University, Fuzhou, Fujian 350002, Ch ina) Abs tract: The cutw i th problem is known that the problem for general graphs is NP har w hile it is polynom ially solvable for trees. Suppose thatG is a caterpillar, a necessary an sufficient con ition is given for a caterp illar G to have the sam e cutw i th w ith the graph obtaine by G un er triangle or qua rangle transformation. Keywords: cuwt i th; triangle transform ation; qua rangle transformation; caterpillar 1 [ 1, 2] , . , , [ 3] . NP , [ 4] . , , , [ 1, 5, 6] . : 1)G = ( V, E) , V, | V | = n, E. G f : V { 1, 2, , n}, G . G f , f : c(G, f ) = m ax {uv E: f (u) i f (v) } 1 i n f : c(G ) = m in c( G, f ) f , u = f - 1 ( i), f u , u , , u i 1 2