Počet vrcholů

V teorii grafů je vrcholový graf graf, který může být rovinný odstraněním jednoho vrcholu. Odstraněný vrchol se nazývá vrchol grafu. Všimněte si, že může existovat více než jeden vrchol. Například v minimálním nerovinném grafu K 5 nebo K 3,3 je každý vrchol vrcholem. Vrcholové grafy zahrnují zpočátku rovinné grafy, ve kterých je každý vrchol vrcholem. Nulový graf je také považován za apikální, ačkoli nemá žádné vrcholy k odstranění.

Apexové grafy jsou uzavřeny operací generování minoritních hodnot a hrají velkou roli v několika dalších aspektech teorie grafových minorit, včetně nepropojeného vkládání [1] , Hadwigerovy domněnky [2] , YΔY-redukovatelných grafů [3] a vztahu mezi šířka stromu a průměr grafu [4] [5] .

Popis a rozpoznání

Apexové grafy jsou uzavřeny operací generování minorů - zmenšení jakékoli hrany nebo odstranění vrcholu nebo hrany vede k dalšímu apex grafu. Pokud je G vrcholový graf s vrcholem v , pak kontrakce nebo odstranění, které neovlivňuje vrchol v , zachovává rovinnost zbytku grafu (bez vrcholu v ). totéž platí při odstraňování jakéhokoli incidentu hrany s v . Pokud je hrana spadající do v se stažena , účinek je ekvivalentní odstranění opačného konce hrany. Pokud je odstraněn samotný vrchol v , lze za vrchol považovat jakýkoli jiný vrchol [6] .

Vzhledem k tomu, že vrcholové grafy jsou uzavřeny operací generování minorů, mají Robertson-Seymourův teorém charakterizaci zakázanými grafy . Existuje pouze konečný počet grafů, které nejsou vrcholovými grafy a neobsahují jako menší další nevrcholový graf. Tyto grafy jsou pro vlastnost vertex graph zakázány jako vedlejší. Jakýkoli jiný graf G je vrcholem právě tehdy, když žádný ze zakázaných nezletilých není menší než G . Mezi zakázané nezletilé patří sedm grafů z Petersenovy rodiny , tři nespojené grafy vytvořené z disjunktních spojení K 5 a K 3,3 a mnoho dalších grafů. Úplný seznam všech zakázaných mladistvých zůstává neúplný [6] [7] .

Přestože není znám úplný seznam zakázaných nezletilých, je možné v lineárním čase zkontrolovat, zda je daný graf vrcholový, a pokud ano, najít vrchol grafu . Obecněji platí, že pro jakoukoli pevnou konstantu k lze v lineárním čase rozpoznat grafy k -vrcholů (grafy, ve kterých vymazání pečlivě zvolené množiny obsahující nejvýše k vrcholů vede k rovinnému grafu [8] ) . Pokud však k není pevné, problém se stává NP-úplným [9] .

Chromatické číslo

Každý vrcholový graf má chromatické číslo , které nepřesahuje pět - rovinný graf bez vrcholu vyžaduje podle čtyřbarevné věty maximálně čtyři barvy a pro vrchol stačí jedna barva navíc. Robertson, Seymour a Thomas [2] použili tuto skutečnost k prokázání případu k  = 6 Hadwigerovy domněnky , tvrzení, že každý 6-chromatický graf má úplný graf K 6 jako vedlejší – ukázali, že jakýkoli minimální protipříklad k domněnka musí být vrcholový graf, ale neexistují žádné vrcholové 6-chromatické grafy, takže žádný takový protipříklad neexistuje.

Nevyřešené problémy v matematice : Je každý vertex-6-souvislý graf bez vedlejších vrcholů ?

Jorgensen [10] se domníval, že každý vrcholový 6-souvislý graf, který nemá K 6 jako vedlejší, musí být vrcholem. Pokud by to bylo prokázáno, byl by výsledek Robertson–Seymour–Thomas pro Hadwigerovu domněnku přímým důsledkem [2] . Jorgensenova domněnka zatím nebyla prokázána [11] . Pokud je však domněnka nepravdivá, má pouze konečný počet protipříkladů [12] .

