Rozdělený graf

V teorii grafů je rozdělený graf graf, ve kterém lze vrcholy rozdělit na kliku a nezávislou množinu . Dělené grafy poprvé studovali Földes a Hammer [1] [2] a nezávisle na nich je představili Tyszkiewicz a Czernyak [3] [4] .

Rozdělený graf může mít několik rozkladů na kliku a nezávislou množinu. Cesta a - b - c je tedy rozdělena a lze ji 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ělitelné grafy lze charakterizovat z hlediska jejich zakázaných podgrafů – graf je rozdělen tehdy a jen tehdy, když žádný vygenerovaný podgraf není cyklem se čtyřmi nebo pěti vrcholy a také neexistuje dvojice nespojených vrcholů (tj. doplněk cyklu). ze 4 vrcholů) [5 ] [6] .

Vztah k jiným skupinám grafů

Podle definice je třída rozdělených grafů uzavřena vzhledem k operaci doplňku [7] . Další vlastností dělených grafů, která zahrnuje doplněk, jsou akordické grafy , jejichž doplňky jsou také akordické [8] . Protože akordické grafy jsou průsečíkové grafy podstromů stromů, dělené grafy jsou průsečíkové grafy různých podhvězd hvězd [9] . Téměř všechny akordické grafy jsou rozdělené grafy. To znamená, že když n směřuje k nekonečnu, podíl počtu akordických grafů s n vrcholy k počtu oddělitelných grafů má tendenci k jedné [10] .

Vzhledem k tomu, že akordické grafy jsou dokonalé , jsou perfektní i dělitelné grafy. Dvojité rozdělené grafy , rodina grafů získaná z rozdělených grafů zdvojnásobením počtu vrcholů (takže klika dává anti-shodu – množinu hran vzdálených nejvýše 2 od sebe a nezávislá množina se stává odpovídající), se jeví jako jedna z pěti hlavních tříd dokonalých grafů, ze kterých lze sestavit všechny ostatní, aby se dokázala přísná věta o dokonalém grafu [11] .

Pokud je graf jak dělitelný, tak intervalový , pak je jeho doplněk jak dělitelný, tak graf srovnatelnosti a naopak. Rozdělitelné grafy srovnatelnosti, a tedy i rozdělitelné intervalové grafy, lze popsat pomocí tří zakázaných podgrafů [12] . Dělené kografy jsou  přesně prahové grafy a dělené permutační grafy  jsou přesně intervalové grafy, jejichž doplňky jsou také intervalové [13] . Kochromatické číslo rozdělených grafů je 2.

Maximální klika a maximální nezávislá sada

Nechť G  je rozdělený graf rozložený na kliku C a nezávislou množinu I . Pak se jakákoli maximální klika v rozděleném grafu buď shoduje s C nebo je sousedstvím vrcholu z I . V rozděleném grafu je tedy snadné najít maximální kliku a navíc maximální nezávislou množinu . Jakýkoli dělitelný graf musí obsahovat jedno z následujících tvrzení [14] :

  1. V I je vrchol x takový, že C ∪ { x } je kompletní. V tomto případě C ∪ { x } je maximální klika a I  je maximální nezávislá množina.
  2. V C existuje vrchol x takový, že I ∪ { x } je nezávislá množina. V tomto případě je I ∪ { x } maximální nezávislá množina a C  je maximální klika.
  3. C je největší klika a I největší nezávislá množina. V tomto případě má G jedinečný rozklad ( C , I ) na kliku a nezávislou množinu, C je maximální klika a I je maximální nezávislá množina.

Některé další optimalizační problémy, které jsou NP-úplné na obecnějších rodinách grafů, včetně zbarvení , jsou řešeny jednoduše na rozdělených grafech.

Posloupnosti stupňů

Jednou z velkých vlastností rozdělených grafů je to, že je lze rozpoznat čistě podle jejich vrcholových stupňů . Nechť d 1 ≥ d 2 ≥ … ≥ d n  je posloupnost vrcholových stupňů grafu G a m  je největší hodnota i , pro kterou d i ≥ i  - 1. Pak G je rozdělený graf právě tehdy, když

Pokud je to pravda, pak m vrcholů s největšími stupni tvoří maximální kliku G a zbývající vrcholy tvoří nezávislou množinu [15] .

Počítání rozdělených grafů

Royle [16] ukázal, že rozdělené grafy s n vrcholy odpovídají jedna ku jedné určitým Spernerovým rodinám . Pomocí této skutečnosti našel vzorec pro počet (neizomorfních) rozdělených grafů s n vrcholy. Pro malé hodnoty n , počínaje n = 1, jsou tato čísla

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

Tento výčet již dříve dokázali Tyszkiewicz a Chernyak [17] .

Poznámky

  1. ↑ Földes, Hammer, 1977a .
  2. ↑ Földes, Hammer, 1977b .
  3. ↑ Tyshkevich, Chernyak, 1979 .
  4. ↑ Földes a Hammer Földes, Hammer, 1977a dali obecnější definici, ve které grafy, které nazývají dělitelné, zahrnují také bipartitní grafy (tj. grafy rozdělené do dvou nezávislých sad) a doplňky bipartitních grafů (tj. grafy, které lze rozložit na dva kliky). Földer a Hammer Földes, Hammer, 1977b uvádí zde uvedenou definici a použitou v následné literatuře, např. Brandstädt, Le a Spinrad Brandstädt, Le, Spinrad, 1999 , Definice 3.2.3, str. 41
  5. ↑ Földes, Kladivo, 1977a ; Golumbic, 1980 , věta 6.3, str. 151.
  6. ↑ Pinar Heggernes, Dieter Kratsch. Algoritmy rozpoznávání certifikující lineární čas a zakázané indukované podgrafy // Nordic Journal of Computing. - 2007. - T. 14 .
  7. ↑ Golumbic, 1980 , Věta 6.1, s. 150.
  8. ↑ Földes, Kladivo, 1977a ; Golumbic, 1980 , věta 6.3, str. 151; Brandstädt, Le, Spinrad, 1999 , věta 3.2.3, s. 41.
  9. ↑ McMorris, Shier, 1983 ; Voss, 1985 ; Brandstädt, Le, Spinrad, 1999 , věta 4.4.2, s. 52.
  10. ↑ Bender, Richmond, Wormald, 1985 .
  11. ↑ Chudnovsky, Robertson, Seymour, Thomas, 2006 .
  12. ↑ Földes, Kladivo, 1977b ; Golumbic, 1980 , věta 9.7, str. 212.
  13. ↑ Brandstädt, Le, Spinrad, 1999 , Důsledek 7.1.1 s. 106 a věta 7.1.2 s. 107.
  14. ↑ Kladivo, Simeone, 1981 ; Golumbic, 1980 , věta 6.2, str. 150.
  15. ↑ Kladivo, Simeone, 1981 ; Tyshkevich, 1980 ; Tyshkevich, Melnikov, Kotov, 1981 ; Golumbic, 1980 , věta 6.7 a důsledek 6.8, str. 154; Brandstädt, Le, Spinrad, 1999 , Věta 13.3.2, s. 203. Merris, 2003 další úvahy o stupňové posloupnosti rozdělených grafů.
  16. ↑ Royle, 2000 .
  17. ↑ Tyshkevich, Chernyak, 1990 .

Literatura

Další čtení