사이클(그래프 이론)

Cycle (graph theory)
녹색으로 표시된 닫힌 보행 H–A–B–H, 파란색으로 모든 가장자리가 구별되는 닫힌 보행 회로, 빨간색으로 모든 정점이 구별되지만 H–D–H의 첫 번째와 마지막 정점이 구별되는 닫힌 보행 사이클을 나타내는 에지가 있는 그래프.

그래프 이론에서, 그래프의 순환은 첫 번째 정점과 마지막 정점만 동일한 비어 있지 않은 궤적입니다.방향 그래프의 방향 주기는 첫 번째 정점과 마지막 정점만 동일한 비어 있지 않은 방향 추적입니다.

순환이 없는 그래프를 비순환 그래프라고 합니다.유향 사이클이 없는 유향 그래프를 유향 비순환 그래프라고 합니다.주기가 없는 연결된 그래프를 트리라고 합니다.

정의들

회로 및 사이클

  • 회로는 첫 번째 정점과 마지막 정점이 동일한 비어 있지 않은 트레일입니다(닫힌 트레일).[1]
G = (V, E, θ)를 그래프로 한다.회로는 정점 시퀀스(v1, v2, …, vn, vn, v1)를 가진 비어 있지 않은 트레일(e1, e2, …, e)입니다.
  • 사이클 또는 단순 회로는 첫 번째 정점과 마지막 정점만 [1]동일한 회로입니다.

유도 회로 및 유도 사이클

  • 유향회로는 첫 번째 정점과 마지막 정점이 동일한 비어 있지 않은 유향트레일(닫힌 유향트레일)[1]입니다.
G = (V, E, θ)를 지향 그래프로 한다.유향회로는 정점 시퀀스(v1, v2, …, vnn, v1)를 가진 비어 있지 않은 유향트레일(e1, e2, …, e)이다.
  • 다이렉트 사이클 또는 단순 다이렉트 회로는 첫 번째 정점과 마지막 정점만 [1]동일한 다이렉트 회로입니다.

무현 사이클

이 그래프에서 녹색 주기 A-B-C-D-E-F-A는 무현인 반면 빨간색 주기 G-H-I-J-K-L-G는 무현이다.모서리 {K, I}이(가) 코드이기 때문입니다.

홀 또는 유도 사이클이라고도 하는 그래프의 코드리스 사이클은 사이클의 두 정점이 사이클에 속하지 않는 에지로 연결되어 있지 않은 사이클입니다.안티 홀은 그래프 홀의 보완체입니다.코드리스 사이클은 완전한 그래프를 특징짓기 위해 사용될 수 있다: 강력한 완전 그래프 정리에 따르면, 그래프는 홀수 개수의 정점이 3개보다 크지 않은 경우에만 완벽하다.완전 그래프의 특별한 유형인 현 그래프에는 세 개보다 큰 크기의 구멍이 없습니다.

그래프의 둘레는 최단 주기의 길이이며, 이 주기는 반드시 코드리스입니다.케이지(cage)는 주어진 정도와 둘레의 조합을 가진 가장 작은 정규 그래프로 정의된다.

페리페럴 사이클은 사이클에 포함되지 않은 두 개의 에지가 내부 정점이 사이클을 회피하는 경로에 의해 연결될 수 있는 특성을 가진 그래프 내의 사이클입니다.주기에 한 엣지를 더해서 형성되지 않은 그래프에서 주변주기는 유도주기로 해야 한다.

사이클 스페이스

주기라는 용어는 그래프의 주기 공간의 요소를 나타낼 수도 있습니다.각 계수 필드 또는 링에 대해 하나씩 많은 사이클 공간이 있습니다.가장 일반적인 것은 바이너리 사이클 공간(일반적으로 단순히 사이클 공간이라고 함)으로, 모든 정점에 균등도가 있는 에지 집합으로 구성됩니다. 이 공간은 2-요소 필드 위에 벡터 공간을 형성합니다.베블렌의 정리에 따르면 사이클 공간의 모든 원소는 단순한 사이클의 에지-분리 결합으로 형성될 수 있다.그래프의 사이클 베이스는 사이클 [2]공간의 기초를 형성하는 단순한 사이클 세트입니다.

