Apex-diagram - Apex graph

Ett toppdiagram. Den subgraf bildad genom avlägsnande av den röda toppunkten är plant .

I grafteori , en gren av matematik, är ett toppdiagram ett diagram som kan göras plant genom att ta bort ett enda toppunkt. Det raderade toppunktet kallas en topp i diagrammet. Det är en spets, inte den spetsen, eftersom en spets graf kan ha mer än en spets; till exempel, i de minimala icke-plana grafer K 5 eller K 3,3 , är varje vertex en spets. Apex-graferna innehåller grafer som själva är plana, i vilket fall varje topp är en topp. Den nollgraf räknas också som en topp graf trots att den inte har någon vertex att ta bort.

Apex-diagram stängs under operationen av att ta minderåriga och spelar en roll i flera andra aspekter av grafmorsteori: länklös inbäddning , Hadwiger's gissning , YΔY-reducerbara grafer och sambandet mellan trebredd och diagramdiameter .

Karakterisering och igenkänning

Apex-diagram stängs under användning av minderåriga : att dra ihop någon kant eller ta bort någon kant eller topp, leder till en annan toppdiagram. För, om G är ett toppdiagram med apex v , behåller varje sammandragning eller borttagning som inte involverar v planen för den återstående grafen, liksom varje kantavlägsnande av en kant som inträffar mot v . Om en kant som inträffar till v kontraheras motsvarar effekten på den återstående grafen borttagningen av den andra ändpunkten för kanten. Och om v i sig avlägsnas, kan vilken som helst toppunkt väljas som toppunkt.

Av satsen Robertson – Seymour , eftersom de bildar en mindre stängd familj av grafer, har toppdiagrammen en förbjuden grafkaraktärisering . Det finns bara ändligt många diagram som varken är apex-grafer eller har ett annat icke-apex-diagram som mindre. Dessa grafer är förbjudna minderåriga för egenskapen att vara ett toppdiagram. Någon annan graf G är en spets graf om och endast om ingen av de förbjudna minderåriga är en mindre av G . Dessa förbjudna minderåriga inkluderar de sju graferna från Petersen-familjen , tre frånkopplade grafer bildade från de ojämna fackföreningarna av två av K 5 och K 3,3 och många andra grafer. En fullständig beskrivning av dem är dock okänd.

Trots att hela uppsättningen förbjudna minderåriga förblir okända är det möjligt att testa om en given graf är ett toppdiagram, och i så fall att hitta en topp för grafen, linjärt . Mer allmänt är det för vilken som helst fast konstant k det möjligt att känna igen k -apex-graferna linjärt , graferna i vilka avlägsnandet av någon noggrant utvald uppsättning av högst k- hörn leder till en plan graf. Om k är variabel är problemet dock NP-komplett .

Kromatiskt nummer

Varje toppdiagram har högst fem kromatiska siffror: den underliggande plana grafen kräver högst fyra färger med fyrafärgssatsen , och det återstående toppunktet behöver högst en ytterligare färg. Robertson, Seymour & Thomas (1993a) använde detta faktum i sitt bevis på fallet k  = 6 i Hadwiger-antagandet , påståendet att varje 6-kromatisk graf har den fullständiga grafen K 6 som mindre: de visade att varje minimalt motexempel till antagandet måste vara ett toppdiagram, men eftersom det inte finns några 6-kromatiska toppdiagram kan ett sådant motexempel inte existera.

Olöst problem i matematik :

Är varje 6- hörnanslutet -minorfritt diagram ett toppdiagram?

(mer olösta problem i matematik)

Jørgensen (1994) antog att varje 6-vertex-ansluten graf som inte har K 6 som mindre måste vara ett toppdiagram. Om detta bevisades skulle resultatet av Robertson – Seymour – Thomas på Hadwiger-antagandet vara en omedelbar konsekvens. Jørgensens antaganden förblir obevisade. Om det är falskt har det dock bara många motexempel.

Lokal träbredd

En graffamilj F har begränsat lokal trebredd om graferna i F följer ett funktionellt förhållande mellan diameter och trebredd : det finns en funktion ƒ så att trebredden för en diameter- d- graf i F är högst ƒ ( d ). Apex-graferna har inte begränsad lokal trebredd: toppdiagrammen som bildas genom att ansluta ett toppunkt till varje toppunkt i ett n  ×  n- rutnät har trebredd n och diameter 2, så trebredden begränsas inte av en funktion av diametern för dessa grafer . Apex-grafer är emellertid nära kopplade till avgränsad lokal trebredd: de mindre stängda graffamiljerna F som har avgränsat lokal trevidd är exakt de familjer som har en toppdiagram som en av sina förbjudna minderåriga. En mindre stängd familj av grafer som har en toppdiagram som en av sina förbjudna minderåriga kallas apex-minor-fri . Med denna terminologi kan kopplingen mellan toppdiagram och lokal trebredd omställas som det faktum att apex-minor-fria graffamiljer är samma som mindre stängda graffamiljer med begränsad lokal trebredd.

Begreppet avgränsad lokal trebredd utgör grunden för teorin om tvådimensionalitet och möjliggör att många algoritmiska problem på apex-minor-fria grafer kan lösas exakt med en polynom-tidsalgoritm eller en fastparameterbar algoritm, eller approximeras med en approximationsschema för polynomtid . Apex-minor-fria graffamiljer följer en förstärkt version av grafstrukturen , vilket leder till ytterligare approximationsalgoritmer för graffärgning och det problem med resande säljare . Några av dessa resultat kan emellertid också utvidgas till godtyckliga mindre stängda graffamiljer via struktursatser som relaterar dem till apex-minor-fria grafer.

Inbäddningar

