Klika-součet - Clique-sum

Klika-součet dvou rovinných grafů a Wagnerova grafu, tvořící a K.5- bezvýznamný graf.

v teorie grafů, obor matematiky, a klika-součet je způsob kombinace dvou grafů jejich slepením v a klika, analogicky k připojená suma provoz v topologie. Pokud dva grafy G a H každá obsahuje kliky stejné velikosti, klika-součet G a H je tvořen z jejich disjunktní unie identifikováním dvojic vrcholů v těchto dvou klikách pro vytvoření jedné sdílené kliky a následným odstraněním některých okrajů kliky. A k-klika-součet je klika-součet, ve kterém mají obě kliky maximálně k vrcholy. Jeden může také tvořit kliky-součty a k-klika-součty více než dvou grafů opakovanou aplikací operace se dvěma kliky a součty.

Různé zdroje se neshodují na tom, které hrany by měly být odstraněny v rámci operace klika-součet. V některých kontextech, jako je například rozklad chordální grafy nebo zúžené grafy, neměly by být odstraněny žádné hrany. V jiných kontextech, například SPQR-strom rozkladu grafů na jejich komponenty spojené se 3 vrcholy, všechny hrany by měly být odstraněny. A v ještě dalších kontextech, jako je věta o struktuře grafu pro méně uzavřené rodiny jednoduchých grafů je přirozené povolit, aby byla sada odstraněných hran specifikována jako součást operace.

Související pojmy

Clique-sumy mají úzkou souvislost s šířka stromu: Pokud mají dva grafy maximálně šířku stromu k, stejně tak jejich k-klika-součet. Každý strom je součet 1 hran kliky. Každý sériově paralelní graf, nebo obecněji každý graf s šířka stromu nanejvýš dva, mohou být vytvořeny jako součet trojúhelníků se 2 klikami. Stejný typ výsledku se rozšíří na větší hodnoty k: každý graf s šířka stromu nejvíce k mohou být vytvořeny jako klikový součet grafů s maximálně k + 1 vrcholy; to je nutně a k-klika-součet.[1]

Existuje také úzké spojení mezi klikovými součty a připojení grafu: pokud graf není (k + 1) -vertex-connected (tak, aby existovala sada k vrcholy, jejichž odstranění odpojí graf), pak může být reprezentován jako a k-klika-součet menších grafů. Například SPQR strom biconnected graph je reprezentace grafu jako 2-klika-součet jeho tři propojené komponenty.

Aplikace v teorii struktury grafů

A zúžený graf, vytvořený jako klika-součet a maximální rovinný graf (žlutá) a dvě chordální grafy (červená a modrá)

Clique-součty jsou důležité v teorii struktury grafů, kde se používají k charakterizaci určitých rodin grafů jako grafů tvořených klikovými součty jednodušších grafů. První výsledek tohoto typu[2] byla věta o Wagner (1937), který dokázal, že grafy, které nemají pětvertexový úplný graf jako a Méně důležitý jsou 3 kliky - součty rovinné grafy s osmi-vrcholem Wagnerův graf; tato věta o struktuře může být použita k ukázat, že čtyřbarevná věta je ekvivalentní případu k = 5 z Hadwigerův dohad. The chordální grafy jsou přesně grafy, které lze vytvořit součty kliků bez odstranění hran, a uškrcené grafy jsou grafy, které lze vytvořit součtem klik a klik maximální rovinné grafy bez mazání hran.[3] Grafy, ve kterých každý indukovaný cyklus délky čtyři nebo větší tvoří minimální oddělovač grafu (jeho odstranění rozděluje graf na dvě nebo více odpojených komponent a žádná podmnožina cyklu nemá stejnou vlastnost) jsou přesně klika-součty kliků a maximální rovinné grafy, opět bez odstranění hran.[4] Johnson & McKee (1996) použijte kliky-součty chordálních grafů a sériově paralelních grafů k charakterizaci dílčích matice mít pozitivní určitý dokončení.

Je možné odvodit rozklad klika-součet pro libovolnou rodinu grafů uzavřenou pod drobnými operacemi grafů: grafy v každé méně uzavřené rodině mohou být vytvořeny z klika-součty grafů, které jsou „téměř vloženy“ na povrchy ohraničené rod, což znamená, že je povoleno vynechat malý počet znaků vrcholy (vrcholy, které mohou být připojeny k libovolné podmnožině ostatních vrcholů) a víry (grafy s nízkou šířka cesty které nahrazují plochy vložení povrchu).[5] Tyto charakterizace byly použity jako důležitý nástroj při konstrukci aproximační algoritmy a subexponenciálně časově přesné algoritmy pro NP-kompletní optimalizační problémy na rodinách méně uzavřených grafů.[6]

Zobecnění

Teorii klikových součtů lze také zobecnit z grafů na matroidy.[1] Zejména, Seymourova věta o rozkladu charakterizuje pravidelné matroidy (matroidy reprezentovatelné zcela unimodulární matice ) jako 3-součty grafické matroidy (matroidy představující rozpětí stromů v grafu), cographic matroidy a určitý 10prvkový matroid.[1][7]

Poznámky

  1. ^ A b C Lovász (2006).
  2. ^ Podle připsání Kříž a Thomas (1990), kteří uvádějí několik dalších charakteristik rodin grafů na základě klika-součet.
  3. ^ Seymour & Weaver (1984).
  4. ^ Diestel (1987).
  5. ^ Robertson & Seymour (2003)
  6. ^ Demaine a kol. (2004); Demaine a kol. (2005); Demaine, Hajiaghayi & Kawarabayashi (2005).
  7. ^ Seymour (1980).

Reference