Wytrzymałość wykresu - Graph toughness
W teorii wykres , wytrzymałość jest miarą łączności wykresu. Mówi się, że graf G jest t- twardy dla danej liczby rzeczywistej t, jeśli dla każdej liczby całkowitej k > 1 , G nie może być rozbity na k różnych połączonych składowych poprzez usunięcie mniej niż tk wierzchołków. Na przykład, graf jest 1- twardy, jeśli liczba komponentów utworzonych przez usunięcie zestawu wierzchołków jest zawsze co najwyżej równa liczbie usuniętych wierzchołków. Twardość grafu to maksymalne t, dla którego jest t -twardy; jest to liczba skończona dla wszystkich skończonych grafów z wyjątkiem grafów pełnych , które umownie mają nieskończoną wytrzymałość.
Twardość wykresu po raz pierwszy wprowadził Václav Chvátal ( 1973 ). Od tego czasu inni matematycy przeprowadzili szeroko zakrojoną pracę nad wytrzymałością; niedawne badanie Bauera, Broersmy i Schmeichela (2006) wymienia 99 twierdzeń i 162 artykuły na ten temat.
Przykłady
Usunięcie k wierzchołków z wykresu ścieżki może podzielić pozostały wykres na aż k + 1 połączonych komponentów. Maksymalny stosunek komponentów do usuniętych wierzchołków uzyskuje się poprzez usunięcie jednego wierzchołka (z wnętrza ścieżki) i podzielenie go na dwie składowe. Dlatego ścieżki są1/2-twardy. W przeciwieństwie do tego, usunięcie k wierzchołków z wykresu cyklu pozostawia co najwyżej k pozostałych połączonych składowych, a czasami pozostawia dokładnie k połączonych składowych, więc cykl jest 1- trudny.
Połączenie z połączeniem wierzchołków
Jeśli graf jest t -twardy, to jedną z konsekwencji (uzyskaną przez ustawienie k = 2 ) jest to, że dowolny zestaw 2 t − 1 węzłów można usunąć bez dzielenia grafu na dwie części. Oznacza to, że każdy t -twardy wykres jest również połączony z 2 t -wierzchołkami .
Związek z hamiltonicznością
Czy istnieje taka liczba , że każdy -twardy wykres jest hamiltonianem?
Chvátal (1973) zaobserwował, że każdy cykl , a zatem każdy wykres Hamiltona , jest 1- twardy; to znaczy, bycie 1- twardym jest warunkiem koniecznym, aby graf był hamiltonianem. Przypuszczał, że związek między twardością a hamiltonicznością jest dwukierunkowy: że istnieje próg t taki, że każdy wykres t -twardy jest hamiltonianem. Oryginalny Chvátal przypuszczenie, że T = 2 będzie okazały twierdzenie Fleischner w ale znalazł potwierdzenia Bauer Broersma i Veldman (2000) . Istnienie większego progu twardości dla Hamiltoniczności pozostaje otwarte i jest czasami nazywane przypuszczeniem twardości Chvátala .
Złożoność obliczeniowa
Testowanie, czy wykres jest 1- twardy, jest współ-NP- kompletny . To znaczy, problem decyzyjny, na który odpowiedź brzmi „tak” dla grafu, który nie jest 1-trudny, a „nie” dla grafu, który jest 1-trudny, jest NP-zupełny . To samo dotyczy każdej ustalonej dodatniej liczby wymiernej q : testowanie, czy wykres jest q- twardy, jest współ-NP-zupełny ( Bauer, Hakimi i Schmeichel 1990 ).
Zobacz też
- Siła grafu , analogiczne pojęcie dla delecji brzegowych
- Wzór Tutte-Berge , powiązana charakterystyka rozmiaru maksymalnego dopasowania na wykresie
Bibliografia
- Bauer, Douglas; Broersma, Hajo; Schmeichel, Edward (2006), "Twardość wykresów-ankieta", Wykresy i kombinatoryka , 22 (1): 1-35, doi : 10.1007/s00373-006-0649-0 , MR 2221006 , S2CID 3237188.
- Bauer, D.; Broersma, HJ; Veldman, HJ (2000), „Nie każdy 2-trudny wykres jest hamiltonianem” , Proceedings of the 5th Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1997), Discrete Applied Mathematics (wyd. 1-3), 99 (1– 3): 317–321, doi : 10.1016/S0166-218X(99)00141-9 , MR 1743840.
- Bauer, D.; Hakimi, SL ; Schmeichel, E. (1990), „Rozpoznawanie trudnych wykresów jest NP-trudne”, Discrete Applied Mathematics , 28 (3): 191-195, doi : 10.1016/0166-218X(90)90001-S , MR 1074858.
- Chvátal, Václav (1973), „Twarde wykresy i obwody Hamiltona”, Matematyka dyskretna , 5 (3): 215-228, doi : 10.1016/0012-365X (73) 90138-6 , MR 0316301.