한붓그리기

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 역사와 어원
4. 성질
5. 오일러 회로 및 경로 구성 알고리즘
- 5.1. 플뢰리 알고리즘
- 5.2. 히에르홀처 알고리즘
6. 오일러 회로 수 계산
- 6.1. 복잡도 문제
- 6.2. 특수한 경우
7. 응용
8. 무한 그래프
9. 혼합 그래프
참조

1. 개요

한붓그리기는 그래프의 모든 변을 포함하는 트레일 또는 사이클을 찾는 문제이다. 한붓그리기는 시작점과 끝점이 같은 닫힌 한붓그리기와, 시작점과 끝점이 다른 한붓그리기로 나뉜다. 닫힌 한붓그리기를 갖는 그래프는 오일러 그래프라고 한다. 그래프가 닫힌 한붓그리기를 갖기 위한 필요충분 조건은 연결 그래프이면서 모든 꼭짓점의 차수가 짝수여야 한다는 것이다. 한붓그리기는 레온하르트 오일러가 쾨니히스베르크의 다리 문제를 해결하기 위해 도입했으며, 플뢰리 알고리즘과 히에르홀처 알고리즘과 같은 알고리즘을 통해 찾을 수 있다.

더 읽어볼만한 페이지

레온하르트 오일러 - 오일러-라그랑주 방정식
오일러-라그랑주 방정식은 변분법으로 범함수의 정류점을 찾는 편미분 방정식으로, 라그랑주 역학 등 다양한 분야에 활용되며 뉴턴 역학을 일반화한 것으로 여겨진다.
레온하르트 오일러 - 오일러-마스케로니 상수
오일러-마스케로니 상수 $\gamma$ 는 조화급수와 자연로그 함수의 차이의 극한으로 정의되는 수학 상수로, 감마 함수, 리만 제타 함수 등 다양한 수학적 개념과 관련되어 있으며 유리수인지 무리수인지 밝혀지지 않은 미해결 문제이다.
그래프 이론 - 다이어그램
다이어그램은 2차원 기하학적 기호를 사용하여 정보를 시각적으로 표현하는 기술로, 과학, 공학, IT, 비즈니스 등 다양한 분야에서 활용되며 정보를 간략하게 나타내고 시각적 사고를 돕는다.
그래프 이론 - 쾨니히스베르크의 다리 문제
쾨니히스베르크의 다리 문제는 프레겔 강에 놓인 7개의 다리를 한 번씩만 건너 출발점으로 되돌아올 수 있는지 묻는 문제로, 오일러에 의해 그래프 이론적으로 분석되어 해결되었으며 그래프 이론의 탄생에 기여했다.
사람 이름을 딴 낱말 - 뒤베르제의 법칙
뒤베르제의 법칙은 선거제도와 정당 수 사이의 관계를 설명하는 가설로, 단순 다수 대표제는 양당제를, 결선투표제와 비례대표제는 다당제를 낳는다는 내용을 제시한다.
사람 이름을 딴 낱말 - 옴의 법칙
옴의 법칙은 1827년 게오르크 옴이 발표한, 전압(V)은 전류(I)와 저항(R)의 곱(V=IR)으로 표현되는, 전압, 전류, 저항 간의 관계를 나타내는 기본 법칙이다.

