유도경로

Induced path
큐브에 있는 길이 4의 유도 경로.하이퍼큐브에서 가장 오래 유도된 경로를 찾는 것은 뱀-인-더-박스 문제로 알려져 있다.

그래프 이론의 수학적 영역에서, 비방향 그래프 G의 유도 경로는 G의 유도 하위 그래프인 경로다.즉, 시퀀스의 각 인접 정점 두 개가 G의 에지로 연결되고, 시퀀스의 각 비인접 정점 두 개가 G의 어떤 에지로 연결되지 않는 G의 정점 시퀀스다.유도된 경로를 뱀이라고 부르기도 하며, 하이퍼큐브 그래프에서 긴 유도 경로를 찾는 문제를 뱀-인-더-박스 문제로 알려져 있다.

마찬가지로 유도 사이클은 G의 유도 서브그래프인 사이클이다. 유도 사이클은 코드리스 사이클 또는 (주기의 길이가 4 이상일 때) 홀이라고도 한다.안티홀은 G의 보완에 있는 구멍이다. 즉, 안티홀은 구멍의 보완물이다.

그래프에서 가장 긴 유도 경로의 길이를 그래프의 우회 번호라고 부르기도 했다.[1] 희소성 그래프의 경우, 우회 번호를 갖는 것은 경계 트리 깊이를 갖는 것과 같다.[2]그래프 G의 유도 경로 번호는 그래프의 정점이 분할될 수 있는 유도 경로의 최소 수이며,[3] 밀접한 관련이 있는 G의 유도 경로 커버 번호는 G의 모든 정점을 함께 포함하는 유도 경로의 최소 수이다.[4]그래프의 둘레는 최단 주기의 길이지만, 이 주기는 짧은 주기의 생성에 어떤 화음을 사용할 수 있기 때문에 유도 주기가 되어야 한다. 유사한 이유로 그래프의 홀수 둘레는 최단 홀수 유도 주기의 길이이기도 하다.

예

1에서 4까지의 치수 n에 대한 즉시 뱀(Ls) 및 코일(Lc) 최대 길이

그림에는 큐브, 8개의 정점과 12개의 가장자리가 있는 그래프, 그리고 4개의 길이로 유도된 경로를 이 그래프에서 보여준다.간단한 사례 분석을 통해 큐브에는 길이 6의 유도 주기가 있지만 더 이상 유도 경로가 있을 수 없다는 것을 알 수 있다.코우츠(1958)가 처음 제기하는 하이퍼큐브에서 가장 오래 유도된 경로나 사이클을 찾는 문제는 뱀-인-더-박스 문제로 알려져 있으며, 코딩 이론과 공학에 응용되어 광범위하게 연구되어 왔다.

그래프 패밀리의 특성화

많은 중요한 그래프 패밀리는 패밀리에 있는 그래프의 유도 경로나 사이클 측면에서 특징지어질 수 있다.

  • 사소한 것은 2길이의 유도 경로가 없는 연결된 그래프가 완전한 그래프, 유도 사이클이 없는 연결된 그래프가 나무라는 것이다.
  • 삼각형이 없는 그래프는 길이 3의 유도 주기가 없는 그래프다.
  • cographs는 정확히 길이 3의 유도 경로가 없는 그래프다.
  • 코드 그래프는 길이 4 이상의 유도 주기가 없는 그래프다.
  • 짝수 구멍 없는 그래프는 정점 수가 짝수인 유도 사이클을 포함하지 않는 그래프다.
  • 소소하게 완벽한 그래프는 길이 3의 유도 경로도 길이 4의 유도 사이클도 없는 그래프다.
  • 강력하고 완벽한 그래프 정리에 의해 완벽한 그래프는 홀수 구멍이 없고 홀수 안티홀이 없는 그래프다.
  • 거리-연속 그래프는 모든 유도 경로가 최단 경로인 그래프로, 동일한 두 꼭지점 사이의 유도 경로마다 길이가 같은 그래프다.
  • 블록 그래프는 두 꼭지점 사이에 최대 하나의 유도 경로가 있는 그래프이고, 연결된 블록 그래프는 두 꼭지점 사이에 정확히 하나의 유도 경로가 있는 그래프다.

