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:
- klika { a , b } a nezávislá množina { c }
- klika { b , c } a nezávislá množina { a }
- 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] :
- 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.
- 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.
- 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
- ↑ Földes, Hammer, 1977a .
- ↑ Földes, Hammer, 1977b .
- ↑ Tyshkevich, Chernyak, 1979 .
- ↑ 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
- ↑ Földes, Kladivo, 1977a ; Golumbic, 1980 , věta 6.3, str. 151.
- ↑ 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 .
- ↑ Golumbic, 1980 , Věta 6.1, s. 150.
- ↑ Földes, Kladivo, 1977a ; Golumbic, 1980 , věta 6.3, str. 151; Brandstädt, Le, Spinrad, 1999 , věta 3.2.3, s. 41.
- ↑ McMorris, Shier, 1983 ; Voss, 1985 ; Brandstädt, Le, Spinrad, 1999 , věta 4.4.2, s. 52.
- ↑ Bender, Richmond, Wormald, 1985 .
- ↑ Chudnovsky, Robertson, Seymour, Thomas, 2006 .
- ↑ Földes, Kladivo, 1977b ; Golumbic, 1980 , věta 9.7, str. 212.
- ↑ Brandstädt, Le, Spinrad, 1999 , Důsledek 7.1.1 s. 106 a věta 7.1.2 s. 107.
- ↑ Kladivo, Simeone, 1981 ; Golumbic, 1980 , věta 6.2, str. 150.
- ↑ 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ů.
- ↑ Royle, 2000 .
- ↑ Tyshkevich, Chernyak, 1990 .
Literatura
- EA Bender, LB Richmond, NC Wormald. Téměř všechny akordické grafy se rozdělily // J. Austral. Matematika. Soc .. - 1985. - T. 38 , no. 2 . - S. 214-221 . - doi : 10.1017/S1446788700023077 .
- Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Třídy grafů: Průzkum. - Monografie SIAM o diskrétní matematice a aplikacích, 1999. - ISBN 0-89871-432-X .
- Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. Věta o silném dokonalém grafu // Annals of Mathematics . - 2006. - T. 164 , č. 1 . - S. 51-229 . doi : 10.4007 / anals.2006.164.51 .
- Stephane Földes, Peter L. Hammer. Congressus Numerantium. - Winnipeg: Utilitas Math., 1977a. - T. XIX. - S. 311-315.
- Stephane Földes, Peter L. Hammer. Rozdělit grafy s Dilworthem číslo dva // Canadian Journal of Mathematics . — 1977b. — Sv. 29. - Vydání. 3 . - S. 666-672 . - doi : 10.4153/CJM-1977-069-1 .
- Martin Charles Golumbic. Algoritmická teorie grafů a dokonalé grafy. - Academic Press, 1980. - ISBN 0-12-289260-7 .
- Peter L. Hammer, Bruno Simeone. Rozdělení grafu // Combinatorica . - 1981. - T. 1 , vydání. 3 . - S. 275-284 . - doi : 10.1007/BF02579333 .
- FR McMorris, DR Shier. Reprezentující akordické grafy na K 1, n // Commentationes Mathematicae Universitatis Carolinae. - 1983. - T. 24 . - S. 489-494 .
- Russell Merris. Dělené grafy // European Journal of Combinatorics . - 2003. - T. 24 , no. 4 . - S. 413-430 . - doi : 10.1016/S0195-6698(03)00030-1 .
- Gordon F. Royle. Počítací sady krytů a rozdělených grafů // Journal of Integer Sequences. - 2000. - T. 3 , no. 2 . - S. 00.2.6 .
- Regina I. Tyškevič. Kanonický rozklad grafu // Zprávy Akademie věd BSSR . - 1980. - T. 24 , no. 8 . - S. 677-679 .
- R. I. Tyškevič, A. A. Černyak. Kanonický rozklad grafu definovaného stupni jeho vrcholů // Izvestiya AN BSSR, ser. Fyzikální matematika vědy. - 1979. - T. 5 . - S. 14-26 .
- R. I. Tyškevič, A. A. Černyak. Další metoda pro výčet neoznačených kombinatorických objektů // Matem. Poznámky. - 1990. - T. 48 , no. 6 . - S. 98-105 .
- R. I. Tyškevič, O. I. Melnikov, V. M. Kotov. O grafech a mocninných sekvencích: Canonical Expansion // Kybernetika. - 1981. - T. 6 . - S. 5-8 .
- H.J. Voss. Poznámka k článku McMorrise a Shiera // Commentationes Mathematicae Universitatis Carolinae. - 1985. - T. 26 . - S. 319-322 .
Další čtení
- Kapitola o rozdělených grafech lze nalézt v Algorithmic Graph Theory and Perfect Graphs Martina Charlese Golumbica.