[圖論] euler trail
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
推
07/27 23:59, , 1F
07/27 23:59, 1F