한붓그리기
정의
정의	그래프 이론에서, 오일러 경로(Eulerian trail)는 그래프의 모든 변(edge)을 정확히 한 번씩 통과하는 경로를 의미한다.
다른 이름	오일러 경로(Eulerian trail), 오일러 체인(Eulerian chain), 오일러 트레버스(Eulerian traverse)
종류
오일러 회로 (Euler circuit)	시작 정점과 끝 정점이 같은 오일러 경로
열린 오일러 경로 (open Eulerian trail)	시작 정점과 끝 정점이 다른 오일러 경로
조건
오일러 경로 존재 조건 (무방향 그래프)	연결 그래프이어야 한다. 홀수 차수를 가지는 정점의 개수가 0개 또는 2개이어야 한다.
오일러 회로 존재 조건 (무방향 그래프)	연결 그래프이어야 한다. 모든 정점의 차수가 짝수여야 한다.
오일러 경로 존재 조건 (방향 그래프)	약하게 연결된 그래프이어야 한다. 모든 정점에 대해 (나가는 차수) = (들어오는 차수)이거나, 시작 정점의 경우 (나가는 차수) = (들어오는 차수) + 1, 끝 정점의 경우 (들어오는 차수) = (나가는 차수) + 1, 나머지 정점의 경우 (나가는 차수) = (들어오는 차수)이어야 한다.
오일러 회로 존재 조건 (방향 그래프)	강하게 연결된 그래프이어야 한다. 모든 정점에 대해 (나가는 차수) = (들어오는 차수)이어야 한다.
응용
응용 분야	DNA 시퀀싱 로봇 경로 계획 데이터 압축
관련 항목
관련 항목	쾨니히스베르크 다리 문제 해밀턴 경로 최단 경로 문제 그래프 순회

2. 정의

(단순) 그래프 $G$ 위의 '''한붓그리기''' 또는 '''오일러 트레일'''은 그래프의 모든 변을 포함하는 트레일이다. (정의에 따라, 트레일은 변을 중복해서 거칠 수 없다.) '''닫힌 한붓그리기'''는 시작점과 끝점이 같은 한붓그리기다. 일부 저자들은 닫힌 트레일을 '''회로'''(circuit^영어)라고 부르며, 이 경우 닫힌 한붓그리기는 '''오일러 회로'''(Eulerian circuit^영어)가 된다.

(단순) 유한 그래프 $G$ 에 대하여, 다음 두 조건은 서로 동치이다.

$G$ 는 닫힌 한붓그리기를 가진다.
$G$ 는 연결 그래프이며, $G$ 의 모든 꼭짓점의 차수는 짝수이다.

닫힌 한붓그리기를 갖는 그래프를 '''오일러 그래프'''(Eulerian graph^영어)라고 한다.

(단순) 유한 그래프

G

에 대하여, 다음 두 조건은 서로 동치이다.

$G$ 는 한붓그리기를 가진다.
$G$ 는 연결 그래프이며, $G$ 의 홀수 차수 꼭짓점의 수는 0 또는 2이다.

만약 홀수 차수 꼭짓점이 2개 존재하는 경우,

G

의 한붓그리기는 이들 점들을 시작점·끝점으로 한다.

'''오일러 경로'''^[3] 또는 '''오일러 워크'''는 무향 그래프에서 각 변을 정확히 한 번씩 사용하는 경로이다. 이러한 경로가 존재하면 그래프를 '''통과 가능''' 또는 '''반-오일러'''라고 한다.^[4]

'''오일러 사이클'''^[3]은 무향 그래프에서 각 변을 정확히 한 번씩 사용하는 사이클이며, '''오일러 회로''' 또는 '''오일러 투어'''라고도 한다. 이러한 사이클이 존재하면 그래프를 '''오일러''' 또는 '''단일선'''이라고 한다.^[5] "오일러 그래프"라는 용어는 때때로 모든 정점의 차수가 짝수인 그래프를 나타내는 데 더 약한 의미로 사용되기도 한다. 유한한 연결 그래프의 경우 두 정의는 동일하며, 연결되지 않을 수 있는 그래프는 각 연결 구성 요소에 오일러 사이클이 있는 경우에만 더 약한 의미에서 오일러 그래프이다.

유향 그래프의 경우 "경로"는 ''유향 경로''로, "사이클"은 ''유향 사이클''로 대체되어야 한다.

오일러 경로, 사이클 및 그래프의 정의와 속성은 멀티그래프에도 유효하다.

무향 그래프 ''G''의 '''오일러 방향'''은 각 정점 ''v''에서 ''v''의 진입 차수가 ''v''의 진출 차수와 같도록 ''G''의 각 변에 방향을 할당하는 것이다. 이러한 방향은 모든 정점의 차수가 짝수인 모든 무향 그래프에 존재하며, ''G''의 각 연결 구성 요소에서 오일러 투어를 구성한 다음 투어에 따라 변의 방향을 지정하여 찾을 수 있다.^[6] 연결 그래프의 모든 오일러 방향은 결과 유향 그래프를 강하게 연결된 그래프로 만드는 방향인 강한 방향이다.

