경로 커버

Path cover

방향 그래프 G = (V, E)가 주어진 경로 커버는 모든 꼭지점 v v V가 적어도 하나의 경로에 속하도록 유도된 경로의 집합이다.경로 커버에는 길이 0(단일 꼭지점)의 경로가 포함될 수 있다는 점에 유의하십시오.[1]

경로 커버는 정점 분리 경로 커버, 즉 모든 정점 v to V가 정확히 하나의 경로에 속하도록 일련의 경로를 참조할 수도 있다.[2]

특성.

갈라이와 밀그램에 의한 정리는 가장 작은 경로 커버의 경로 수가 가장 큰 독립 집합의 정점 수보다 클 수 없음을 보여준다.[3]특히 어떤 그래프 G의 경우 P의 각 경로에서 정확히 하나의 꼭지점을 포함하는 경로 표지 P와 독립된 집합 I이 있다.딜워스의 정리는 이 결과의 귀결로서 뒤따른다.

계산 복잡성

방향 그래프 G가 주어진 경우, 최소 경로 커버 문제는 경로가 가장 적은 G에 대한 경로 커버를 찾는 것으로 구성된다.

최소 경로 커버는 G에 해밀턴 경로가 있는 경우에만 하나의 경로로 구성된다.해밀턴 경로 문제는 NP-완전하며, 따라서 최소 경로 커버 문제는 NP-hard이다.그러나 그래프가 반복적인 경우 문제는 복잡도 등급 P에 있으므로 다항 시간 내에 일치하는 문제로 변환하여 해결할 수 있다.

적용들

최소 경로 커버의 적용은 소프트웨어 테스트를 포함한다.[4]예를 들어, 그래프 G가 컴퓨터 프로그램의 가능한 모든 실행 순서를 나타낸다면, 경로 커버는 각 프로그램 문을 최소한 한 번 이상 포함하는 일련의 테스트 실행이다.

참고 항목

메모들

  1. ^ Diestel(2005년), 섹션 2.5.
  2. ^ 프란츠블라우 & 레이쇼우드후리(2002년).
  3. ^ 다이어스텔(2005)정리 2.5.1.
  4. ^ 나토스&하키미(1979년)

참조

  • Bang-Jensen, Jørgen; Gutin, Gregory (2006), Digraphs: Theory, Algorithms and Applications (1st ed.), Springer.
  • Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer.
  • Franzblau, D. S.; Raychaudhuri, A. (2002), "Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow", ANZIAM Journal, 44 (2): 193–204, doi:10.1017/S1446181100013894.
  • Ntafos, S. C.; Hakimi, S. Louis. (1979), "On path cover problems in digraphs and applications to program testing", IEEE Transactions on Software Engineering, 5 (5): 520–529, doi:10.1109/TSE.1979.234213.