Toptal

I grafteori er en toppunktsgraf en graf, der kan gøres plan ved at fjerne et toppunkt. Det fjernede toppunkt kaldes toppen af ​​grafen. Bemærk, at der kan være mere end én apex. For eksempel i en minimal ikke-plan graf K 5 eller K 3,3 er hvert toppunkt et toppunkt. Apex-grafer inkluderer oprindeligt plane grafer, hvor hvert toppunkt er et toppunkt. En nul-graf betragtes også som apikal, selvom den ikke har nogen hjørner at fjerne.

Apex-grafer lukkes under driften af ​​at generere mindreårige og spiller en stor rolle i flere andre aspekter af graf-minor-teori, herunder ulinket indlejring [1] , Hadwiger- formodningen [2] , YΔY-reducerbare grafer [3] og forholdet mellem træbredde og grafdiameter [4] [5] .

Beskrivelse og anerkendelse

Apex-grafer lukkes under driften af ​​at generere minor - krympning af enhver kant eller sletning af et toppunkt eller kant fører til en anden top-graf. Faktisk, hvis G er en toppunktsgraf med toppunkt v , så bevarer en sammentrækning eller fjernelse, der ikke påvirker toppunkt v , planariteten af ​​resten af ​​grafen (uden toppunkt v ). det samme er tilfældet, når du fjerner enhver kanthændelse med v . Hvis en kanthændelse med v er kontraheret , svarer effekten til at fjerne den modsatte ende af kanten. Hvis selve toppunktet v fjernes , kan ethvert andet toppunkt betragtes som et toppunkt [6] .

Da toppunktsgrafer lukkes ved driften af ​​at generere mindre, har de ved Robertson -Seymour-sætningen en karakterisering ved forbudte grafer . Der er kun et begrænset antal grafer, der ikke er apex-grafer, og som ikke indeholder som en mindre en anden ikke-apex-graf. Disse grafer er forbudte mindreårige for vertex-grafegenskaben. Enhver anden graf G er apex, hvis og kun hvis ingen af ​​de forbudte mindreårige er en mindre af G . Forbudte mindreårige omfatter syv grafer fra Petersen-familien , tre afbrudte grafer dannet af usammenhængende foreninger af K 5 og K 3,3 og mange andre grafer. En komplet liste over alle forbudte mindreårige er stadig ufuldstændig [6] [7] .

På trods af at den komplette liste over forbudte mindreårige ikke kendes, er det muligt i lineær tid at kontrollere, om en given graf er apex, og hvis den er, finde spidsen af ​​grafen. Mere generelt, for enhver fast konstant k , kan k -vertex-grafer (grafer, hvor sletning af et nøje udvalgt sæt, der indeholder højst k knudepunkter, fører til en plan graf [8] ) genkendes i lineær tid . Men hvis k ikke er løst, bliver problemet NP-komplet [9] .

Kromatisk tal

Enhver toppunktsgraf har et kromatisk tal , der ikke overstiger fem - en plan graf uden et toppunkt kræver højst fire farver efter firefarvesætningen , og en ekstra farve er nok til et toppunkt. Robertson, Seymour og Thomas [2] brugte denne kendsgerning til at bevise k  = 6 -tilfældet af Hadwigers formodning , påstanden om, at enhver 6-kromatisk graf har en komplet graf K 6 som minor - de viste, at ethvert minimalt modeksempel til formodningen skal være en apex-graf, men der er ingen toppunkts 6-kromatiske grafer, så der er ikke et sådant modeksempel.

Uløste problemer i matematik : Er hver vertex-6-forbundet graf uden mindre spids?

Jørgensen [10] formodede, at enhver vertex 6-forbundet graf, der ikke har K 6 som mindre , skal være apex. Hvis dette blev bevist, ville Robertson-Seymour-Thomas-resultatet for Hadwiger-formodningen være en direkte konsekvens af [2] . Jørgensens formodning er endnu ikke blevet bevist [11] . Men hvis formodningen er falsk, har den kun et begrænset antal modeksempler [12] .

Lokal træbredde

