Částka za kliknutí

Sum by clique  je graf-teoretická operace, která poskytuje kombinaci dvou grafů jejich slepením klikou , podobně jako spojený součet v topologii . Jestliže dva grafy a obsahují kliky stejné velikosti, klikový součet se vytvoří z nesouvisejícího spojení grafů identifikací párů vrcholů z klik tak, aby vytvořily jednu kliku, a poté odstraněním některých hran [1] . Součet za proklik je součet za proklik, který neobsahuje více než vrcholy. Opakováním operace součtu je možné vytvořit součet po kliknutí a součet po kliknutí z více než dvou grafů.

Související pojmy

Součty kliknutí mají úzký vztah s šířkou stromu  – pokud dva grafy mají šířku stromu menší nebo rovnou , pak y- součet kliknutí bude mít stejnou vlastnost. Každý strom je součtem jeho hran na 1 kliknutí. Jakýkoli paralelně sériový graf nebo obecněji jakýkoli graf se šířkou stromu nepřesahující dvě, lze sestavit jako součet za 2 kliknutí trojúhelníků. Stejný výsledek zobecňuje na velké  — každý graf se šířkou stromu nepřesahující , lze sestavit jako klikový součet grafů s maximálními vrcholy, v takovém případě se používají c-klikové součty [2] .

Existuje také úzký vztah mezi klikovými součty a konektivitou grafu  — pokud graf není vertexově propojen (takže existuje mnoho vertexů, jejichž odstranění vede ke ztrátě konektivity), pak lze graf reprezentovat jako klikový součet menších grafů. Například strom SPQR dvojitě propojeného grafu je znázorněním grafu jako součet jeho trojnásobně spojených komponent na 2 kliknutí .

Aplikace na strukturální teorii grafů

Klikové součty jsou důležité ve strukturální teorii grafů, kde se používají k popisu určitých rodin grafů jako grafů tvořených klikovým součtem menších grafů. Prvním výsledkem tohoto typu [3] byla Wagnerova věta [4] , která dokázala, že grafy, které neobsahují kompletní grafy s pěti vrcholy jako vedlejší , jsou součty přes 3 kliky rovinných grafů s Wagnerovým grafem . Pomocí této strukturní věty lze ukázat, že problém čtyř barev je ekvivalentní případu Hadwigerovy domněnky . Chordální grafy  jsou přesně ty grafy, které lze vytvořit jako součty klik nad klikami bez mazání hran, a kontrahované grafy  jsou grafy, které lze vytvořit jako součty bez mazání hran nad klikami a maximální rovinné grafy [5] . Grafy, ve kterých jakýkoli vygenerovaný cyklus délky čtyři a více tvoří minimální oddělovací podgraf (po jeho odstranění se graf rozdělí na dvě nebo více oddělených složek a žádná podmnožina cyklu nemá stejné vlastnosti), jsou přesně klikové součty klik a maximální rovinné grafy , opět bez odstranění hran [6] . Johnson a McKee [7] použili klikové součty akordických grafů a paralelně-sekvenčních grafů k popisu částečně definovaných [8] matic s pozitivně definitní extenzí.

Je možné získat rozklad klikových součtů pro jakoukoli rodinu grafů uzavřenou pod vedlejší operací - grafy v jakékoli vedlejší uzavřené rodině lze vytvořit z klikových součtů grafů, které jsou "téměř vnořeny" na površích konečného rodu , což znamená že vnoření je povoleno při vyhýbání se malému počtu střech (vrcholů, které mohou být připojeny k libovolnému počtu dalších vrcholů) a trychtýřů (grafy s úzkou šířkou dráhy , které nahrazují plochy, když jsou vloženy na povrch) [9] . Tyto popisy byly použity jako důležitý nástroj při konstrukci aproximačních algoritmů a časově-subexponenciálních přesných algoritmů pro NP-úplné optimalizační problémy na malých uzavřených rodinách grafů [10] [11] [12] .

Zobecnění

Teorii součtů přes kliky lze zobecnit z grafů na matroidy . Seymourův dekompoziční teorém popisuje pravidelné matroidy (matroidy reprezentující zcela unimodulární matice ) jako 3-součty grafických matroidů (matroidy reprezentující kostry), kografické matroidy a některé 10prvkové matroidy [13] .

Poznámky

  1. ↑ Je zde určitá nejasnost. Oxley Oxley, 1992 říká, že všechny klikové hrany musí být odstraněny. D. Epstein (ve vysvětlivkách k anglické verzi článku) uvádí, že v některých aplikacích je možné zvolit, které okraje odstranit a které ponechat, a v některých aplikacích nelze odstranit vůbec
  2. ↑ Lovász, 2006 .
  3. ↑ Jak poukazují Križ a Thomas Kříž, Thomas, 1990 , kteří uvádějí některé další popisy rodin grafů na základě součtů kliknutí.
  4. ↑ Wagner, 1937 .
  5. ↑ Seymour, Weaver, 1984 .
  6. ↑ Diestel, 1987 .
  7. ↑ Johnson, McKee, 1996 .
  8. ↑ Částečně definovaná matice je matice, ve které nejsou vyplněny všechny buňky. Takové matice se používají v teorii expertních hodnocení, v doporučovacích systémech
  9. ↑ Robertson, Seymour, 2003 .
  10. ↑ Demaine (1), 2004 .
  11. ↑ Demaine (2), 2005 .
  12. ↑ Demaine (3), 2005 .
  13. ↑ Seymour, 1980 .

Literatura