Periferní smyčka

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 31. ledna 2022; kontroly vyžadují 4 úpravy .

Periferní cyklus v neorientovaném grafu  je cyklus , který neodděluje žádnou část grafu od jiné. Periferní cykly (nebo, jak byly poprvé nazývány, periferní polygony , jak Tutt nazval cykly " polygony "), poprvé studoval Tutt, William Thomas [1] . Periferní cykly hrají důležitou roli při popisu rovinných grafů a při vytváření cyklických prostorů neplanárních grafů [2] .

Definice

Periferní cyklus v grafu lze formálně definovat jedním z následujících způsobů:

Ekvivalenci těchto definic lze snadno vidět: souvislý podgraf grafu (spolu s hranami, které jej spojují s ) nebo tětiva cyklu, která porušuje generování cyklu, musí být v každém případě most a musí existovat také třída ekvivalence a binární relace na hranách, ve kterých jsou dvě hrany spojeny, pokud jsou konci cesty bez vnitřních vrcholů v [8]

Vlastnosti

Periferní cykly se objevují v teorii polyedrických grafů , tedy rovinných grafů spojených vrcholem-3 . Pro jakýkoli rovinný graf a jakékoli rovinné vložení musí být plochy vložení generované cykly obvodovými cykly. V polyhedrálním grafu jsou všechny plochy periferními cykly a každý periferní cyklus je plocha [9] . To znamená, že (před kombinatorickou ekvivalencí, volbou vnější plochy a orientací roviny) má každý polyedrický graf jedinečné rovinné vložení [10] .

V rovinných grafech je cyklický prostor tvořen hranami, ale v nerovinných grafech hrají periferní cykly podobnou roli - pro jakýkoli konečný graf s vrcholem-3 je cyklický prostor tvořen periferními cykly [11] . Výsledek lze rozšířit na lokálně konečné nekonečné grafy [12] . Konkrétně to znamená, že 3-spojené grafy zaručeně obsahují periferní cykly. Existují 2-spojené grafy, které neobsahují periferní cykly (příkladem je úplný bipartitní graf , ve kterém má každý cyklus dva můstky), ale pokud má 2-souvislý graf minimální stupeň tři, pak obsahuje alespoň jeden periferní cyklus [13] .

Periferní cykly ve 3-souvislých grafech lze vypočítat v lineárním čase a byly použity k vývoji testů rovinnosti [14] . Byly také rozšířeny na obecnější pojem neoddělující se expanze ucha . V některých algoritmech pro kontrolu rovinnosti grafů je užitečné najít cyklus, který není periferní, aby se problém rozdělil na menší dílčí problémy. Ve dvoupropojeném grafu s úrovní obrysu menším než tři (jako je cyklus nebo graf theta ) je každý cyklus periferií, ale každý dvoupropojený graf s úrovní obrysu tři nebo více má neperiferní cyklus, který lze nalézt v lineárním čase. [15] .

Seymour a Weaver [16] definovali stažený graf jako graf, ve kterém je každý periferní cyklus trojúhelníkem. Tyto grafy popsali jako klikové součty akordických grafů a maximálních planárních grafů [17] .

Související pojmy

Periferní cykly se také nazývaly neoddělující cykly [3] , ale tento termín je nejednoznačný, protože se používá pro dva další koncepty - pro jednoduché cykly, jejichž odstraněním se zbývající graf rozpojí [18] , a pro cykly topologických vložení grafu tak, že řezání podél cyklu nerozpojí povrch, do kterého je graf zasazen [19] .

V matroidech je neoddělující cyklus matroidní cyklus (tj. minimální závislá množina), kde odstraněním cyklu zůstane menší matroid , který je propojený (tj. který nelze rozdělit na přímý součet matroidů) [20] . Jsou podobné periferním cyklům, ale nejsou totožné ani v grafových matroidech (matroidy, ve kterých jsou cykly jednoduché cykly grafu). Například v úplném bipartitním grafu je každý cyklus periferní (má pouze jeden můstek, cestu dvou hran), ale grafová matrice tvořená tímto mostem není spojena, takže žádný cyklus matrice grafu není neoddělující.

Poznámky

  1. ↑ Tutte, 1963 .
  2. ↑ Tutte, 1963 , str. 743–767.
  3. ↑ 1 2 Di Battista, Eades, Tamassia, Tollis, 1998 , str. 74–75.
  4. ↑ Toto je definice použitá Bruhnem ( 2004 ). Brun však odlišil případ, který má izolované vrcholy od odpojení způsobeného odstraněním cyklu .
  5. ↑ Nezaměňujte s bridge , dalším stejnojmenným konceptem.
  6. ↑ Tutte, 1960 , str. 304–320.
  7. ↑ Tuto definici periferních cyklů původně používal Tutte ( Tutte 1963 ). Seymour a Weaver ( 1984 ) použili stejnou definici periferní smyčky, ale s odlišnou definicí mostu, která se více podobá definici podřízené smyčky pro periferní smyčky.
  8. ↑ Viz například věta 2.4 v Tutte ( Tutte 1960 ), která ukazuje, že množina vrcholů mostů je spojena cestami, viz Seymour a Weaver ( 1984 ) pro definování mostů pomocí tětiv a spojených komponent a viz také Di Battista, Eades, Tamassia, Tollis 1998 pro definování mostů pomocí tříd ekvivalence binární relace na hranách.
  9. ↑ Tutte, 1963 , str. Věty 2.7 a 2.8.
  10. ↑ Viz poznámky po větě 2.8 v Tutteho článku ( Tutte 1963 ). Jak poznamenává Tutt, bylo to již známo Whitney ( Whitney 1932 )
  11. ↑ Tutte, 1963 , str. Věta 2.5.
  12. ↑ Bruhn, 2004 , str. 235–256.
  13. ↑ Thomassen, Toft, 1981 , s. 199–224.
  14. ↑ Schmidt, 2014 , str. 967-978.
  15. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , str. 75–76 Lemma 3.4.
  16. ↑ Seymour, Weaver, 1984 .
  17. ↑ Seymour, Weaver, 1984 , str. 241–251.
  18. ↑ Viz například ( Borse, Waphare 2008 )
  19. ↑ Viz například ( Cabello, Mohar 2007 )
  20. ↑ Maia, Lemos, Melo, 2007 , str. 162–171.

Literatura