A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
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.
Maximálna nezávislá množina
Je preto prospešné zaoberať sa maximálnymi nezávislými množinami, keďže každý vrchol 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ú: N1={1}, N2={2,5}, N3={3,5}, N4={3,6}, N5={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 .
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 (G). V príklade 2 je to (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é:
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: D1={1, D2={6,3}, D3={5,3} a D4={5,2}, D5={6,4,2}. Z definície minimálnej dominujúcej podmnožiny vyplýva dôkaz nasledujúcej vety: komponent 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 (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 (G) a nezávislosť (G) grafu G platí vzťah
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
Tento text bol inšpirovaný publikáciou Michala Bučka, Mariána Klešča: Diskrétna matematika, vydavateľstvo ELFA
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Binárny strom (teória grafov)
Cesta (teória grafov)
Chromatické číslo
Chromatický index
Cyklomatické číslo grafu
Eulerovský ťah
Excentricita (teória grafov)
Faktor grafu
Farbenie grafu
Farbenie vrcholov
Grafová postupnosť
Graf (matematika)
Hamiltonovská kružnica
Hamiltonovský graf
Hrana (teória grafov)
Komplement grafu
Komponent grafu
Kostra grafu
Kružnica (teória grafov)
Minimálna kostra grafu
Most (teória grafov)
Neplanárny graf
Nezávislá množina
Ohodnotený graf
Oreho veta
Orientované stromy
Párny graf
Petersenov graf
Podgraf
Priesečníkové číslo (teória grafov)
Problém obchodného cestujúceho
Problém siedmich mostov
Rovinný graf
Súvislý graf
Sled (teória grafov)
Spektrálna teória grafov
Strom (teória grafov)
Teória grafov
Teória grafov – grafová postupnosť
Topologická teória grafov
Vrchol (teória grafov)
Vzdialenosť (teória grafov)
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk