Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Stránky: 1
- Hlavní strana
- » Algoritmy a programování
- » Algoritmus pro zjištění, zdali je podmnožina uzlů v grafu nezávislá
#1 15. 05. 2012 05:23
Algoritmus pro zjištění, zdali je podmnožina uzlů v grafu nezávislá
Ahoj, řeším problém, kdy mám danou podmnožinu uzlů nějakého grafu a potřebuju zjistit, zdali je tato konkrétní podmnožina maximálně nezávislá (tedy nelze přidat uzel, aniž by se porušila nezávislost). Následující algoritmus tento problém řeší v O(n^3), ale já bych to potřebovala rychleji.
Můj algoritmus pro ověření, zdali je podmnožina maximálně nezávislou obsahuje dvě funkce:
isIndependent
- Pro všechny uzly v podmnožině zkontroluje jejich sousedy, zdali také nejsou v podmnožině. Pokud ano, tak není nezávislá.
IsMaxIndependent
- Zkontroluje se, zdali je podmnožina nezávislá zavoláním funkce isIndependent. Pokud ne, tak konec.
- Postupně vždy přidá uzel, který v množině není, zkontroluje nezávislost funkcí isIndependent, uzel zase odebere a přidá další. Pokud po přidání uzlu je podmnožina nezávislá, tak konec - není maximální nezávislou podmnožinou.
Jak bylo řečeno, tento algoritmus má kubickou složitost. Existuje nějaký, který by to zvládl rychleji?
Díky za odpověď.
Offline
#2 15. 05. 2012 08:28
Re: Algoritmus pro zjištění, zdali je podmnožina uzlů v grafu nezávislá
Nejsem si jistý že jsem problém správně pochopil, takže netvrdím že to mám 100% správně.
Pokud se dá přidat alespoň jeden uzel tak že nebude sousedit s žádným uzlem, který v podmnožině již je-> algoritmus se zastaví, není maximálně nezávislá
Takže v podstatě potřebuješ určit uzlům vzdálenost od nejbližšího uzlu který je v podmožině. Pokud některý uzel bude od nejbližšího vzdálený o víc než jen hranu, není podmnožina max. nezávislá.
Nejdřív jsem přemýšlel na použití prohl. do šířky nebo do hloubky ale jde to podobně a jednodušejí.
Projdeš uzle podmnožiny, obarvíš je a obarvíš i jejich sousedy. Poté projdeš uzly grafu a pokud najdeš nějaký neobarvený uzel, není podmnožina maximálně nezávislá.
n - počet uzlů v grafu
m - počet hran v grafu
protože může být max. nezávislá, obarvení může vzít až O(n+m)
projití uzlů O(n)
což výsledně je O(n+m)
Ale můžu to mít dost dobře špatně, před 10 minuty jsem ani nevěděl co to maximálně nezávislá podmnožina je.
Offline
Stránky: 1
- Hlavní strana
- » Algoritmy a programování
- » Algoritmus pro zjištění, zdali je podmnožina uzlů v grafu nezávislá