Místní šířka stromu

Rodina grafů F má omezenou místní šířku stromu , pokud se grafy v F řídí funkčním vztahem mezi průměrem a šířkou stromu — existuje funkce ƒ taková, že šířka stromu grafu v F s průměrem d nepřesahuje ƒ( d ). Vrcholové grafy nemají ohraničenou místní šířku stromu – graf vytvořený připojením vrcholu ke každému vrcholu mřížky n  ×  n má šířku stromu n a průměr 2, takže šířka stromu není omezena nějakou funkcí průměru těchto grafů . Vrcholové grafy však úzce souvisejí s grafy s ohraničenou místní šířkou stromu – vedlejší uzavřené rodiny grafů F , které mají ohraničenou místní šířku stromu, jsou přesně rodiny, jejichž zakázanými vedlejšími položkami jsou nějaký vrcholový graf [4] [5] . Minor-uzavřené rodiny grafů, které mají vrcholový graf jako jejich minor, je známo , že jsou bez apex minor . Podle této terminologie lze vztah mezi vertexovými grafy a lokální šířkou stromu přeformulovat následovně: rodiny grafů bez vertex minors se shodují s rodinami grafů uzavřených v minors s omezenou lokální šířkou stromu.

Koncept ohraničené místní šířky stromu tvoří základ teorie dvourozměrnosti a umožňuje řešit mnoho algoritmických problémů na grafech bez top minorit přesně pomocí polynomiálního časového algoritmu nebo algoritmu řešitelného s pevnými parametry , nebo lze problém aproximovat pomocí přibližného schématu polynomiálního času [4] [13] [14] . Pro rodiny grafů bez apikálních minorů je splněna posílená verze věty o strukturním grafu , což vede k dalším aproximačním algoritmům pro barvení grafů a pro problém obchodního cestujícího [15] . Některé z těchto výsledků však lze rozšířit na libovolné uzavřené rodiny grafů pomocí strukturních teorémů na grafy spojené s rodinami, které neobsahují apex minor [16] .

Přílohy

Pokud je graf G vrcholovým grafem s vrcholem v a je roven minimálnímu počtu ploch požadovaných k pokrytí všech sousedů vrcholu v pod rovinným vnořením G \{ v }, pak G lze vložit do dvourozměrného povrchu rodu přidáním mnoha mostů k rovinnému zapuštění tím, že spojí všechny plochy, ke kterým má být v připojeno. Například přidáním jednoho vrcholu do vnějšího rovinného grafu (graf s a ) vznikne rovinný graf. Pokud je graf G \{ v } 3-souvislý, neliší se jeho hranice od optimální o více než konstantní faktor — jakékoli vložení G do plochy vyžaduje rod minimálně . Problém určení optimálního rodu pro vkládací plochu pro vrcholové grafy je však NP-těžký problém [17] .

Při použití stromů SPQR pro kódování možných vnoření rovinné části vrcholového grafu je možné vypočítat v polynomiálním čase vnoření grafu do roviny, ve které jsou průniky způsobeny pouze hranami vycházejícími z vrcholového vrcholu, a celkový počet křižovatek je minimální [18] . Pokud jsou povoleny libovolné průsečíky, problém minimalizace počtu průniků se stává NP-obtížným, a to i ve speciálním případě vrcholových grafů vytvořených přidáním jedné hrany k rovinnému grafu [19] .

Vrcholové grafy jsou vnořitelné bez propojení v trojrozměrném prostoru – lze je vložit tak, že jakýkoli cyklus v grafu je hranicí disku, který není protnut žádnou jinou částí grafu [20] . Výkres tohoto typu lze získat nakreslením rovinné části grafu na rovinu, umístěním horní části grafu nad rovinu a jeho spojením se sousedy pomocí segmentů. Bezlinkové vložitelné grafy tvoří nezletilou uzavřenou rodinu se sedmi grafy z rodiny Petersenových jako minimální zakázané nezletilé [1] . Proto jsou tyto grafy zakázané i pro vrcholové grafy. Existují však grafy, které lze vložit bez odkazu a nejsou vrcholem.

YΔY-redukovatelnost

Souvislý graf je YΔY-redukovatelný, pokud jej lze redukovat na jeden vrchol sledem kroků, z nichž každý je transformací Δ-Y nebo Y-Δ , odstraněním smyčky nebo více hran, odstraněním vrcholu s jedním sousedem, a nahrazení vrcholu stupně dva a jeho dvou sousedních hran jednou hranou [3] .

Stejně jako vrcholové grafy a vnořitelné grafy bez odkazů jsou YΔY-redukovatelné grafy uzavřeny operací generování nezletilých. Stejně jako vnořitelné grafy bez propojení mají YΔY-redukovatelné grafy sedm grafů z Petersenovy rodiny jako minimální zakázané nezletilé, což vyvolává otázku, zda jsou tyto grafy jedinými zakázanými nezletilými a zda se rodiny YΔY-redukovatelných grafů a vnořitelných grafů bez propojení shodují. . Neil Robertson však uvedl příklad vrcholového grafu, který není YΔY-redukovatelný. Protože jakýkoli vrcholový graf je vnořitelný bez vazby, ukazuje to, že existují vnořitelné grafy bez vazby, které nejsou YΔY-redukovatelné, a proto jsou zde další zakázané minory pro YΔY-redukovatelné grafy [3] .

Vrcholový Robertsonův graf je znázorněn na obrázku. Lze jej získat spojením vrcholu se všemi vrcholy třetího stupně kosočtvercového dvanáctistěnu nebo sloučením dvou protilehlých vrcholů čtyřrozměrného grafu hyperkrychle . Protože graf kosočtvercového dvanáctistěnu je rovinný, Robertsonův graf je vrcholový. Graf neobsahuje trojúhelníky a má minimální stupeň čtyři, takže na něj nelze použít žádnou operaci redukce YΔY [3] .

Téměř rovinné grafy

Pokud je graf vrcholový, nemusí mít nutně jeden vrchol. Například v vedlejších-minimálních nerovinných grafech K 5 a K 3,3 může být jako vrchol vybrán jakýkoli vrchol. Wagner [21] [22] definoval téměř rovinný graf jako nerovinný vrcholový graf, ve kterém může jako vrchol sloužit jakýkoli vrchol. K 5 a K 3,3 jsou tedy téměř rovinné grafy. Uvedl klasifikaci takových grafů a rozdělil je do čtyř rodin. Jedna rodina se skládá z grafů, které (jako Möbiovy žebříky ) lze vložit do Möbiova pásu takovým způsobem, že okraj pásu se shoduje s Hamiltonovým cyklem grafu. Ještě předtím, než dokázal větu o čtyřech barvách , dokázal, že každý téměř rovinný graf lze obarvit nejvýše čtyřmi barvami, s výjimkou grafů vytvořených z kola s lichým vnějším cyklem nahrazením centrálního vrcholu dvěma sousedními vrcholy - takový graf potřebuje pět barev. Navíc dokázal, že až na jednu výjimku (osmivrcholový doplněk krychle ) má každý téměř rovinný graf vložení do projektivní roviny .

Výraz „téměř rovinný graf“ je však značně nejednoznačný – stejný termín byl použit pro vrcholové grafy [20] [4] , grafy vytvořené přidáním jedné hrany k rovinnému grafu [23] , grafy vytvořené z rovinného vnoření grafu nahrazením omezeného počtu "vírů" ploch s omezenou šířkou cesty [24] , stejně jako některé další méně přísně definované sady grafů.

Poznámky

  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. ↑ Jorgensen's Conjecture , < http://www.openproblemgarden.org/op/jorgensens_conjecture > . Získáno 13. listopadu 2016. Archivováno 14. listopadu 2016 na 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. ↑ Arciděkan, Bonnington, 2004 .
  24. ↑ Abraham, Gavoille, 2006 .

Literatura