Zúžený graf - Strangulated graph

Zúžený graf, vytvořený pomocí kliky-součty slepit dohromady a maximální rovinný graf (žlutá) a dvě chordální grafy (červená a modrá). Červený chordální graf lze zase rozložit na kliky - součty čtyř maximálních rovinných grafů (dva okraje a dva trojúhelníky).

v teoretická matematika, a zúžený graf je graf, ve kterém mazání okrajů všech indukovaný cyklus o délce větší než tři by odpojit zbývající graf. To znamená, že jsou to grafy, ve kterých každý periferní cyklus je trojúhelník.

Příklady

V maximální rovinný graf, nebo obecněji v každém polyedrický graf, periferní cykly jsou přesně plochami rovinného vložení grafu, takže polyedrický graf je škrcen tehdy a jen tehdy, jsou-li všechny plochy trojúhelníky, nebo ekvivalentně je to maximální rovinnost. Každý chordální graf je uškrceno, protože jedinými indukovanými cykly v chordálních grafech jsou trojúhelníky, takže již není možné cykly mazat.

Charakterizace

A klika-součet dvou grafů je tvořen identifikací dvou stejně velkých kliky v každém grafu a poté případně smazat některé hrany kliky. U verze klikových součtů relevantních pro zúžené grafy je krok odstranění hrany vynechán. Výsledek kliky-součtu tohoto typu mezi dvěma zúženými grafy vede k dalšímu zúženému grafu, protože každý dlouhý indukovaný cyklus v součtu musí být omezen na jednu nebo druhou stranu (jinak by to mělo akord mezi vrcholy, u kterých přešel z jednoho strana součtu na druhou) a odpojené části této strany vytvořené odstraněním cyklu musí zůstat odpojené v klikacím součtu. Každý chordální graf lze tímto způsobem rozložit na klikový součet kompletní grafy a každý maximální rovinný graf lze rozložit na klikový součet 4-vrchol připojený maximální rovinné grafy.

Tak jako Seymour & Weaver (1984) Ukaž, toto jsou jediné možné stavební kameny zúžených grafů: zúžené grafy jsou přesně grafy, které lze vytvořit jako kliky - součty úplných grafů a maximálních rovinných grafů.

Viz také

Reference

  • Seymour, P. D.; Weaver, R. W. (1984), „Zobecnění chordálních grafů“, Journal of Graph Theory, 8 (2): 241–251, doi:10,1002 / jgt.3190080206, PAN  0742878.