오일러 경로

그래프 이론에서 오일러 트레일(또는 오일러 경로)은 모든 가장자리를 정확히 한 번 방문하는 유한 그래프의 트레일이다(정점 재방문 허용). 마찬가지로 오일러 회로 또는 오일러 사이클은 동일한 정점에서 시작하고 끝나는 오일러 트레일이다. 이들은 1736년 쾨니히스베르크의 유명한 일곱 다리 문제를 해결하면서 레온하르트 오일러에 의해 처음 논의되었다. 이 문제는 다음과 같이 수학적으로 서술할 수 있다.

영상의 그래프를 볼 때 각 가장자리를 정확히 한 번 방문하는 경로(또는 사이클, 즉 동일한 정점에서 시작하고 끝나는 경로)를 구성할 수 있는가?

오일러는 오일러 회로의 존재에 필요한 조건이 그래프의 모든 정점이 짝수도를 갖는다는 것을 증명하고, 짝수도의 모든 정점을 가진 연결된 그래프에 오일러 회로가 있다는 증거 없이 명시했다. 이 후자의 주장에 대한 최초의 완전한 증거는 칼 히어홀저에 의해 1873년에 사후에 발표되었다.^[1] 이것을 오일러의 정리라고 한다.

연결된 그래프는 모든 꼭지점에 균등도가 있는 경우에만 오일러 사이클을 가진다.

오일러 그래프라는 용어는 그래프 이론에서 두 가지 공통된 의미를 가지고 있다. 한 가지 의미는 오일러 회로를 가진 그래프이고, 다른 하나는 모든 꼭지점이 짝수인 그래프다. 이러한 정의는 연결된 그래프에 대해 일치한다.^[2]

오일러 트레일이 존재하기 위해서는 0 또는 2개의 꼭지점이 홀수 정도를 가져야 한다. 이는 쾨니히스베르크 그래프가 오일러 트레일이 아님을 의미한다. 홀수도의 정점이 없다면 모든 오일러 트레일은 회로가 된다. 만약 오도의 정점이 정확히 두 개라면, 모든 오일러 길은 그 중 한 곳에서 시작해서 다른 곳에서 끝난다. 오일러식 자국이 있지만 오일러식 회로가 없는 그래프를 세미 오일러식이라고 한다.

정의

오일러 산책로,^[3] 또는 오일러 산책로는 각 가장자리를 정확히 한 번 사용하는 산책로다. 그러한 보행이 존재한다면 그 그래프를 가로지르거나 반을지앙이라고 한다.^[4]

비방향 그래프의 오일러 사이클,^[3] 오일러 회로 또는 오일러 투어는 각 에지를 정확히 한 번 사용하는 사이클이다. 그러한 주기가 존재할 경우 그래프를 오일러어 또는 유니쿠르어라고 한다.^[5] "Eulerian graph"라는 용어는 또한 모든 꼭지점에 고른 정도가 있는 그래프를 나타내기 위해 더 약한 의미로 사용되기도 한다. 유한 연결 그래프의 경우 두 정의는 동일하지만, 연결된 각 구성요소가 오일러 사이클을 갖는 경우에만 연결되지 않은 그래프가 약한 의미에서 오일러어일 수 있다.

지시된 그래프의 경우 "경로"는 지시된 경로로, "주기"는 지시된 사이클로 대체해야 한다.

오일러 트레일, 사이클 및 그래프의 정의와 속성은 다중 글씨도 유효하다.

비직접 그래프 G의 오일러 방향은 각 정점 v에서 v의 외측도가 v의 외측도와 같도록 G의 각 가장자리에 대한 방향을 할당하는 것이다. 이러한 방향은 모든 정점이 짝수인 비직접 그래프에 대해 존재하며, G와 th의 각 연결된 구성 요소에 오일러 투어를 구성함으로써 찾을 수 있다.투어에 따라 가장자리 방향을 ^[6]정하다 연결된 그래프의 모든 오일러 방향은 강한 방향이며, 결과 방향화된 그래프를 강하게 연결시키는 방향이다.

특성.