3. 역사와 어원

1736년에 레온하르트 오일러가 쾨니히스베르크의 다리 문제를 풀기 위하여 도입하였다. 이는 그래프 이론의 시초로 여겨진다.

"한붓그리기"라는 이름은 그래프를 붓으로 종이 위에 그리는 것에 빗댄 것이다. 그래프를 한붓그리기를 따라 그리게 되면 붓을 종이에서 떼지 않고, 이미 그린 변을 덧칠할 필요 없이 그릴 수 있다.

4. 성질

무방향 그래프는 모든 꼭짓점이 짝수 차수를 가지며, 0이 아닌 차수를 가진 모든 꼭짓점이 단일 연결 요소에 속할 때 오일러 회로를 갖는다.^[7]
무방향 그래프는 0개 또는 2개의 꼭짓점이 홀수 차수를 가지며, 0이 아닌 차수를 가진 모든 꼭짓점이 단일 연결 요소에 속하는 경우에만 오일러 트레일을 갖는다.^[7]
방향 그래프는 모든 꼭짓점이 동일한 내차수와 외차수를 가지며, 0이 아닌 차수를 가진 모든 꼭짓점이 단일 강하게 연결된 요소에 속하는 경우에만 오일러 회로를 갖는다.^[7]
방향 그래프는 최대 하나의 꼭짓점이 (외차수) - (내차수) = 1, 최대 하나의 꼭짓점이 (내차수) - (외차수) = 1, 다른 모든 꼭짓점이 동일한 내차수와 외차수를 가지며, 0이 아닌 차수를 가진 모든 꼭짓점이 기저 무방향 그래프의 단일 연결 요소에 속하는 경우에만 오일러 트레일을 갖는다.^[7]

5. 오일러 회로 및 경로 구성 알고리즘

연속된 획으로 도형을 그리는 문제를 풀기 위한 오일러 경로 사용: 니콜라우스의 집 퍼즐은 홀수 차수 꼭짓점(주황색)이 두 개이므로 경로는 한 점에서 시작하여 다른 점에서 끝나야 한다. 홀수 차수 꼭짓점이 4개인 변형은 해가 없다. 홀수 차수 꼭짓점이 없으면 경로는 어디에서나 시작할 수 있으며, 오일러 회로를 형성한다. 느슨한 끝은 차수가 1인 꼭짓점으로 간주되며, 그래프는 연결되어야 한다.

오일러 회로 및 경로 구성 알고리즘에는 플뢰리 알고리즘과 히에르홀처 알고리즘이 있다. 플뢰리 알고리즘은 1883년에 제시된 알고리즘으로 한붓그리기가 가능한 그래프에서 모든 간선을 한 번씩만 지나는 경로를 찾는 방법이지만 효율성은 떨어진다.^[8] 카를 히에르홀처는 1873년에 플뢰리 알고리즘보다 효율적으로 오일러 회로를 찾는 방법을 제시했다.^[10]

5. 1. 플뢰리 알고리즘

플뢰리 알고리즘은 1883년에 제시된 알고리즘으로, 한붓그리기가 가능한 그래프에서 모든 간선을 한 번씩만 지나는 경로를 찾는 방법 중 하나이다.^[8] 이 알고리즘은 우아하지만, 효율성은 떨어진다는 특징이 있다.

플뢰리 알고리즘은 다음 단계를 따른다.

1. 그래프에 홀수 차수(연결된 간선의 개수가 홀수인) 정점이 없거나, 홀수 차수 정점이 두 개 있는지 확인한다. 홀수 차수 정점이 두 개라면 그중 하나에서 시작하고, 없다면 아무 정점에서나 시작한다.

2. 현재 정점에서 연결된 간선 중, 제거했을 때 그래프가 두 개 이상의 연결 요소로 분리되지 않는 간선(단절선이 아닌 간선)을 선택하여 이동한다.

3. 만약 그런 간선이 없다면, 남아 있는 간선 중 아무거나 선택하여 이동한다.

