Maximální nezávislá sada

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 9. listopadu 2021; kontroly vyžadují 2 úpravy .

V teorii grafů je maximální nezávislá množina , maximální stabilní množina nebo maximální stabilní množina nezávislá množina , která není podmnožinou jiné nezávislé množiny. To znamená, že je to množina vrcholů S taková, že každá hrana grafu má alespoň jeden koncový vrchol ne v S a každý vrchol mimo S má alespoň jednoho souseda v S . Maximální nezávislá množina je také dominantní množinou v grafu a každá dominantní množina, která je nezávislá, musí být maximální nezávislou množinou, proto se maximální nezávislé množiny také nazývají nezávislé dominující množiny . Graf může mít mnoho maximálních nezávislých množin v širokém rozsahu velikostí. [jeden]

Největší nezávislá množina co do velikosti se nazývá největší nezávislá množina .

Například v grafu P 3 jsou cesty se třemi vrcholy a , b a c a dvěma hranami ab a bc , obě množiny { b } a { a , c } maximálně nezávislé, z nichž pouze { a , c } je největší nezávislý. Množina { a } je nezávislá, ale není maximální, protože je podmnožinou { a , c }. Ve stejném grafu jsou množiny { a , b } a { b , c } maximální kliky.

Fráze „maximální nezávislá množina“ se také používá k popisu maximálních podmnožin nezávislých prvků v matematických strukturách jiných než grafy, zejména ve vektorových prostorech a matroidech .

Vztah s jinými množinami vrcholů

Jestliže S  je maximální nezávislá množina v nějakém grafu, pak je to maximální klika v doplňku grafu . Maximální klika je sada vrcholů, které generují úplný podgraf a nejsou obsaženy ve větším úplném podgrafu. Jedná se tedy o množinu vrcholů S tak, že každý pár vrcholů v S je spojen hranou a pro žádný vrchol mimo S neexistuje žádná hrana spojující jej alespoň s jedním vrcholem v S . Graf může mít několik maximálních kliků různých velikostí. Nalezení maximální kliky maximální velikosti je problém maximální kliky .

Někteří autoři požadují, aby klika byla v definici maximální a místo výrazu maximální klika používají výraz klika.

Doplněk maximální nezávislé množiny, tedy vrcholy, které do nezávislé množiny nepatří, tvoří minimální vertexové pokrytí . To znamená, že doplněk je kryt vrcholu , sada vrcholů, které obsahují alespoň jeden koncový vrchol jakékoli hrany, a je minimální v tom smyslu, že žádný z vrcholů nelze odstranit bez porušení krytu. Minimální vrcholové pokrytí je studováno ve statistické mechanice v modelu plynové mřížky na tuhých koulích , matematické abstrakci přechodu z kapaliny do pevného skupenství. [2]

Dominantní je jakákoliv maximální nezávislá množina , tedy množina vrcholů taková, že jakýkoli vrchol v grafu buď patří do množiny, nebo s ní sousedí. Množina vertexů je maximální nezávislou množinou právě tehdy, když se jedná o nezávislou dominující množinu.

Použití v charakteristikách rodin grafů

Některé rodiny grafů lze popsat pomocí jejich maximálních kliků nebo maximálních nezávislých množin. Příklady zahrnují grafy s neredukovatelnými maximálními kliky a grafy s dědičně neredukovatelnými maximálními kliky. O grafu se říká, že má neredukovatelné maximální kliky , pokud jakákoli maximální klika obsahuje hranu, která nepatří žádné jiné maximální klikě, a dědičně neredukovatelné maximální kliky , pokud tato vlastnost platí pro jakýkoli podgraf. [3] Grafy s dědičně neredukovatelnými maximálními klikami zahrnují grafy bez trojúhelníků , bipartitní grafy a intervalové grafy .

Cographs lze popsat jako grafy, ve kterých jakákoli maximální klika protíná jakoukoli maximální nezávislou množinu a ve kterých tato vlastnost platí pro všechny generované podgrafy.

Odhady počtu sad

Moon a Moser ( Moon, Moser 1965 ) ukázali, že každý graf s n vrcholy má maximálně 3n /3 maximální kliky. Také graf s n vrcholy má nejvýše 3 n /3 maximálních nezávislých množin. Graf, který má přesně 3n /3 maximálních nezávislých množin, lze snadno sestrojit jednoduše tím, že vezmeme rozpojenou množinu n /3 trojúhelníkových grafů . Jakákoli maximální nezávislá množina v tomto grafu je tvořena výběrem jednoho vrcholu z každého trojúhelníku. Dodatečný graf s 3 n / 3 maximálními kliky je speciální formou Turanových grafů . Kvůli spojení tohoto grafu s hranicí Měsíc-Moser se tyto grafy někdy nazývají grafy Měsíc-Moser. Silnější hranice jsou možné, pokud je omezena velikost maximálních nezávislých množin — počet maximálních nezávislých množin velikosti k v žádném grafu s n vrcholy nepřekročí

Grafy dosahující této hranice jsou opět Turanovy grafy. [čtyři]