대수적 위상으로부터의 아이디어를 사용하여, 2진수 주기 공간은 정수, 유리 또는 실수 등과 [3]같은 다른 고리 위의 공간이나 모듈로 일반화된다.

사이클 검출

방향 및 무방향 그래프에서 주기의 존재 여부는 깊이 우선 검색(DFS)이 현재 정점의 상위([4]뒷면 가장자리 포함)를 가리키는 가장자리를 찾는지 여부에 따라 확인할 수 있습니다.DFS가 건너뛰는 모든 후면 가장자리는 [5]사이클의 일부입니다.무방향 그래프에서 노드의 부모에 대한 에지는 백에지로 카운트되지 않아야 하지만 이미 방문한 다른 정점을 찾으면 백에지가 표시됩니다.무방향 그래프의 경우, 최대 n - 1 에지가 트리 에지가 될 수 있기 때문에 n-vertex 그래프에서 사이클을 찾는 데 필요한 시간은 O(n) 시간뿐입니다.

많은 위상 정렬 알고리즘도 사이클을 검출합니다.이는 위상 순서가 존재하는 데 장애가 되기 때문입니다.또한 방향 그래프가 강하게 연결된 구성요소로 분할된 경우, 사이클은 강하게 [5]연결되기 때문에 구성요소 내부에만 존재하고 구성요소 간에는 존재하지 않습니다.

방향 그래프의 경우 분산 메시지 기반 알고리즘을 사용할 수 있습니다.이러한 알고리즘은 사이클의 정점에 의해 송신된 메시지가 그 자체로 돌아온다는 생각에 의존합니다.분산 사이클 검출 알고리즘은 컴퓨터 클러스터(또는 슈퍼컴퓨터)에서 분산 그래프 처리 시스템을 사용하여 대규모 그래프를 처리하는 데 유용합니다.

사이클 검출의 응용 프로그램에는 동시 시스템의 [6]교착 상태를 검출하기 위해 대기 그래프를 사용하는 것이 포함됩니다.

알고리즘.

모든 정점에 대해: 방문한(v) = 거짓, 완료된(v) = 거짓 모든 정점에 대해: DFS(v)
DFS(v): 완료된 경우(v) 방문한 경우 반환(v) "주기가 발견됨" 및 반환된 경우 반환(v) = 완료된 모든 인접 DFS(w)에 대해 true = true

Neighbor는 DFS(v)라고 불리는 정점을 제외하고 v에 연결된 모든 정점을 의미합니다.이렇게 하면 알고리즘이 최소 1개의 에지를 가진 모든 무방향 그래프에서 발생하는 사소한 사이클도 캐치되지 않습니다.

프로그래밍

다음 프로그래밍 언어 C#의 예는 인접 목록을 사용한 무방향 그래프의 1가지 구현을 나타내고 있습니다.비방향 그래프는 Undirected Graph 클래스로 선언됩니다.프로그램을 실행할 때는 메인 메서드를 사용합니다.메인 메서드가 있는 경우 콘솔로 가장 [7]짧은 간단한 사이클을 출력합니다.