4. 선택한 간선을 그래프에서 제거하고, 간선의 다른 끝점으로 이동한다.

5. 모든 간선이 제거될 때까지 2~4단계를 반복한다.

이 알고리즘이 끝났을 때, 간선이 선택된 순서가 바로 오일러 경로나 오일러 회로가 된다. 홀수 차수 정점이 두 개 있는 그래프에서는 오일러 경로를, 홀수 차수 정점이 없는 그래프에서는 오일러 회로를 얻게 된다.

플뢰리 알고리즘에서 그래프 순회 자체는 간선의 개수(|E|)에 비례하는 시간이 걸려 빠르지만, 각 단계에서 단절선(제거하면 그래프가 분리되는 간선)을 찾아야 하기 때문에 시간이 오래 걸린다. 모든 간선을 제거한 후 타잔의 선형 시간 단절선 찾기 알고리즘^[9]을 사용하면, 플뢰리 알고리즘의 시간 복잡도는

O(|E|^2)

이 된다. 미켈 토럽(M. Thorup)의 동적 단절선 찾기 알고리즘을 사용하면

O(|E| \cdot \log^3 |E| \cdot \log \log |E|)

로 개선할 수 있지만, 다른 알고리즘에 비해 여전히 느리다.

5. 2. 히에르홀처 알고리즘

카를 히에르홀처는 1873년에 플뢰리 알고리즘보다 효율적으로 오일러 회로를 찾는 방법을 제시했다.^[10]

히에르홀처 알고리즘은 다음과 같이 동작한다.

1. 시작 정점 ''v''를 선택하고, ''v''에서 시작하는 경로를 따라 ''v''로 돌아온다. 모든 정점의 차수가 짝수이므로, ''v''가 아닌 다른 정점에서 경로가 막히는 경우는 없다. 이렇게 만들어진 경로는 닫힌 경로이지만, 초기 그래프의 모든 정점과 간선을 포함하지 않을 수도 있다.

2. 현재 경로에 포함되지만, 아직 경로에 포함되지 않은 인접한 간선이 있는 정점 ''u''가 있다면, ''u''에서 다른 경로를 시작하여 사용하지 않은 간선을 따라 ''u''로 돌아온다. 그리고 이 경로를 이전 경로와 결합한다.

3. 원래 그래프가 연결 그래프라고 가정하면, 위 과정을 반복하여 그래프의 모든 간선을 포함하는 경로를 얻을 수 있다.

양방향 연결 리스트와 같은 자료 구조를 사용하면, 각 정점에서 사용하지 않은 간선을 찾고, 새로운 시작 정점을 찾고, 두 경로를 연결하는 작업을 상수 시간에 수행할 수 있다. 따라서 전체 알고리즘은 선형 시간, 즉

O(|E|)

시간 안에 오일러 회로를 찾을 수 있다.^[10]

이 알고리즘은 데크를 사용하여 구현할 수도 있다. 데크가 닫힌 경로를 나타낼 때만 막힐 수 있다는 점을 이용하여, 데크의 꼬리에서 간선을 제거하고 머리에 추가하는 방식으로 데크를 회전시키는 과정을 반복하면 모든 간선을 처리할 수 있다. 이 방법 또한 선형 시간이 걸린다.^[10]

6. 오일러 회로 수 계산

유향 그래프의 오일러 회로 수는 BEST 정리를 사용하여 계산할 수 있다. BEST 정리는 드 브루인, 반 아르덴-에렌페스트, 스미스, 터트의 이름에서 따왔다.^[11] 이 공식은 유향 그래프의 오일러 회로 수는 특정 차수 계승과 근원 아보레스턴스의 수의 곱으로 나타낼 수 있다고 명시한다. 아보레스턴스는 행렬 트리 정리를 통해 행렬식으로 계산할 수 있으며, 이는 다항 시간 알고리즘을 제공한다.

BEST 정리는 1951년 아르덴-에렌페스트와 드 브루인의 논문에서 처음 언급되었다. 원래 증명은 전단사 증명이었고 드 브루인 수열을 일반화했다. 이는 1941년 스미스와 터트의 이전 결과의 변형이다.