Om G är ett toppdiagram med apex v , och τ är det minsta antalet ansikten som behövs för att täcka alla grannarna till v i en plan inbäddning av G \ { v }, kan G vara inbäddad på en tvådimensionell yta av släktet τ - 1: lägg bara till det antalet broar till den plana inbäddningen och förbinder alla ansikten som v måste anslutas till. Om du till exempel lägger till ett enda toppunkt i en yttre plan graf (en graf med τ = 1) produceras en plan graf. När G \ { v } är 3-ansluten ligger hans gräns inom en konstant faktor som är optimal: varje ytbäddning av G kräver släkt åtminstone τ / 160. Det är dock NP-svårt att bestämma det optimala släktet av en ytbäddning av ett toppdiagram.

Genom att använda SPQR-träd för att koda de möjliga inbäddningarna i den plana delen av ett toppdiagram är det möjligt att beräkna en ritning av diagrammet i planet där de enda korsningarna involverar toppunktet, vilket minimerar det totala antalet korsningar, i polynom tid. Men om godtyckliga korsningar är tillåtna blir det NP-svårt att minimera antalet korsningar, även i speciella fall av toppdiagram som bildas genom att lägga till en enda kant till en plan graf.

Apex-grafer är också länklösa inbäddade i tredimensionellt utrymme: de kan bäddas in på ett sådant sätt att varje cykel i diagrammet är gränsen för en skiva som inte korsas av någon annan funktion i diagrammet. En ritning av denna typ kan erhållas genom att rita den plana delen av diagrammet i ett plan, placera spetsen ovanför planet och ansluta spetsen med raka kanter till var och en av dess grannar. Länklösa inbäddade grafer bildar en mindre sluten familj med de sju graferna i Petersen-familjen som deras minimalt förbjudna minderåriga; därför är dessa grafer också förbjudna som minderåriga för toppdiagrammen. Det finns dock länklöst inbäddade diagram som inte är toppdiagram.

YΔY-reducerbarhet

Robertsons exempel på ett icke-YΔY-reducerbart toppdiagram.

En ansluten graf är YΔY-reducerbar om den kan reduceras till ett enda toppunkt med en sekvens av steg, var och en är en A-Y- eller Y-A-transform , avlägsnande av en självslinga eller multipel adjacency, avlägsnande av ett toppunkt med en granne och ersättning av ett toppunkt av grad två och dess två angränsande kanter med en enda kant.

Liksom topparna och de länklösa inbäddade graferna stängs de YΔY-reducerbara graferna under mindreåriga. Och, som de länklösa inbäddade graferna, har de YΔY-reducerbara graferna de sju graferna i Petersen-familjen som förbjudna minderåriga, vilket frågar om dessa är de enda förbjudna minderåriga och om de YΔY-reducerbara graferna är desamma som den länklösa inbäddningsbara grafer. Neil Robertson gav dock ett exempel på ett toppdiagram som inte är YΔY-reducerbart. Eftersom varje toppdiagram är länkfritt inbäddat, visar detta att det finns diagram som är länklösa inbäddningsbara men inte YΔY-reducerbara och därför finns det ytterligare förbjudna minderåriga för YΔY-reducerbara diagram.

Robertsons toppdiagram visas i figuren. Det kan erhållas genom att ansluta ett toppunkt till vart och ett av de tre-graders hörn i en rombisk dodekaeder , eller genom att slå samman två diametralt motsatta hörn i en fyrdimensionell hyperkubgraf . Eftersom den rombiska dodecahedrons graf är plan är Robertsons graf en toppdiagram. Det är ett triangelfritt diagram med minsta grad fyra, så det kan inte ändras med någon YΔY-reduktion.

Nästan plana grafer

Den 16-toppiga Möbius-stegen , ett exempel på en nästan plan graf.

Om ett diagram är ett toppdiagram är det inte nödvändigtvis så att det har en unik topp. Till exempel, i de mindre-minimala icke-plana graferna K 5 och K 3,3 kan någon av topparna väljas som toppunkt. Wagner ( 1967 , 1970 ) definierade en nästan plan graf som en icke- plan apex-graf med den egenskapen att alla hörn kan vara toppen i diagrammet; sålunda, K 5 och K 3,3 är nästan plana. Han tillhandahöll en klassificering av dessa grafer i fyra delmängder, varav den ena består av graferna som (som Möbius-stegen ) kan inbäddas i Möbius-remsan på ett sådant sätt att remsans enda kant sammanfaller med en Hamilton-cykel av Graf. Före beviset för fyrfärgssatsen bevisade han att varje nästan plan graf kan färgas med högst fyra färger, med undantag för graferna bildade från ett hjuldiagram med en udda yttre cykel genom att ersätta navkanten med två intilliggande hörn, som kräver fem färger. Dessutom visade han att, med ett enda undantag (åtta-vertex komplementgraf av kuben ) varje nästan plana graf har en inbäddning på projektivt plan .

Uttrycket "nästan plan graf" är emellertid mycket tvetydigt: det har också använts för att hänvisa till toppdiagram, grafer bildade genom att lägga till en kant till en plan graf och grafer bildade från en plan inbäddad graf genom att ersätta ett begränsat antal ansikten med "virvlar" av begränsad banbredd , liksom för andra mindre exakt definierade uppsättningar av grafer.

Relaterade diagramklasser

En abstrakt graf sägs vara n -apex om den kan göras plan genom att radera n eller färre hörn. En 1-apex-graf sägs också vara apex.

Enligt Lipton et al. (2016) , en graf är edge-apex om det finns någon kant i diagrammet som kan raderas för att göra diagrammet plan. En graf är sammandrag-apex om det finns någon kant i diagrammet som kan kontraktas för att göra grafen plan.

Se även

Anteckningar

Referenser