Grafens seghet
I grafteori är seghet ett mått på anslutningsmöjligheten för en graf . En graf G sägs vara t -tuff för ett givet reellt tal t om G för varje heltal k > 1 inte kan delas upp i k olika sammankopplade komponenter genom att ta bort färre än tk hörn . Till exempel är en graf 1 -tuff om antalet komponenter som bildas genom att ta bort en uppsättning hörn alltid är högst lika stort som antalet borttagna hörn. En grafs seghet är det maximala t för vilket det är t -tufft; detta är ett ändligt tal för alla finita grafer utom de fullständiga graferna , som enligt konventionen har oändlig seghet.
Grafseghet introducerades först av Václav Chvátal ( 1973 ). Sedan dess har det förekommit omfattande arbete av andra matematiker på tuffhet; den senaste undersökningen av Bauer, Broersma & Schmeichel (2006) listar 99 satser och 162 artiklar i ämnet.
Exempel
Om du tar bort k hörn från en väggraf kan den återstående grafen delas upp i så många som k + 1 anslutna komponenter. Det maximala förhållandet mellan komponenter och borttagna hörn uppnås genom att ta bort en vertex (från det inre av banan) och dela upp den i två komponenter. Därför är vägar 1 / 2 -tuffa. Om du däremot tar bort k hörn från en cykelgraf lämnar högst k kvarvarande anslutna komponenter, och ibland lämnar exakt k anslutna komponenter, så en cykel är 1 -tuff.
Anslutning till vertexanslutning
Om en graf är t -tuff, är en konsekvens (erhållen genom att sätta k = 2 ) att vilken uppsättning av 2 t − 1 noder som helst kan tas bort utan att dela grafen i två. Det vill säga, varje t -tough graf är också 2 t -vertex-ansluten .
Anslutning till Hamiltonicity
Finns det ett tal så att varje -tuff graf är Hamiltonsk?
Chvátal (1973) observerade att varje cykel , och därför varje Hamiltonsk graf , är 1 -tuff; det vill säga att vara 1 -tuff är ett nödvändigt villkor för att en graf ska vara Hamiltonsk. Han förmodade att sambandet mellan seghet och Hamiltonicitet går åt båda hållen: att det finns en tröskel t så att varje t -tuff graf är Hamiltonsk. Chvátals ursprungliga gissning att t = 2 skulle ha bevisat Fleischners teorem men motbevisades av Bauer, Broersma & Veldman (2000) . Förekomsten av en större seghetströskel för Hamiltonicitet förblir öppen, och kallas ibland Chvátals seghetsförmodan .
Beräkningskomplexitet
Att testa om en graf är 1 -tuff är co-NP -komplett. Det vill säga beslutsproblemet vars svar är "ja" för en graf som inte är 1-tuff, och "nej" för en graf som är 1-tuff, är NP-komplett . Detsamma gäller för alla fasta positiva rationella tal q : att testa om en graf är q -tuff är co-NP-komplett ( Bauer, Hakimi & Schmeichel 1990) .
Se även
- Styrka av en graf , ett analogt koncept för kantborttagningar
- Tutte–Berge formel , en relaterad karaktärisering av storleken på en maximal matchning i en graf
- 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 823 .
- Bauer, D.; Broersma, HJ; Veldman, HJ (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 uppl.), 99 (1– 3): 317-321, doi : 10.1016/S0166-218X(99)00141-9 , MR 1743840 .
- Bauer, D.; Hakimi, SL ; Schmeichel, E. (1990), "Recogniing tough graphs is NP-hard", Discrete Applied Mathematics , 28 (3): 191–195, doi : 10.1016/0166-218X(90)90001-S , MR 5 8 1074 .
- 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 .