Fórum studentů MFF UK

Heuristickym hladovym algoritmem najdete nejake male vrcholove pokryti grafu, tj. takovou mnozinu P vrcholu, ze aspon jeden vrchol kazde hrany lezi v P. Graf je zadan ke kazdemu vrcholu seznamem sousedu.

[code]Heuristickym hladovym algoritmem najdete nejake male vrcholove pokryti grafu, tj. takovou mnozinu P vrcholu, ze aspon jeden vrchol kazde hrany lezi v P. Graf je zadan ke kazdemu vrcholu seznamem sousedu.[/code]

Heuristika: do zoznamu_A si usporiadas vrcholy podla velkosti stupna.

Postupne odoberas vrcholy s najvacsim stupnom (a vkladas do zoznamu_B) a upravujes stupne ostatnych vrcholov v zozname_A, dokym ti v zozname_A neostanu vrcholy s nulovym stupnom,teda vrcholy bez hran.
V tom pripade je obsah zoznamu_A minimalnym vrcholovym pokrytim grafu.

Avsak najst minimalne vrcholove pokrytie grafu je NPC problem, teda toto je aprox. algoritmus. :)

Hladovým algoritmem sestrojte v daném grafu nezávislou množinu vrcholů, která nejde zvětšit přidáním vrcholu.

Heuristickym hladovym algoritmem najdete nejake male vrcholove pokryti grafu, tj. takovou mnozinu P vrcholu, ze aspon jeden vrchol kazde hrany lezi v P. Graf je zadan ke kazdemu vrcholu seznamem sousedu.

Zdar vsetci,
nemohol by niekto z vas postnut hladovy algoritmus pre vyhladavanie v grafe?
Napr. takato uloha:
[code]Hladovým algoritmem sestrojte v daném grafu nezávislou množinu vrcholů, která nejde zvětšit přidáním vrcholu.[/code]
alebo s heuristikou:
[code]Heuristickym hladovym algoritmem najdete nejake male vrcholove pokryti grafu, tj. takovou mnozinu P vrcholu, ze aspon jeden vrchol kazde hrany lezi v P. Graf je zadan ke kazdemu vrcholu seznamem sousedu.[/code]
Dikes, moc by ste mi pomohli aj s popisom principu.
Keby ste mali nejake priklady na assert atp.. Pomohlo by.
THX