• 비방향 그래프는 모든 꼭지점에 균일한 정도가 있고 0도가 아닌 정점이 단일 연결된 구성요소에 속하는 경우에만 오일러 사이클을 가진다.
• 비방향 그래프는 모든 정점이 짝수도를 갖는 경우에만 에지 분리 주기로 분해할 수 있다. 따라서, 그래프는 가장자리-분해 사이클로 분해될 수 있고 0도가 아닌 정점이 단일 연결된 구성요소에 속하는 경우에만 오일러 사이클을 가진다.
• 정확히 0 또는 2개의 정점이 홀수도를 가지며 0도가 아닌 모든 정점이 단일 연결 구성요소에 속하는 경우에만 비방향 그래프에 오일러 자국이 있다.
• 방향 그래프는 모든 꼭지점이 도 및 도에서 동일하고 0도가 아닌 모든 정점이 강하게 연결된 단일 구성요소에 속하는 경우에만 오일러 사이클을 가진다. 마찬가지로 방향 그래프는 에지 분리 지시 사이클로 분해될 수 있고 0도가 아닌 모든 정점이 강하게 연결된 단일 구성요소에 속하는 경우에만 오일러 사이클을 가진다.
• 만일 최대 한개 꼭지점 −(in-degree)=1, 대부분의 한 코너의 각끝에는(in-degree)다(out-degree)을 가지고 있는 직접적인 그래프 이론의 오일러 흔적이 있−(out-degree)=1, 다른 모든 꼭지점이 동등한in-degree과out-degree고 그 vertices과 조금이라도 정도의 자리로 단일 연결된 구성 요소의 내부 지도자 없는 그래프이다.[표창 필요한]

오일러 산책로 및 회로 구축

플뢰리의 알고리즘

플뢰리의 알고리즘은 1883년까지 거슬러 올라가는 우아하지만 비효율적인 알고리즘이다.^[7] 모든 가장자리가 동일한 성분과 최대 두 개의 정점 이상에 있는 것으로 알려진 그래프를 생각해 보십시오. 알고리즘은 홀수도의 정점에서 시작하거나, 그래프가 없는 경우 임의로 선택한 정점에서 시작한다. 각 단계에서 경로의 다음 에지를 현재 정점에 남아 있는 나머지 에지를 선택하는 에지가 없는 한 삭제로 그래프를 분리하지 않는 에지로 선택한다. 그런 다음 해당 에지의 다른 끝점으로 이동하여 에지를 삭제한다. 알고리즘의 끝에는 가장자리가 남아 있지 않으며, 가장자리가 선택된 시퀀스는 그래프가 홀수도의 정점이 없으면 오일러 사이클을 형성하고, 홀수도의 정점이 정확히 두 개 있으면 오일러 트레일을 형성한다.

플뢰리 알고리즘의 그래프 통과는 가장자리 수로 선형이지만, $즉{\displaystyle }$ O (${\displaystyle E}$) ${\displaystyle O ($E $)\},$ 브리지 검출의 복잡성도 고려해야 한다. 만약 우리가 algorithm[8]모든 가장자리의 제거한 후 bridge-finding Tarjan의 선형 시간 재방송하려면, 플러리의 알고리즘. Thorup(2000년)의 동적 bridge-finding 알고리즘 이 O에 E⋅ 로그 3⁡ E⋅ 로그⁡ 로그 ⁡ 개선될 수 있도록 O(E2){O(E^{2})\displaystyle}의 시간 복잡도를 가질 것이다.${\displaystyle E}$) ${\displaystyle O(E \cdot \log ^{3}E \cdot \log \$log E )}이$($가) 있지만, 이 속도는 여전히 대체 알고리즘보다 현저히 느리다.

히에홀저 알고리즘

하이얼홀저의 1873년 논문은 플뢰리의 알고리즘보다 더 효율적인 오일러 사이클을 찾는 다른 방법을 제공한다.

