그래프강성

Graph toughness
이 그래프에서, 네 개의 빨간색 정점을 제거하면 네 개의 연결된 구성 요소가 생성될 것이다. (네 가지 다른 색상으로 제거됨)그러나 제거가 k 성분보다 많이 남는 k 정점 집합은 없다.그러므로 그것의 강인함은 정확히 1이다.

그래프 이론에서 강인성은 그래프의 연결성을 측정하는 척도다.tk 정점 이하를 제거하여 모든 정수 k > 1에 대해 G를 k 서로 다른 연결된 구성요소로 분할할 수 없는 경우, 그래프 G는 주어진 실수 t에 대해 t-tough라고 한다.예를 들어, 정점 집합을 제거하여 형성된 성분의 수가 항상 제거된 정점의 수만큼 큰 경우 그래프는 1-tough이다.그래프의 강도는 t-tough인 최대 t이다. 이는 완전한 그래프를 제외한 모든 유한 그래프에 대한 유한한 수이며, 관례상 무한한 강인성을 가지고 있다.

그래프의 강인성은 바클라프 차바탈(1973년)에 의해 처음 소개되었다.그 이후로 강인함에 대한 다른 수학자들의 광범위한 연구가 있었다; 최근 바우어, 브로어스마 & 슈마이켈(2006)의 조사는 이 주제에 대한 99개의 이론과 162개의 논문을 열거했다.

예

경로 그래프에서 k 정점을 제거하면 나머지 그래프를 k + 1의 연결된 성분으로 분할할 수 있다.제거된 정점에 대한 구성요소의 최대 비율은 (경로 내부로부터) 하나의 꼭지점을 제거하고 두 개의 구성요소로 분할함으로써 달성된다.그러므로, 길은2분의 1이와는 대조적으로 사이클 그래프에서 k 정점을 제거하면 대부분 k개의 연결된 구성요소가 남아 있고, 때로는 정확히 k개의 연결된 구성요소를 남기므로 주기는 1-tough이다.

정점 연결

그래프가 t-tough인 경우 하나의 결과(k = 2)는 그래프를 둘로 분할하지 않고 2t - 1 노드 세트를 제거할 수 있다는 것이다.즉, 모든 t-tough 그래프는 2t-vertex 연결된다.

해밀턴시티와의 연결

수학의 미해결 문제:

모든 t -tough 그래프가 Hamiltonian이라는 숫자 이(가) 있는가?

(수학에서 더 풀리지 않은 문제)

Chvatal(1973)은 모든 사이클, 즉 모든 해밀턴 그래프는 1-tough, 즉 1-tough가 해밀턴 그래프가 되기 위해 필요한 조건이라고 관찰했다.그는 강인함과 해밀턴성의 연관성은 양방향으로 갈 것이라고 추측했다: 모든 t-tough 그래프가 해밀턴식일 정도로 문턱 t가 존재한다는 것이다.t = 2가 플라이스치너의 정리를 증명했을 것이라는 Chvátal의 원래 추측은 Bauer, Broersma & Veldman(2000년)에 의해 반증되었다.해밀턴시티에게 더 큰 강인성 문턱의 존재는 여전히 열려 있으며, 때로는 치바탈의 강인성 추측이라고 불린다.

계산 복잡성

그래프가 1-tough인지 테스트하는 것은 공동 NP 완성이다.즉, 1-tough가 아닌 그래프에 대해서는 "예"라고 답하고, 1-tough 그래프에 대해서는 "아니오"라고 답한 의사결정 문제는 NP-완전이다.어떤 고정된 양의 이성적 숫자 q: 그래프가 q-tough인지 테스트하는 것은 공동 NP-완전하다(Bauer, Hakimi & Schmeichel 1990).

참고 항목

참조

  • Bauer, Douglas; Broersma, Hajo; Schmeichel, Edward (2006), "Toughness in graphs—a survey", Graphs and Combinatorics, 22 (1): 1–35, doi:10.1007/s00373-006-0649-0, MR 2221006, S2CID 3237188.
  • Bauer, D.; Broersma, H. J.; Veldman, H. J. (2000), "Not every 2-tough graph is Hamiltonian", Proceedings of the 5th Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1997), Discrete Applied Mathematics (1-3 ed.), 99 (1–3): 317–321, doi:10.1016/S0166-218X(99)00141-9, MR 1743840.
  • Bauer, D.; Hakimi, S. L.; Schmeichel, E. (1990), "Recognizing tough graphs is NP-hard", Discrete Applied Mathematics, 28 (3): 191–195, doi:10.1016/0166-218X(90)90001-S, MR 1074858.
  • Chvátal, Václav (1973), "Tough graphs and Hamiltonian circuits", Discrete Mathematics, 5 (3): 215–228, doi:10.1016/0012-365X(73)90138-6, MR 0316301.