En familie af grafer F har en afgrænset lokal træbredde , hvis graferne i F overholder et funktionelt forhold mellem diameter og træbredde - der eksisterer en funktion ƒ, således at træbredden af ​​en graf i F med diameter d ikke overstiger ƒ( d ). Topgrafer har ikke en afgrænset lokal træbredde - grafen dannet ved at forbinde et toppunkt til hvert hjørne af et n  ×  n gitter har træbredde n og diameter 2, så træbredden er ikke begrænset af en funktion af diameteren af ​​disse grafer . Topgrafer er dog tæt beslægtede med grafer med begrænset lokal træbredde - mindre lukkede familier af grafer F , der har afgrænset lokal træbredde, er præcis familier, hvis forbudte mindretal er en eller anden topgraf [4] [5] . Minor-lukkede familier af grafer, der har en apex-graf som deres mindre, er kendt for at være apex minor-fri . Ifølge denne terminologi kan forholdet mellem toppunktsgrafer og lokal træbredde omformuleres som følger: familier af grafer, der er fri for vertex minor, falder sammen med familier af grafer lukket i mol med afgrænset lokal træbredde.

Begrebet afgrænset lokal træbredde danner grundlaget for teorien om todimensionalitet [ og gør det muligt at løse mange algoritmiske problemer på grafer, der er fri for top minor, nøjagtigt ved hjælp af en polynomiel tidsalgoritme eller ved hjælp af en algoritme, der kan løses med faste parametre . , eller problemet kan tilnærmes ved hjælp af et tilnærmet skema polynomisk tid [4] [13] [14] . For familier af grafer uden apikale mindreårige er en styrket version af strukturgrafsætningen opfyldt , hvilket fører til yderligere tilnærmelsesalgoritmer til graffarvning og for rejsende sælgerproblemet [15] . Nogle af disse resultater kan dog udvides til vilkårlige mol-lukkede familier af grafer ved at bruge struktursætninger til grafer forbundet med familier, der er fri for apex minor [16] .

Vedhæftede filer

Hvis en graf G er en apex-graf med apex v og er lig med det mindste antal flader, der kræves for at dække alle naboer til apex v under en plan indlejring G \{ v }, så kan G indlejres i en todimensionel slægtsoverflade ved at tilføje, at mange broer til den plane indstøbning ved at forbinde således alle flader, som v skal forbindes med. Hvis du f.eks. tilføjer et toppunkt til en ydreplanær graf (en graf med et ), produceres en plan graf. Hvis grafen G \{ v } er 3-forbundet, adskiller dens grænse sig ikke fra den optimale med mere end en konstant faktor - enhver indlejring af G i en overflade kræver mindst slægten . Problemet med at bestemme den optimale slægt for en indlejringsflade til toppunktsgrafer er imidlertid et NP-hårdt problem [17] .

Når du bruger SPQR-træer til at kode mulige indlejringer af den plane del af apex-grafen, er det muligt i polynomisk tid at beregne indlejringen af ​​grafen på et plan, hvor skæringspunkter kun er forårsaget af kanter, der udgår fra apex-vertexet, og den totale antallet af kryds er minimalt [18] . Hvis vilkårlige skæringspunkter tillades, bliver problemet med at minimere antallet af skæringspunkter NP-hårdt, selv i det specielle tilfælde af toppunktsgrafer dannet ved at tilføje en enkelt kant til en plan graf [19] .

Vertex- grafer kan indlejres uden at forbindes i tredimensionelt rum - de kan indlejres på en sådan måde, at enhver cyklus i grafen er grænsen for en disk, der ikke er gennemskåret af nogen anden del af grafen [20] . En tegning af denne type kan opnås ved at tegne den plane del af grafen på et plan, placere toppen af ​​grafen over planet og forbinde den med sine naboer med segmenter. Link-fri indlejrede grafer danner en mindre-lukket familie med syv grafer fra Petersen-familien som minimale forbudte mindreårige [1] . Derfor er disse grafer også forbudte mindreårige for vertex-grafer. Der er dog grafer, der kan integreres uden et link og ikke er apex.

YΔY-reducerbarhed

En forbundet graf er YΔY-reducerbar, hvis den kan reduceres til et enkelt toppunkt ved en sekvens af trin, som hver er en Δ-Y eller Y-Δ transformation , fjernelse af en sløjfe eller flere kanter, fjernelse af et toppunkt med en nabo, og at erstatte et toppunkt af grad to og dets to tilstødende kanter med en kant [3] .

Ligesom toppunktsgrafer og indlejrbare grafer uden links, lukkes YΔY-reducerbare grafer under drift af at generere mindreårige. Ligesom indlejrbare grafer uden kobling har YΔY-reducerbare grafer syv grafer fra Petersen-familien som minimale forbudte mindreårige, hvilket rejser spørgsmålet om, hvorvidt disse grafer er de eneste forbudte mindreårige, og om familierne af YΔY-reducerbare grafer og indlejrbare grafer uden kobling er sammenfaldende . Neil Robertson gav dog et eksempel på en apex-graf, der ikke er YΔY-reducerbar. Da enhver toppunktsgraf kan indlejres uden et link, viser dette, at der er indlejrbare grafer uden et link, som ikke er YΔY-reducerbare, og derfor er der yderligere forbudte mindre for YΔY-reducerbare grafer [3] .

Top Robertson-grafen er vist i figuren. Det kan opnås ved at forbinde spidsen med alle hjørner af grad tre rombisk dodekaeder eller ved at fusionere to modsatte hjørner af den firedimensionelle hyperkubegraf . Fordi grafen for det rombiske dodekaeder er plan, er Robertson-grafen apex. Grafen indeholder ikke trekanter og har en minimumsgrad på fire, så enhver YΔY-reduktionsoperation [ 3] kan ikke anvendes på den .

Næsten plane grafer

Hvis en graf er apex, har den ikke nødvendigvis en enkelt apex. For eksempel i minor-minimal ikke-plane grafer K 5 og K 3,3 kan et hvilket som helst toppunkt vælges som et toppunkt. Wagner [21] [22] definerede en næsten plan graf som en ikke-plan spidsgraf, hvor et hvilket som helst toppunkt kan tjene som spids. K 5 og K 3,3 er således næsten plane grafer. Han gav en klassificering af sådanne grafer og opdelte dem i fire familier. En familie består af grafer, der (ligesom Möbius-stiger ) kan indlejres i en Möbius-strimmel på en sådan måde, at kanten af ​​strimlen falder sammen med den Hamiltonske cyklus af grafen. Selv før han beviste firefarvesætningen , beviste han, at enhver næsten plan graf ikke kan farves med mere end fire farver, med undtagelse af grafer dannet af et hjul med en ulige ydre cyklus ved at erstatte det centrale toppunkt med to tilstødende hjørner - sådan en graf har brug for fem farver. Derudover beviste han, at med én undtagelse (den otte-vertex- komplement af en terning ) har enhver næsten plan graf en indlejring i det projektive plan .

Udtrykket "næsten plan graf" er dog meget tvetydig - det samme udtryk er blevet brugt for toppunktsgrafer [20] [4] , grafer dannet ved at tilføje en enkelt kant til en plan graf [23] , grafer dannet ud fra en plan indlejring af en graf ved at erstatte et begrænset antal flader "hvirvelvinde" med begrænset vejbredde [24] , såvel som nogle andre mindre strengt definerede sæt af grafer.

Noter

  1. ↑ 12 Robertson, Seymour, Thomas, 1993b .
  2. ↑ 1 2 3 Robertson, Seymour, Thomas, 1993a .
  3. ↑ 1 2 3 4 Truemper, 1992 .
  4. ↑ 1 2 3 4 Eppstein, 2000 .
  5. ↑ 1 2 Demaine, Hajiaghayi, 2004 .
  6. ↑ 1 2 Gupta, Impagliazzo, 1991 .
  7. ↑ Pierce, 2014 .
  8. ↑ Kawarabayashi, 2009 .
  9. ↑ Lewis, Yannakakis, 1980 .
  10. ↑ Jørgensen, 1994 .
  11. ↑ Jorgensens formodning , < http://www.openproblemgarden.org/op/jorgensens_conjecture > . Hentet 13. november 2016. Arkiveret 14. november 2016 på Wayback Machine . 
  12. ↑ Kawarabayashi, Norine, Thomas, Wollan, 2012 .
  13. ↑ Frick, Grohe, 2001 .
  14. ↑ Demaine, Hajiaghayi, 2005 .
  15. ↑ Demaine, Hajiaghayi, Kawarabayashi, 2009 .
  16. ↑ Grohe, 2003 .
  17. ↑ Mohar, 2001 .
  18. ↑ Chimani, Gutwenger, Mutzel, Wolf, 2009 .
  19. ↑ Cabello, Mohar, 2010 .
  20. ↑ 12 Robertson, Seymour, Thomas, 1993c .
  21. ↑ Wagner, 1967 .
  22. ↑ Wagner, 1970 .
  23. ↑ Archdeacon, Bonnington, 2004 .
  24. ↑ Abraham, Gavoille, 2006 .

Litteratur