• 시작 꼭지점 v를 선택하고 해당 꼭지점에서 v로 돌아갈 때까지 가장자리 흔적을 따르십시오. 모든 정점의 균일한 정도는 오솔길이 다른 정점에 진입할 때 w를 떠나는 사용되지 않은 가장자리가 있어야 함을 보장하기 때문에 v 이외의 정점에 고정되는 것은 불가능하다. 이러한 방식으로 형성된 투어는 닫힌 투어로, 초기 그래프의 정점과 가장자리를 모두 포함하지는 않을 수 있다.
• 현재 둘러보기에 속하지만 둘러보기의 일부가 아닌 인접 가장자리가 있는 꼭지점 u가 존재하는 한, 사용하지 않는 가장자리를 따라 u에서 다시 한 번 오솔길을 시작하여 u로 돌아가기 전까지 이 방법으로 형성된 둘러보기에 합류한다.
• 원래 그래프가 연결되어 있다고 가정하기 때문에 이전 단계를 반복하면 그래프의 모든 가장자리가 소진된다.

이중 링크된 목록과 같은 데이터 구조를 사용하여 각 정점에 발생하는 미사용 에지 집합을 유지하고, 미사용 에지가 있는 현재 둘러보기의 정점 목록을 유지하며, 둘러보기 자체를 유지함으로써 알고리즘의 개별 운영(각 정점 밖으로 나가는 미사용 에지 찾기, ~에 대한 새로운 시작 정점 찾기)ur, 그리고 꼭지점을 공유하는 두 개의 투어를 각각 일정한 시간에 연결할 수 있으므로 전체 알고리즘은 $O{\displaystyle }$( ${\displaystyle E}$) ${\displaystyle O$( E$)}$의 선형 시간이 걸린다$.$^[9]

이 알고리즘은 또한 디큐로 구현될 수 있다. 데크가 폐쇄된 투어를 나타낼 때만 막힐 수 있기 때문에 꼬리에서 가장자리를 떼어내고 머리에 붙이는 방식으로 데크를 회전시킨 뒤 모든 가장자리가 설명될 때까지 계속해야 한다. ${\displaystyle 또한}$ 수행된 회전 횟수가 E $displaystyle$E$}$보다 결코 크지 않기 때문에 선형적인 시간이 소요된다($$직관적으로 어떤 "나쁜" 가장자리는 머리로 이동하지만 새로운 가장자리는 꼬리에 추가됨).

오일러 회로 카운팅

복잡성 문제

digraps에 있는 오일러 회로의 수는 de Bruijn, van Aardenne-Ehrenfest, Smith, Tutte의 이름을 딴 이른바 BEST 정리를 사용하여 계산할 수 있다. 이 공식은 디그라프에 있는 오일러 회로의 수가 일정 수준의 요인 및 뿌리 수목의 수라고 명시되어 있다. 후자는 다항 시간 알고리즘을 제공하는 매트릭스 트리 정리에 의해 결정 인자로 계산될 수 있다.

BEST 정리는 우선 이 형식에서 Aardenne-Ehrenfest와 de Bruijn 종이(1951년)에 "증거에 추가된 노트"로 명시된다. 최초의 증거는 비굴적이었고 드 브루옌 시퀀스들을 일반화했다. 스미스와 투테(1941)의 초기 결과에 대한 변화다.

간접 그래프에서 오일러 회로의 수를 세는 것은 훨씬 더 어렵다. 이 문제는 #P-완전한 것으로 알려져 있다.^[10] 긍정적인 방향으로, 마르코프 체인 몬테 카를로 접근은 (안톤 코치히가 1968년에 소개한) 코치히 변환을 통해, 아직 이 사실에 대한 증거는 없지만, 그래프의 오일러 회로 수에 대한 날카로운 근사치를 제공하는 것으로 생각된다.

특례

전체 그래프에서 오일러 회로 수에 대한 점증식 공식은 McKay와 Robinson(1995)에 의해 결정되었다.^[11]

${\displaystyle \operatorname {ec}(K_{n})=2^{\frac {(n+1)}{2}}}}\pi ^{\frac{1}{2}}:{\frac{-n^{2}}+{{2}}+{\frac{11}{12}}}n^{\frac {(n-2)(n+1)}{2}{2}}{2}}}{{\bigl (}1+O(n^{-{\frac {1}{1}:{2}}+\epsilon }}{\bigr )}.}$

M.I. Isaev(2009)가 완전한 초당적 그래프에 대해 나중에 얻은 유사한 공식은 다음과 같다.^[12]

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

적용들

