作者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