사용. 시스템.; 사용. System.Collections.포괄적인;  // 그래프의 정점에 대한 클래스를 선언합니다. 학급 노드 {  일반의 인트 색인;  일반의 스트링 가치;  일반의 해시 세트< >노드> 인접 노드 = 신규 해시 세트< >노드> ( ) ; // 인접 정점 집합 }  // 무방향 그래프의 클래스를 선언합니다. 학급 무방향 그래프 {  일반의 해시 세트< >노드> 노드 = 신규 해시 세트< >노드> ( ) ;    // 이 메서드는 node1과 node2를 서로 연결합니다.  일반의 무효 접속 노드(노드 노드 1, 노드 노드2)  {   노드 1.인접 노드.더하다(노드2);   노드2.인접 노드.더하다(노드 1);  } }  학급 프로그램. {  // 이 메서드는 A, B, C, ... 형식의 사이클을 텍스트로 반환합니다.  일반의 정적인 스트링 ToString(ToString)(목록.< >노드> 사이클)  {   스트링 본문 = "";   위해서 (인트 i = 0; i < > 사이클.세어보세요; i++) // for-loop, 정점 반복   {    본문 += 사이클[i].가치 + ", ";   }   본문 = 본문.서브스트링(0, 본문.길이 - 2);   돌아가다 본문;  }    // 프로그램을 실행하는 주요 방법  일반의 정적인 무효 주된(스트링[] args)  {   // 5개의 정점을 선언 및 초기화합니다.   노드 노드 1 = 신규 노드{색인 = 0, 가치 = "A"};   노드 노드2 = 신규 노드{색인 = 1, 가치 = 'B'};   노드 노드 3 = 신규 노드{색인 = 2, 가치 = 'C'};   노드 노드 4 = 신규 노드{색인 = 3, 가치 = 'D'};   // 정점을 유지하는 배열을 선언 및 초기화합니다.   노드[] 노드 = {노드 1, 노드2, 노드 3, 노드 4};   // 무방향 그래프를 만듭니다.   무방향 그래프 무방향 그래프 = 신규 무방향 그래프();   인트 number Of Nodes = 노드.길이;   위해서 (인트 i = 0; i < > number Of Nodes; i++) // for-loop, 모든 정점 반복   {    무방향 그래프.노드.더하다(노드[i]); // 그래프에 정점을 추가합니다.   }   // 그래프의 정점을 서로 연결합니다.   무방향 그래프.접속 노드(노드 1, 노드 1);   무방향 그래프.접속 노드(노드 1, 노드2);   무방향 그래프.접속 노드(노드2, 노드 3);   무방향 그래프.접속 노드(노드 3, 노드 1);   무방향 그래프.접속 노드(노드 3, 노드 4);   무방향 그래프.접속 노드(노드 4, 노드 1);      해시 세트< >노드> 새로운 노드 = 신규 해시 세트< >노드>(노드); // 반복할 새 정점 집합   해시 세트< >목록.< >노드>> 패스 = 신규 해시 세트< >목록.< >노드>>( ) ; // 전류 경로 집합   위해서 (인트 i = 0; i < > number Of Nodes; i++) // for-loop, 그래프의 모든 정점을 반복합니다.   {    노드 노드 = 노드[i];    새로운 노드.더하다(노드); // 반복할 새 정점 집합에 정점 추가    목록.< >노드> 경로. = 신규 목록.< >노드> ( ) ;    경로..더하다(노드);    패스.더하다(경로.); // 각 노드의 경로를 시작 정점으로 추가합니다.   }   해시 세트< >목록.< >노드>> 최단 사이클 = 신규 해시 세트< >목록.< >노드>>( ) ; // 최단 사이클 세트   인트 length Of Cycles(주기 길이) = 0; // 최단 사이클 길이   부울 cyclesAreFound(검색 완료) = 거짓의; // 사이클이 발견되었는지 여부   하는 동안에 (!cyclesAreFound(검색 완료) & & 새로운 노드.세어보세요 > 0) // 반복할 정점이 있는 한   {    새로운 노드.분명한(); // 반복할 노드 집합을 비웁니다.    해시 세트< >목록.< >노드>> newPaths(New Paths) = 신규 해시 세트< >목록.< >노드>>( ) ; // 새로 찾은 경로 집합    앞지르다 (목록.< >노드> 경로. 에 패스) // foreach-loop, 모든 현재 경로 반복    {     노드 라스트 노드 = 경로.[경로..세어보세요 - 1];     새로운 노드.더하다(라스트 노드); // 반복할 정점 목록에 경로의 마지막 정점을 추가합니다.     앞지르다 (노드 다음 노드 에 라스트 노드.인접 노드) // 이전 노드의 모든 네이버를 반복하는 foreach-loop     {      한다면 (경로..세어보세요 >= 3 & & 경로.[0] == 다음 노드) // 길이가 3 이상인 사이클이 발견된 경우      {       cyclesAreFound(검색 완료) = 진실의;       최단 사이클.더하다(경로.); // 사이클 세트에 경로를 추가합니다.       length Of Cycles(주기 길이) = 경로..세어보세요;      }      한다면 (!경로..포함하다(다음 노드)) // 경로에 인접 라우터가 포함되지 않은 경우      {       새로운 노드.더하다(다음 노드); // 반복할 정점 집합에 인접 라우터를 추가합니다.       // 새 경로를 만듭니다.       목록.< >노드> new Path(신규 경로) = 신규 목록.< >노드> ( ) ;       new Path(신규 경로).추가 범위(경로.); // 현재 경로의 정점을 올바른 순서로 새 경로에 추가합니다.       new Path(신규 경로).더하다(다음 노드); // 새 경로에 인접 라우터를 추가합니다.       newPaths(New Paths).더하다(new Path(신규 경로)); // 새로 찾은 경로 집합에 경로를 추가합니다.      }     }    }    패스 = newPaths(New Paths); // 현재 경로 집합을 업데이트합니다.   }   한다면 (최단 사이클.세어보세요 > 0) // 사이클이 발견된 경우   {    콘솔.기입선("그래프는 다음을 포함합니다." + 최단 사이클.세어보세요 + "길이의 주기" + length Of Cycles(주기 길이) + "."); // 콘솔에 인쇄    앞지르다 (목록.< >노드> 사이클 에 최단 사이클) // foreach-loop, 발견된 모든 사이클 반복    {     콘솔.기입선(ToString(ToString)(사이클)); // 콘솔에 인쇄    }   }   또 다른   {    콘솔.기입선("그래프에 주기가 없습니다."); // 콘솔에 인쇄   }      콘솔.라인 읽기();  } }

