作者mqazz1 (無法顯示)
看板Math
標題[圖論] euler trail
時間Wed Jul 27 12:06:56 2011
suppose that G=(V,E) is a directed graph, where |V| > 1
let di(in) and di(out) denote the indegree and outdegree of vertex i
then, G has a u-to-v Euler trail
iff the underlying graph of G is connected
and either
(a) u = v and di(in)=di(out) for every i in V, or
(b) u =/= v, di(in)=di(out) for every i in V-{u,v},
du(in) = du(out)-1, and dv(in) = dv(out)+1
請問這題該怎麼證呢?
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 192.192.13.101
1F：推 XII :=>easy;<=(a)有cycle,then數歸,(b)by(a) 07/27 23:59