알고리즘 및 복잡성

그래프 G와 파라미터 k에 대해 그래프에 최소 k의 유도 경로가 있는지 여부를 결정하는 것은 NP 완성이다.개리 앤 존슨(1979)은 이 결과를 미할리스 얀나카키스의 미공개 의사소통 탓으로 돌렸다.그러나 소행성-삼중 자유 그래프나[5] 긴 구멍이 없는 그래프 등 특정 그래프 계열의 경우 다항식 시간에 이 문제를 해결할 수 있다.[6]

그래프의 정점을 두 개의 유도 경로로 분할할 수 있는지 또는 두 개의 유도 사이클로 분할할 수 있는지를 결정하는 것도 NP-완전이다.[7]그 결과, 그래프의 유도 경로 번호를 결정하는 것은 NP-hard이다.

가장 긴 유도 경로 또는 주기 문제를 대략적으로 추정하는 복잡성은 그래프에서 큰 독립 집합을 찾는 복잡성과 관련될 수 있다.[8]정점이 없는 그래프 G에서 G의 각 정점 쌍에 하나씩 각각 두 개의 이웃이 있는 G n(n - 1)/2 정점에 추가하여 G의 두 배 정점 수를 갖는 다른 그래프 H를 형성하십시오.G가 k 크기의 독립된 세트를 가지고 있는 경우, H는 반드시 유도 경로와 길이 2k의 유도 사이클을 가져야 하며, G에서 독립된 세트의 정점과 I의 정점을 교대로 형성해야 한다.반대로, H가 유도 경로나 길이 k의 주기를 갖는 경우, 이 경로나 주기로부터 G에 있는 비인접 정점의 최대 집합은 적어도 k/3 크기의 G에 독립된 집합을 형성한다.따라서 G에서 최대 독립형 집합의 크기는 H에서 가장 긴 유도 경로와 가장 긴 유도 사이클의 크기의 일정한 요인 내에 있다.따라서, Hstadstad(1996)의 결과에 의해, NP=ZPP가 아닌 한, 최적 용액의 O(n1/2-ε) 인자 내에서 가장 긴 유도 경로 또는 가장 긴 유도 사이클을 근사하게 하기 위한 다항 시간 알고리즘이 존재하지 않는다.

정점과 m 가장자리가 있는 그래프에서 구멍(그리고 코드 없는 길이 5의 사이클이 없는 그래프에서의 안티홀)은 시간(n+m2) 내에 검출될 수 있다.[9]

원자 사이클

원자 사이클은 n-chords를 포함하지 않는 무현상 사이클의 일반화다.n-chord는 어떤 사이클에서 두 지점을 연결하는 길이 n의 경로로 정의되며, 여기서 n은 해당 포인트를 연결하는 사이클에서 가장 짧은 경로의 길이보다 작다.사이클에 n-chords가 없으면 더 작은 사이클로 분해할 수 없기 때문에 이를 원자 사이클이라고 한다.[10]최악의 경우, 그래프의 원자 주기는 O(m2) 시간으로 열거될 수 있으며, 여기서 m은 그래프에서 가장자리 수입니다.

메모들

  1. ^ 버클리&하라리(1988년).
  2. ^ 네셰틸 & 오소나 데 멘데스(2012), 발의안 6.4, 페이지 122.
  3. ^ 샤르트랑 외 연구진(1994)
  4. ^ 바리올리, 팔랏 & 호그벤(2004년).
  5. ^ 크래치, 뮐러 & 토딘카(2003년).
  6. ^ 가브릴(2002년).
  7. ^ 르, 르앤 뮐러(2003년).
  8. ^ Berman & Schnitger (1992년).
  9. ^ 니콜로풀로스 & 팔리오스 (2004)
  10. ^ 가슐러 & 마르티네스(2012년).

참조