오일러 경로

'한붓그리기' 로 모든 간선을 칠한다면 그게 바로 오일러 경로

 

오일러 경로가 존재하려면

1. 출발점=도착점인 경우 (오일러 서킷)

양방향: 모든 정점의 차수가 짝수면 된다.

단방향: 모든 정점의 indegree==outdegree

 

2. 출발점 != 도착점인 경우 (오일러 트레일)

양방향: 출발점과 도착점의 차수는 홀수고 나머지 정점의 차수는 짝수면 된다.

단방향: outdegree[i]==indegree[i]+1인 점(시작점) 단 한개, indegree[i]==outdegree[i]+1인 점(도착점) 단 한개 존재.

 

컴포넌트가 여러 개인 경우 당연히 오일러 서킷이 존재하지 않을 거라고 생각할 수 있지만, 컴포넌트의 정점이 하나인 경우 간선이 존재하지 않는다는 점을 유념해야 한다.

-> 모든 간선이 하나의 컴포넌트에 포함되어 있다면 오일러 서킷이 될 가능성이 있다.

---

<구현>

시작점만 잘 잡아준 후 다음 코드로 구현.(책에선 파라미터로 벡터를 넘겨서 초기화.)

양방향 그래프라면 adj[v][u]-- 넣어주면 된다.

vector<int> ans;
void getEuler(int u) {
	for(int v=0; v<26; v++)
		while (adj[u][v] > 0) {
			adj[u][v]--;
			getEuler(v);
		}
	ans.push_back(u);
}

 

방향그래프 기준 getEuler함수를 처음 호출할 시작점은 다음과 같이 판단한다.

양방향그래프라면 차수가 짝수인지 홀수인지로 판단하면 될 것.

int trailOrCircuit() {
	//가능한 시작점의 수, 도착점의 수
	int s = 0, e = 0; 
	for (int i = 0; i < 26; i++) {
		int t = oud[i] - ind[i];		
		if (t == 1) s++;
		if (t == -1)e++;
	}

	if (s == 1 && e == 1) return 1; //오일러 트레일
	if (s == 0 && e == 0) return 2; //오일러 서킷
	return 0;//한붓그리기 불가
}

 

위 함수에서 주어진 그래프가 오일러 트레일이라고 판단한 경우, oud[i]==ind[i]+1인 점은 단 하나 있어야 하고, 그 점에서 오일러 경로가 시작돼야 한다.

 

서킷이라고 판단한 경우, 주어진 그래프가 오일러 서킷이라면 outdegree가 단 하나라도 있는 그 어떤 점에서 출발해도 오일러 서킷이 돼야 한다.

 

만들어진 ans의 크기가 n+1이 아니라면 이 그래프는 오일러 경로가 없다.

 

 

주의할 점

1. ans에 담기는 것은 정점 번호이지만 핵심은 간선(ans[i-1], ans[i])이다.

2. 방향그래프의 경우 ans를 뒤집어줘야 한다.

3. ans에 담긴 정점의 수는 곧 간선의 수+1이다. ans.size()==n+1인지 검사해줘야 한다. 

 

 

---

시간복잡도는 O(V+E)이다. 

 

어떤 문제가 오일러 경로 문제인지 알기 힘든 경우가 많다. 창의력이 필요한 부분이다.

예시문제 : https://suuntree.tistory.com/177