2개의 댓글이 있습니다.
-
-
infoefficiency -
아~ 그러면 유향그래프에서는 오일러 서킷을 만족하려면
indegree와 outdegree가 같아야 되기 떄문에
오일러 서킷의 조건을 만족시켜주려고
b->a의 조건을 추가 하는 거 맞죠?
10년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
infoefficiency
a에서 시작하고 b에서 끝나는 오일러 트레일을 찾기 위해서는
간선(b,a)를 그래프에 추가한 뒤 오일러 서킷을 찾으면 된다.
라고 적혀있는데
b에서 끝나려면
b의 입장에서는 indegree가 하나 많고 outdegree가 하나 적고
a의 입장에서는 indegree가 하나 적고 outdegree가 하나 많아야
하기 때문에
(a,b) 로 해야하지 않나 생각해봤습니다.
책에 있는 (b,a)가 b->a로의 간선을 의미하는 것은 맞는지도
궁금해서 올렸습니다.
감사합니다.
10년 전