Některé rodiny grafů však mohou mít podstatně silnější hranice počtu maximálních nezávislých množin nebo maximálních kliků. Pokud například grafy v rodině mají O(n) hran a rodina je uzavřena pod podgrafy, pak všechny maximální kliky mají konstantní velikost a počet maximálních kliků je téměř lineární. [5]

Je jasné, že každý graf s neredukovatelnými maximálními klikami má nanejvýš maximální kliky než hrany. Silnější vazba je možná pro intervalové grafy a akordické grafy — v těchto grafech  nemůže být více než n maximálních kliků.

Počet maximálních nezávislých množin v cyklu s n vrcholy je dán Perrinovými čísly a počet maximálních nezávislých množin v cestě s n vrcholy je dán Padovanovou posloupností . [6] Obě tyto posloupnosti jsou tedy úměrné mocnině 1,324718 (tedy plastickému číslu ).

Nastavit výčtové algoritmy

Algoritmus pro výpis všech maximálních nezávislých množin nebo maximálních klik v grafu může být použit jako rutina pro řešení mnoha NP-úplných problémů v teorii grafů. Nejzřetelnějšími problémy jsou problém maximální nezávislé množiny, problém maximální kliky a problém minimální nezávislé dominující množiny.

Všechny musí být maximální nezávislé množiny nebo maximální kliky a lze je najít pomocí algoritmu, který všechny takové množiny vyjmenuje a vybere množinu maximální nebo minimální velikosti. Stejně tak lze minimální pokrytí vrcholů nalézt jako doplněk jedné z maximálních nezávislých množin. Lawler ( Lawler 1976 ) poznamenal, že výčet maximálních nezávislých množin lze také použít k nalezení 3barevného zbarvení grafu – graf může být 3barevný právě tehdy, když je doplněk jedné z maximálních nezávislých množin bipartitní . Tento přístup použil nejen pro barvení 3 barvami, ale také jako součást obecnějšího algoritmu barvení grafů a podobný přístup pro barvení grafů použili i další autoři. [7]

Další složitější problémy lze zredukovat na nalezení kliky nebo samostatné množiny zvláštního druhu. To poskytuje motivaci pro hledání algoritmů, které efektivně vyčíslují všechny maximální nezávislé množiny (nebo ekvivalentně maximální kliky).

Moonův a Moserův důkaz vazby 3 n /3 na počtu maximálních nezávislých množin je možné přímo převést na algoritmus, který všechny takové množiny vyčíslí v čase O(3 n /3 ). [8] Pro grafy, které mají maximální možný počet maximálních nezávislých množin, dává tento algoritmus konstantní čas na nalezenou množinu. Algoritmus s tímto časovým limitem však může být extrémně neefektivní pro grafy s omezenějším počtem nezávislých množin. Z tohoto důvodu mnoho výzkumníků hledá algoritmy pro výčet všech maximálních nezávislých množin v polynomiálním čase na nalezenou množinu. [9] Doba nalezení jedné maximální nezávislé množiny je úměrná době násobení matice v hustých grafech nebo rychlejší v různých třídách řídkých grafů. [deset]

Poznámky

  1. ↑ Erdős ( Erdős 1966 ) ukázal, že počet různých velikostí maximálních nezávislých množin v grafu s n vrcholy může dosáhnout a nikdy nepřekročit .
  2. ↑ Weigt, Hartmann, 2001 .
  3. ↑ Informační systém o zahrnutí tříd grafů: Grafy s neredukovatelnými maximálními kliky archivovány 09. 7. 2007 . a s dědičně neredukovatelnými maximálními kliky Archivováno z originálu 8. července 2007. .
  4. ↑ ( Byskov 2003 ). Dřívější práce viz ( Croitoru 1979 ) a ( Eppstein 2003 ).
  5. ↑ ( Čiba, Nishizeki 1985 ). Podmínka řídkosti je ekvivalentní podmínce, že rodina grafů má ohraničenou stromovitost .
  6. ↑ ( Bisdorff, Marichal 2007 ); ( Euler 2005 ); ( Füredi 1987 ).
  7. ↑ ( Eppstein 2003 ); ( Byskov 2003 ).
  8. ↑ ( Eppstein 2003 ). Pro hranice široce používaného Bron-Kerbosh algoritmu viz ( Tomita, Tanaka, Takahashi 2006 ).
  9. ↑ ( Bomze, Budinich, Pardalos, Pelillo 1999 ); ( Eppstein 2005 ); ( Jennings, Motycková 1992 ); ( Johnson, Yannakakis, Papadimitriou 1988 ); ( Lawler, Lenstra, Rinnooy Kan 1980 ); ( Liang, Dhall, Lakshmivarahan 1991 ); ( Makino, Uno 2004 ); ( Mishra, Pitt 1997 ); ( Stix 2004 ); ( Tsukiyama, Ide, Ariyoshi, Shirakawa 1977 ); ( Yu, Chen 1993 ).
  10. ↑ ( Makino, Uno 2004 ); ( Eppstein 2005 ).

Odkazy