무향 그래프에서 오일러 회로 수를 세는 것은 훨씬 더 어렵다. 이 문제는 Sharp-P-완전으로 알려져 있다.^[11] 긍정적인 방향으로, 마르코프 연쇄 몬테카를로 접근 방식은 코치그 변환을 통해 (1968년) 그래프의 오일러 회로 수를 근사하는 것으로 알려져 있지만, 아직 이 사실에 대한 증명은 없다 (심지어 제한된 차수의 그래프에 대해서도).

6. 1. 복잡도 문제

유향 그래프의 오일러 회로 수는 BEST 정리를 사용하여 계산할 수 있다. BEST 정리는 드 브루인, 반 아르덴-에렌페스트, 스미스, 터트의 이름에서 따왔다.^[11] 이 공식은 유향 그래프의 오일러 회로 수는 특정 차수 계승과 근원 아보레스턴스의 수의 곱으로 나타낼 수 있다고 명시한다. 아보레스턴스는 행렬 트리 정리를 통해 행렬식으로 계산할 수 있으며, 이는 다항 시간 알고리즘을 제공한다.

BEST 정리는 아르덴-에렌페스트와 드 브루인의 논문 (1951)에서 처음 언급되었다. 원래 증명은 전단사 증명이었고 드 브루인 수열을 일반화했다. 이는 스미스와 터트 (1941)의 이전 결과의 변형이다.

무향 그래프에서 오일러 회로 수를 세는 것은 훨씬 더 어렵다. 이 문제는 Sharp-P-완전으로 알려져 있다.^[11] 긍정적인 방향으로, 마르코프 연쇄 몬테카를로 접근 방식은 코치그 변환을 통해 (1968년) 그래프의 오일러 회로 수를 근사하는 것으로 알려져 있지만, 아직 이 사실에 대한 증명은 없다 (심지어 제한된 차수의 그래프에 대해서도).

6. 2. 특수한 경우

완전 그래프의 오일러 회로 개수에 대한 점근 공식은 맥케이와 로빈슨(1995)이 다음과 같이 제시하였다.^[12]

:

\operatorname{ec}(K_n) = 2^{\frac{(n+1)}{2}}\pi^{\frac{1}{2}} e^{\frac{-n^2}{2}+\frac{11}{12}} n^{\frac{(n-2)(n+1)}{2}} \bigl(1+O(n^{-\frac{1}{2}+\epsilon})\bigr).

이후 M.I. 이사예프(2009)는 완전 이분 그래프에 대한 유사한 공식을 얻었다.^[13]

:

\operatorname{ec}(K_{n,n}) = \left(\frac{n}{2}-1\right)!^{2n} 2^{n^2-n+\frac{1}{2}}\pi^{-n+\frac{1}{2}} n^{n-1}  \bigl(1+O(n^{-\frac{1}{2}+\epsilon})\bigr).

7. 응용

생물정보학에서 DNA 염기 서열 조각으로부터 DNA 서열을 재구성하는 데 오일러 경로가 사용된다.^[14] CMOS 회로 설계에서는 최적의 논리 게이트 순서를 찾는 데 사용된다.^[15] 트리의 오일러 투어(각 모서리를 한 쌍의 아크로 취급)에 의존하는 알고리즘도 몇 가지 있다.^[16]^[17] 드 브루인 수열은 드 브루인 그래프의 오일러 경로로 구성할 수 있다.^[18]

8. 무한 그래프

무한 그래프에서 오일러 트레일 또는 오일러 사이클에 해당하는 개념은 그래프의 모든 변을 포함하는 양방향 무한 트레일인 오일러 선이다. 이러한 트레일이 존재하려면 그래프가 연결되어 있고 모든 꼭짓점의 차수가 짝수여야 한다는 것만으로는 충분하지 않다. 예를 들어, 모든 꼭짓점의 차수가 4인 케일리 그래프에는 오일러 선이 없다.^[19]^[20]

무한 그래프 또는 멀티그래프가 오일러 선을 가지기 위한 조건은 다음과 같다:^[19]^[20]