오일러식 자국은 생물정보학에서 그것의 파편으로부터 DNA 서열을 재구성하기 위해 사용된다.^[13] CMOS 회로 설계에서도 최적의 로직 게이트 순서를 찾기 위해 사용된다.^[14] 트리의 오일러 투어에 의존하는 트리 처리 알고리즘이 있다(각 가장자리는 호 한 쌍으로 처리된다.^[15][16] 드 브뤼옌 순서는 드 브뤼옌 그래프의 오일러 자국으로 구성될 수 있다.^[17]

무한 그래프에서

무한 그래프에서 오일러 트레일 또는 오일러 사이클에 해당하는 개념은 오일러 선으로, 그래프의 모든 가장자리를 덮는 이중 무한 트레일이다. 그래프가 연결되고 모든 정점도가 균등하다는 것은 그러한 궤적이 존재하기에 충분하지 않다. 예를 들어, 모든 정점도가 4와 같으며 표시된 무한 케이리 그래프에는 오일러 선이 없다. 오일러 선이 들어 있는 무한 그래프는 에르드, 그룬왈드 & 와이즈펠트(1936년)가 특징이었다. 무한 그래프 또는 다중 그래프 G가 오일러 선을 가지려면 다음 조건을 모두 충족해야 하고 충분하다.^[18][19]

• G가 연결되어 있다.
• G에는 정점과 가장자리가 셀 수 있는 집합이 있다.
• G는 오도의 정점이 없다.
• G에서 임의의 유한 서브그래프 S를 제거하면 나머지 그래프의 최대 두 개의 무한 연결 구성요소가 남고, S가 각각의 정점에 짝수도를 갖는 경우 S를 제거하면 정확히 하나의 무한 연결 구성요소가 남는다.

참고 항목

• 오일러어 매트로이드, 오일러 그래프의 추상 일반화
• 오방 퍼즐
• 오일러가 원본 논문에서 입증한 핸드셰이킹 보조정리(반복되지 않은 모든 그래프에 짝수 수의 홀수 정점이 있음을 나타냄
• 해밀턴 경로 – 각 꼭지점을 정확히 한 번 방문하는 경로.
• 경로 검사 문제, 모든 가장자리를 방문하는 최단 경로를 검색하십시오. 오일러 경로가 없는 경우 가장자리를 반복할 수 있음.
• 고른 정점을 가진 그래프는 연결성과 상관없이 에지-분할 사이클로 분할될 수 있다는 베블렌의 정리

메모들

참조

• Erdõs, Pál, Grünwald, Tibor, Weiszfeld, Endre(1936년),"Végtelen gráfok 오일러 vonalairól"[무한한 그래프의 오일러 라인에서는](PDF), Mat에게. 수정. Lapok(헝가리에서), 43:129–140.Erdős, P.;Grünwald, T.;Vázsonyi, E.(1938년),"Über Euler-Linien unendlicher Graphen"[무한한 그래프에 오일러 라인에서는](PDF), J. 수학으로 번역을 하다.Phys.(독일어로), 17(1–4):59–75, doi:10.1002/sapm193817159.
• 오일러, L "Solutio purmatis ad geometriam situs quiousis", Comment. 아카데미아 공상과학. I. 페트로폴리타나에 8 (1736), 128–140.
• Hierholzer, Carl (1873), "Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren", Mathematische Annalen, 6 (1): 30–32, doi:10.1007/BF01442866, S2CID 119885172.
• 루카스, E, 1921년 파리 마테마티크 4세
• 플뢰리, "Deux problemes de geometrie de president", Journal de matistics levelopers (1883), 257–261.
• T. van van Aardenne-Ehrenfest와 N. G. de Bruijn(1951) "지향적인 선형 그래프의 원과 나무", Simon Stevin 28: 203–217.
• Thorup, Mikkel (2000), "Near-optimal fully-dynamic graph connectivity", Proc. 32nd ACM Symposium on Theory of Computing, pp. 343–350, doi:10.1145/335305.335345, S2CID 128282
• W. T. Tutte와 C. A. B. 스미스(1941) "4급 네트워크의 유니쿠스 경로", 미국 수학 월간 48: 233–237.

외부 링크

위키미디어 커먼즈에는 오일러 경로와 관련된 미디어가 있다.

• 플뢰리의 알고리즘에 대한 초기 언급에 대한 논의.
• 수학 백과사전 오일러 투어.