Sabotaza najefikasnije?

Imam šumu sa usmerenim granama. Treba da pronadjem najmanji broj grana tako da se iz svakog čvora može stići u svaki drugi. Kako?

Pozdrav,
BF

Da...
Dobro jasno je da, svako stablo treba povezati da jednim tj. napraviti od njih put u oba smera... Znaci problem se svodi na jedno stablo. Ovde cu ja diskutovati o obicnom grafu (ne mora biti stablo)...
Definisicemo dva skupova cvorova:
[1] Tops = minimalni skup cvorova iz kojih se moze stici u sve ostale cvorove
[2] Bottoms = minimlani skup cvorova u koje se moze stici iz svih cvorova
Jasno je, da ukoliko nadjemo algoritam za nalazenje Tops, on je analogan za Bottoms. Tops, cemo naci na sledeci nacin:
, ukoliko njega pokriva neki Top
, ukoliko je on top
Uvek, cim imamo neki cvor koji nije markiran, u njega stavimo Top, markiramo i odtopiramo sve u koje on moze da dodje (BFS, DFS) i idemo dalje...
Na kraju resenje je ...
Dokaz zadnje cinjenice ostavljam za citaoce... :-)

Potpis

Math is like love. A simple idea but it can get complicated.

Ccccccccc...... Andrejko Andrejko..... Prepisujes resenja....... STRASNO! :P:P:P:P

Potpis

I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr

Pa mora od negde da se uci... Mada, nisam se ja bas ni toliko trudio da ga uradim mada je veoma simpatican problem... :-)
Doduse, ja sam nisam provalio... Mada je zadatak sa USACO mnogo laksi jer ti onaj deo pod a) objasni sve...
Inace, u delu pod a) treba da se stampa koliko skup Tops moze imati minimalno elemenata?!

Potpis

Math is like love. A simple idea but it can get complicated.

Ajde ti Vojine meni objasni sta je zadatak?

Napisao si da treba naci najmanji broj grana tako da se iz svakog cvora moze stici u sve ostale??? Sta to treba da znaci?

@cassey Koliko ja vidim ti si ovde objasnio trazenje minimalnog dominirajuceg i kodominirajuceg skupa grafa... Zar ne? Do duse mi smo vec imali neki nesporazum oko znacenja termina dominator grafa... Ti i Srdjan ste tvrdili da je to NP tezak problem, sto u mojoj "verziji" definitivno nije...

Potpis

Don’t do drugs, sleep deprivation is better.

Pa, imas usmeren graf i treba da dodas sto je moguce manje ivica (usmerenih) tako u dobijenom grafu za bilo koja dva svora v i u vazi da postoji put od v do u i obrnuto (tj. da je sam novodobijeni graf jako povezan)...

Hmmm... Neznam da sta ti podrazumevas pod dominatorom... Koliko se ja secam (a pogledacu) dominator je NP problem, e a mozda si ti nesto pobrkao (ili ja)...

Potpis

Math is like love. A simple idea but it can get complicated.

Aha sad sam shvatio...
Pa onda trebamo da dodamo grane iz kodominirajuceg skupa u dominirajuci skup, tj. broj grana koje bi dodali bi bio max (|D|, |KD|), tj u tvojoj terminologiji max (|TOPS|, |BOTTOMS|).... malo kasnije...sad sam video da si ti to isto napisao :)

A sto se tice mog shvatanja dominirajuceg skupa, moguce je da u terminologiji "naseg" jezika dominator ima vise znacenja...

P.S. Vidimo se u petak :)

Potpis

Don’t do drugs, sleep deprivation is better.

Dominator grafa je skup cvorova , takav da je svaki cvor iz skupa V ili sadrzan u D, ili je direktno povezan ivicom sa cvorom iz D (tj. rastojanje svakog cvora do D je najvise 1). I ceo skup V predstavlja validan dominirajuci skup, ali je trazenje dominirajuceg skupa sa manje od k ivica (gde je k zadato) u opstem slucaju definitivno NP problem.

A sto se tice zadatka, treba dodati sto manje ivica tako da graf postane jako povezan.

Potpis

I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr

U Urosivecoj knjizi je drugachije objashnjeno shta su to dominatori. On kaze da je D skup dominatora, ako za svaki chvor v koji pripada grafu, postoji put do chvora koji je u skupu D...

Potpis

mmmmmm.. aahhhhhh..
e, nije sex nego serem!