사이클별 그래프 커버

레온하르트 오일러는 그래프 이론의 탄생으로 널리 여겨지는 쾨니히스베르크의 7개의 다리에 대한 그의 1736년 논문에서 유한 무방향 그래프가 각 모서리를 정확히 한 번 방문하는 닫힌 걷기를 가지기 위해서는 고립된 꼭지점(모든 모서리)을 제외하고 연결되어야 하고 충분하다는 것을 증명했다.하나의 성분)에 포함되며 각 정점에 균일한 도를 가진다.방향 그래프에서 각 모서리를 정확히 한 번 방문하는 닫힌 보행의 존재에 대한 해당 특성은 그래프가 강하게 연결되어 있고 각 정점에 들어오는 모서리와 나가는 모서리의 수가 동일하다는 것이다.두 경우 모두, 결과 폐쇄 트레일은 오일러 트레일로 알려져 있다.유한한 무방향 그래프가 각각의 정점에 균등도를 갖는다면, 그것이 연결되어 있는지 여부에 관계없이, 각 모서리를 정확히 한 번 커버하는 일련의 단순한 사이클을 찾을 수 있습니다. 이것이 베블렌의 [8]정리입니다.연결된 그래프가 오일러 정리의 조건을 충족하지 못할 경우, 그럼에도 불구하고 경로 검사 문제를 해결함으로써 각 모서리를 최소 한 번 포함하는 최소 길이의 폐쇄 보행을 다항 시간에 찾을 수 있습니다.

모서리를 덮는 대신 각 정점을 정확히 한 번 덮는 단일 단순 주기를 찾는 문제는 훨씬 더 어렵습니다.이러한 사이클을 해밀턴 사이클이라고 하며, 존재 여부를 판단하는 것은 NP-완전입니다.[9]해밀턴 순환을 포함할 수 있는 그래프의 클래스에 관한 많은 연구가 발표되었습니다. 하나의 예는 모든 인접하지 않은 정점 쌍이 적어도 그래프에서 [10]정점 수의 합을 갖는 그래프에서 항상 해밀턴 순환을 찾을 수 있다는 오레의 정리입니다.

