Nezávislá množina

V teórii grafov je nezávislou podmnožinou N množiny V, taká podmnožina, ktorá nemá žiadne dva zo svojich vrcholov incidentné s tou istou hranou v grafe G=(V, H). To znamená, že je to taká podmnožina N množiny V vrcholov v, že každé dva vrcholy nemajú takú hranu, ktorá by ich spájala.

9 modrých vrcholov je maximálna nezávislá podmnožina tohto grafu.

Maximálna nezávislá množina

Je preto prospešné zaoberať sa maximálnymi nezávislými množinami, keďže každý vrchol ${\displaystyle v\in \ V}$ tvorí nezávislú podmnožinu množiny V. Maximálnou nezávislou podmnožinou V, ak neexistuje taká nezávislá podmnožina N‘ množiny V, aby platilo, že N je rôzna od N‘ a N je podmnožinou N‘ a tá je podmnožinou V. Počet maximálnych nezávislých množín v n-vrcholovom cyklickom grafe G je dané Perrinovym číslom (to je dané rekurentým vzťahom). Maximálna nezávislá množina v n-vrcholovom slede je daný Padovanovou sekvenciou.

Príklad 1: maximálne nezávislé množiny sú: N₁={1}, N₂={2,5}, N₃={3,5}, N₄={3,6}, N₅={2, 4, 6}

Nezávislosť grafu je vlastne maximálna mohutnosť z mohutností všetkých maximálnych nezávislých podmnožín množiny V. Označuje sa &. Pre obrázok v príklade 1 je to ${\displaystyle \alpha (G)=3}$.

Klika grafu

S nezávislosťou grafu úzko súvisí pojem klika grafu. Ak K je podmnožinou množiny V a každé dva prvky množiny K sú priľahlé, potom je množina K úplnou množinou v grafe G. Čiže ak K je úplná v grafe G a nie je podmnožinou žiadnej inej úplnej množiny v grafe G, tak K je maximálna úplná množina alebo klika v grafe G. K nazývame maximálnou klikou v grafe G, vtedy, ak má najväčší počet prvkov medzi všetkými klikami v G. Pojem klika má aplikáciu aj v spoločenských vedách tým, že vrcholy grafu môžu byť osoby a hrany predstavujú nejakú spojitosť medzi týmito ľuďmi (zhodu politických názorov, Erdősovo číslo). Klikové číslo grafu predstavuje počet vrcholov maximálnej kliky grafu G. Označujeme ho ${\displaystyle \omega }$(G). V príklade 2 je to ${\displaystyle \omega }$(G)=4.

Príklad 2:

Uvážme, že každá maximálna nezávislá podmnožina vrcholov grafu G je rovná klike komplementárneho grafu, kvôli tomu, že v nezávislej podmnožine sú vrcholy, medzi ktorými v grafe G neexistuje žiadna hrana.Čiže je platné: ${\displaystyle \alpha (G)=\omega ({\bar {G}})}$

Minimálna dominujúca množina

Žiadna vlastná podmnožina týchto podmnožín nie je dominujúca. V grafe, v príklade 1, sú minimálnymi dominujúcimi podmnožinami: D₁={1], D₂={6,3}, D₃={5,3} a D₄={5,2}, D₅={6,4,2}. Z definície minimálnej dominujúcej podmnožiny vyplýva dôkaz nasledujúcej vety: komponent ${\displaystyle {\bar {D}}=V-D}$ je dominujúcou podmnožinou grafu G, ak D je minimálna dominujúca podmnožina vrcholov grafu G, ktorej nie sú izolované vrcholy.

Dominanciou grafu G, označujeme ${\displaystyle \beta }$(G)nazývame minimálnu mohutnosť z mohutnosti všetkých dominujúcich podmnožín vrcholov grafu G.

Veta: Maximálna nezávislá podmnožina vrcholov grafu G je práve vtedy, ak je jeho dominujúcou podmnožinou.

Dôkaz 1: Nech maximálnou nezávislou podmnožinou grafu G je N, to znamená, že ju nemožno rozšíriť o žiaden vrchol bez porušenia nezávislosti, takže do množiny jej susedov patria všetky ostatné vrcholy. to je ale vlastnosť dominujúcej podmnožiny.

Dôkaz 2: Nech dominujúcou podmnožinou grafu G je D, ktorá je zároveň nezávislá, potom už neexistuje vrchol v grafe G, ktorý by so žiadnyzm vrcholom z množiny D nesusedil; to unamená, že je aj minimálne nezávislá.

Dôsledok: Pre dominanciu ${\displaystyle \beta }$(G) a nezávislosť ${\displaystyle \alpha }$(G) grafu G platí vzťah ${\displaystyle \beta (G)\leq \alpha (G)}$

Externé odkazy (v angličtine)

• http://mathworld.wolfram.com/MaximalIndependentVertexSet.html
• Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring Archivované 2013-05-29 na Wayback Machine

Tento text bol inšpirovaný publikáciou Michala Bučka, Mariána Klešča: Diskrétna matematika, vydavateľstvo ELFA