G는 연결되어 있다.
G는 가산 집합의 꼭짓점과 변을 가진다.
G는 (유한) 홀수 차수의 꼭짓점을 갖지 않는다.
유한 부분 그래프 S를 G에서 제거하면 나머지 그래프에 최대 두 개의 무한 연결 요소가 남고, S가 각 꼭짓점에서 짝수 차수를 가지면 S를 제거하면 정확히 하나의 무한 연결 요소가 남는다.

9. 혼합 그래프

짝수이고 대칭적인 모든 혼합 그래프는 오일러 그래프임이 보장된다. 하지만 이는 필요 조건은 아니다. 왜냐하면 비대칭적이지만 짝수이고 오일러 그래프인 그래프를 구성하는 것이 가능하기 때문이다.^[21]

이 혼합 그래프는 오일러 그래프이다. 그래프는 짝수이지만 대칭적이지 않으며, 이는 짝수성과 대칭성이 혼합 그래프가 오일러 그래프가 되기 위한 필요 충분 조건이 아님을 증명한다.

Ford와 Fulkerson은 1962년 그들의 저서 《네트워크 흐름》에서 그래프가 오일러 그래프이기 위한 필요 충분 조건을 증명했는데, 즉, 모든 정점이 짝수여야 하고 균형 조건을 만족해야 한다. 정점의 모든 부분 집합 S에 대해 S를 떠나는 호의 수와 S로 들어가는 호의 수의 차이는 S에 연결된 변의 수보다 작거나 같아야 한다.^[21]

혼합 그래프가 오일러 그래프인지 확인하는 과정은 무향 그래프 또는 유향 그래프가 오일러 그래프인지 확인하는 것보다 더 어렵다. 왜냐하면 균형 집합 조건은 가능한 모든 정점의 부분 집합과 관련되기 때문이다.

참조

_[1] 서적 Graph Theory, 1736–1936 Clarendon Press
_[2] 논문 Two-graphs, switching classes and Euler graphs are equal in number http://neilsloane.co[...]
_[3] 문서 Some people reserve the terms ''path'' and ''cycle'' to mean ''non-self-intersecting'' path and cycle. A (potentially) self-intersecting path is known as a '''trail''' or an '''open walk'''; and a (potentially) self-intersecting cycle, a '''circuit''' or a '''closed walk'''. This ambiguity can be avoided by using the terms Eulerian trail and Eulerian circuit when self-intersection is allowed.
_[4] 웹사이트 Introduction of Graph Theory http://jwilson.coe.u[...]
_[5] 서적 Schaum's outline of theory and problems of graph theory https://books.google[...]
_[6] 논문 Bounds on the number of Eulerian orientations https://ir.cwi.nl/pu[...]
_[7] 서적 Notes on Introductory Combinatorics Birkhäuser Boston
_[8] 논문 Deux problèmes de Géométrie de situation https://books.google[...]
_[9] 논문 A note on finding the bridges of a graph
_[10] 서적 Eulerian Graphs and Related Topics: Part 1, Volume 2 https://archive.org/[...] Elsevier
_[11] 웹사이트 Note on Counting Eulerian Circuits http://www.cdam.lse.[...]
_[12] 논문 Asymptotic enumeration of eulerian circuits in the complete graph http://cs.anu.edu.au[...]
_[13] 논문 Asymptotic number of Eulerian circuits in complete bipartite graphs
_[14] 논문 An Eulerian trail approach to DNA fragment assembly
_[15] 논문 Optimum Gate Ordering of CMOS Logic Gates Using Euler Path Approach: Some Insights and Explanations
_[16] 논문 An efficient parallel biconnectivity algorithm
_[17] 논문 Finding level-ancestors in trees
_[18] 논문 A Survey of Combinatorial Gray Codes
_[19] 서적 Erdös centennial https://books.google[...] János Bolyai Math. Soc., Budapest
_[20] 서적 Modern graph theory https://books.google[...] Springer-Verlag, New York
_[21] 서적 Arc Routing: Problems, Methods, and Applications https://epubs.siam.o[...] SIAM 2022-08-19

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com