Rozdělit graf - Split graph - Wikipedia

Tento článek je o grafech, které lze rozdělit na kliky a nezávislou sadu. Výřezy, které tvoří úplné bipartitní grafy, viz split (teorie grafů).
Rozdělený graf, rozdělený do kliky a nezávislé množiny.

v teorie grafů, obor matematiky, a dělený graf je graf, ve kterém lze vrcholy rozdělit na a klika a nezávislá sada. Rozdělené grafy byly nejprve studovány Földesem a Kladivo  (1977a, 1977b ) a nezávisle představil Tyshkevich a Černyak (1979 ).[1]

Rozdělený graf může mít více než jeden oddíl do kliky a nezávislou sadu; například cesta A–b–C je dělený graf, jehož vrcholy lze rozdělit třemi různými způsoby:

  1. klika {A,b} a nezávislá množina {C}
  2. klika {b,C} a nezávislá množina {A}
  3. klika {b} a nezávislá množina {A,C}

Rozdělené grafy lze charakterizovat z hlediska jejich zakázané indukované podgrafy: graf je rozdělen právě tehdy, když ne indukovaný podgraf je cyklus na čtyřech nebo pěti vrcholech nebo dvojici disjunktních hran (doplněk 4-cyklu).[2]

Vztah k jiným rodinám grafů

Z definice jsou rozdělené grafy jasně uzavřeny pod doplňování.[3] Další charakterizace dělených grafů zahrnuje doplňování: jsou chordální grafy the doplňuje z nichž jsou také akordické.[4] Stejně jako chordální grafy jsou průsečíkové grafy dílčích stromů stromů jsou rozdělenými grafy průsečíkové grafy odlišných dílčích podloží stromů hvězdné grafy.[5] Téměř všechny chordální grafy jsou rozdělené grafy; tj. v limitu jako n jde do nekonečna, zlomek n-vertexové akordové grafy, které jsou rozdělené, se blíží jednomu.[6]

Protože chordální grafy jsou perfektní, stejně tak i dělené grafy. The dvojité dělené grafy, rodina grafů odvozených z rozdělených grafů zdvojnásobením každého vrcholu (takže klika vyvolá antimatching a nezávislá množina indukuje shodu), figuruje prominentně jako jedna z pěti základních tříd dokonalých grafů, ze kterých mohou být všechny ostatní tvořil v důkazu Chudnovsky a kol. (2006) z Silná dokonalá věta o grafu.

Pokud je graf rozděleným grafem i intervalový graf, pak je jeho doplňkem jak rozdělený graf, tak a srovnávací graf a naopak. Rozdělené grafy srovnatelnosti, a tedy i grafy rozděleného intervalu, lze charakterizovat pomocí sady tří zakázaných indukovaných podgrafů.[7] Rozkol cographs jsou přesně prahové grafy. Rozkol permutační grafy jsou přesně intervalové grafy, které mají doplňky intervalového grafu;[8]toto jsou permutační grafy šikmé sloučené permutace.[9] Rozdělené grafy mají kochromatické číslo 2.

Algoritmické problémy

Nechat G být rozděleným grafem rozděleným do kliky C a nezávislý soubor Já. Pak každý maximální klika v děleném grafu je buď C sám, nebo sousedství vrcholu v Já. Je tedy snadné určit maximální kliku a doplňkově maximální nezávislá sada v děleném grafu. V každém děleném grafu musí platit jedna z následujících tří možností:[10]

  1. Existuje vrchol X v Já takhle C ∪ {X} je kompletní. V tomto případě, C ∪ {X} je maximální klika a Já je maximální nezávislá množina.
  2. Existuje vrchol X v C takhle Já ∪ {X} je nezávislý. V tomto případě, Já ∪ {X} je maximální nezávislá množina a C je maximální klika.
  3. C je maximální klika a Já je maximální nezávislá množina. V tomto případě, G má jedinečný oddíl (C,Já) do kliky a nezávislé sady, C je maximální klika a Já je maximální nezávislá množina.

Některé další optimalizační problémy, které jsou NP-kompletní na obecnějších rodinách grafů, včetně zbarvení grafu, jsou podobně jednoduché na dělených grafech. Hledání a Hamiltonovský cyklus Zůstává NP-kompletní i pro rozdělené grafy, které jsou silně chordální grafy.[11] Je také dobře známo, že problém minimální dominující sady přetrvává NP-kompletní pro dělené grafy.[12]

Sekvence titulů

Jedna pozoruhodná vlastnost dělených grafů je, že je lze rozpoznat pouze z jejich stupně. Nechte posloupnost stupňů grafu G být d1 ≥ d2 ≥ ... ≥ dna nechte m být největší hodnotou i takhle di ≥ i - 1. Potom G je dělený graf právě tehdy

Pokud je to váš případ, pak m vrcholy s největšími stupni tvoří maximální kliky Ga zbývající vrcholy tvoří nezávislou množinu.[13]

Počítání dílčích grafů

Royle (2000) to ukázal n-vertex rozdělené grafy s n jsou v osobní korespondence s jistotou Spernerovy rodiny. Pomocí této skutečnosti určil vzorec pro počet neizomorfních dělených grafů n vrcholy. Pro malé hodnoty n, začínající od n = 1, tato čísla jsou

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... (sekvence A048194 v OEIS ).

Tento enumerativní výsledek také dříve prokázal Tyshkevich & Chernyak (1990).

Poznámky

  1. ^ Földes & Hammer (1977a) měl obecnější definici, ve které byly zahrnuty také grafy, které nazývali rozdělené grafy bipartitní grafy (tj. grafy, které jsou rozděleny na dvě nezávislé sady) a doplňuje bipartitních grafů (tj. grafů, které lze rozdělit na dvě kliky). Földes & Hammer (1977b) použijte zde uvedenou definici, která byla dodržena v následující literatuře; například je Brandstädt, Le & Spinrad (1999), Definice 3.2.3, s. 41.
  2. ^ Földes & Hammer (1977a); Golumbic (1980), Věta 6.3, str. 151.
  3. ^ Golumbic (1980), Věta 6.1, str. 150.
  4. ^ Földes & Hammer (1977a); Golumbic (1980), Věta 6.3, str. 151; Brandstädt, Le & Spinrad (1999), Věta 3.2.3, s. 41.
  5. ^ McMorris & Shier (1983); Voss (1985); Brandstädt, Le & Spinrad (1999), Věta 4.4.2, s. 52.
  6. ^ Bender, Richmond & Wormald (1985).
  7. ^ Földes & Hammer (1977b); Golumbic (1980), Věta 9.7, strana 212.
  8. ^ Brandstädt, Le & Spinrad (1999), Dodatek 7.1.1, str. 106 a Theorem 7.1.2, str. 107.
  9. ^ Kézdy, Snevily & Wang (1996).
  10. ^ Hammer & Simeone (1981); Golumbic (1980), Věta 6.2, str. 150.
  11. ^ Müller (1996)
  12. ^ Bertossi (1984)
  13. ^ Hammer & Simeone (1981); Tyshkevich (1980); Tyshkevich, Melnikow & Kotov (1981); Golumbic (1980), Theorem 6.7 and Corollary 6.8, p. 154; Brandstädt, Le & Spinrad (1999), Věta 13.3.2, s. 203. Merris (2003) dále zkoumá sekvence stupňů dělených grafů.

Reference

Další čtení

  • Kapitola o dělených grafech se v knize objevuje podle Martin Charles Golumbic "Algoritmická teorie grafů a dokonalé grafy".