📂그래프이론

플뢰리 알고리즘 증명

정의 ¹

$G$ 가 오일러 그래프라고 하자. 그러면 다음과 같은 방법으로 오일러 트레일을 만들 수 있다.

임의의 버텍스 $u$ 에서 시작해서 다음의 두 규칙을 따라 트레일을 만든다:

• (i): 이미 지나온 에지는 지운다. 만약 에지가 지워지면서 고립 버텍스가 되면 그 버텍스도 지운다.
• (ii): 각 단계에서 브릿지는 다른 대안이 없을때만 지나간다.

---

• 에지 $b \in G$ 가 지워짐으로써 그래프가 단절되면 $b$ 를 브릿지라고 부른다.

설명

오일러 그래프의 오일러 트레일은 정의에서 그 존재성이 보장되지만 구체적으로 오일러 트레일이 어떻게 생겼는지까지는 알 수 없다. 플뢰리 알고리즘은 주어진 오일러 그래프에서 오일러 트레일을 만들어준다.

증명

오일러 그래프의 동치 조건: $G$ 가 연결 그래프라고 하자.

$G$ 가 오일러 그래프인 것과 $G$ 의 모든 버텍스의 차수가 짝수인 것은 동치다.

트레일이 $u$ 에서 나와서 버텍스 $v$ 에 들어가면 그 에지를 지운다. 만약 $v = u$ 면 $v \ne u$ 일 때까지 루프를 돌면 된다. 만약 $v \ne u$ 면 그 에지가 지워진 서브 그래프 $H$ 는 여전히 연결 그래프고 $u$ 와 $v$ 두 버텍스의 차수만이 홀수다. 따라서 이러한 제거를 한 번 더 했을 때 $H$ 는 여전히 연결 그래프임을 보여야한다. 만약 어떤 버텍스 $w$ 에 대해 $H - vw$ 가 연결 그래프가 아니라고 가정하면, 그것은 $H - vw$ 에 $w$ 를 포함하면서 $u$ 는 포함하지 않는 어떤 컴포넌트 $K$ 가 존재한다는 것이다. $K$ 의 버텍스 $w$ 는 차수가 홀수이므로, $K$ 는 차수가 홀수인 또 다른 버텍스 하나를 가져야만한다. 그러나 이는 모순이므로, $H - vw$ 는 연결 그래프임을 보장할 수 있다. 다시 말해, 이러한 제거는 몇 번을 반복해도 여전히 연결 그래프인데 규칙 (ii)에 따르면 어떤 단계에서든 브릿지는 마지막에만 지울 수 있으므로 트레일의 종점은 $u$ 여야만한다.

■