사이클 이중 커버 추측은 모든 브리지리스 그래프에 대해 그래프의 각 가장자리를 정확히 두 번 커버하는 단순한 사이클의 멀티셋이 존재함을 나타냅니다.이것이 사실임을 증명하는 것(또는 반례를 찾는 것)은 여전히 [11]미해결 문제로 남아 있다.

주기별로 정의된 그래프 클래스

그래프에는 몇 가지 중요한 클래스가 주기에 의해 정의되거나 주기에 의해 특징지어질 수 있습니다.여기에는 다음이 포함됩니다.

  • 이분 그래프, 홀수 주기가 없는 그래프(홀수 수의 정점이 있는 주기)
  • 선인장 그래프, 모든 불요불급한 쌍접합 성분이 주기인 그래프
  • 사이클 그래프, 단일 사이클로 구성된 그래프
  • 모든 유도 주기가 삼각형인 그래프인 현상 그래프
  • 방향 비순환 그래프, 방향 주기가 없는 방향 그래프
  • 모든 홀수 주기가 삼각형인 그래프인 선 완전 그래프
  • 완전 그래프, 유도 주기가 없는 그래프 또는 홀수 길이가 3보다 큰 그래프
  • 의사 포레스트(Pseudo Forest)는 연결된 각 구성요소가 최대 한 사이클을 갖는 그래프입니다.
  • 모든 주변 사이클이 삼각형인 그래프인 교살 그래프
  • 강하게 연결된 그래프, 모든 가장자리가 주기의 일부인 방향 그래프
  • 삼각형이 없는 그래프, 세 개의 수직 주기가 없는 그래프

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b c d 벤더&윌리엄슨 2010, 페이지 164.
  2. ^ 를 클릭합니다Gross, Jonathan L.; Yellen, Jay (2005), "4.6 Graphs and Vector Spaces", Graph Theory and Its Applications (2nd ed.), CRC Press, pp. 197–207, ISBN 9781584885054.
  3. ^ 를 클릭합니다Diestel, Reinhard (2012), "1.9 Some linear algebra", Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer, pp. 23–28.
  4. ^ Tucker, Alan (2006). "Chapter 2: Covering Circuits and Graph Colorings". Applied Combinatorics (5th ed.). Hoboken: John Wiley & sons. p. 49. ISBN 978-0-471-73507-6.
  5. ^ a b Sedgewick, Robert (1983), "Graph algorithms", Algorithms, Addison–Wesley, ISBN 0-201-06672-6
  6. ^ Silberschatz, Abraham; Peter Galvin; Greg Gagne (2003). Operating System Concepts. John Wiley & Sons, INC. pp. 260. ISBN 0-471-25060-0.
  7. ^ GeeksforGeeks: 무방향 무가중 그래프의 최단 주기
  8. ^ 를 클릭합니다Veblen, Oswald (1912), "An Application of Modular Equations in Analysis Situs", Annals of Mathematics, Second Series, 14 (1): 86–94, doi:10.2307/1967604, JSTOR 1967604.
  9. ^ 를 클릭합니다Richard M. Karp (1972), "Reducibility Among Combinatorial Problems" (PDF), in R. E. Miller and J. W. Thatcher (ed.), Complexity of Computer Computations, New York: Plenum, pp. 85–103.
  10. ^ 를 클릭합니다Ore, Ø. (1960), "Note on Hamilton circuits", American Mathematical Monthly, 67 (1): 55, doi:10.2307/2308928, JSTOR 2308928.
  11. ^ 를 클릭합니다Jaeger, F. (1985), "A survey of the cycle double cover conjecture", Annals of Discrete Mathematics 27 – Cycles in Graphs, North-Holland Mathematics Studies, vol. 27, pp. 1–12, doi:10.1016/S0304-0208(08)72993-1.