[es] - Sabotaza najefikasnije?

BIG FOOT

Član broj: 2964
Poruke: 449
*.ptt.yu.

Profil

^{14.06.2005. u 17:47 - pre 229 meseci}

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

Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.11.*

+1 Profil

Re: Sabotaza najefikasnije?

^{22.06.2005. u 20:42 - pre 229 meseci}

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... :-)

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

Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.dial.InfoSky.Net.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..

Profil

Re: Sabotaza najefikasnije?

^{22.06.2005. u 21:19 - pre 229 meseci}

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

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

Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.11.*

+1 Profil

Re: Sabotaza najefikasnije?

^{22.06.2005. u 21:48 - pre 229 meseci}

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?!

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

Odgovor na temu

--SOULMaTe--
Nemanja Skoric
Novi Sad

Član broj: 1464
Poruke: 173
*.pat-pool.nsad.sbb.co.yu.

Profil

Re: Sabotaza najefikasnije?

^{22.06.2005. u 23:10 - pre 229 meseci}

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...

Don’t do drugs, sleep deprivation is better.

Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.11.*

+1 Profil

Re: Sabotaza najefikasnije?

^{22.06.2005. u 23:32 - pre 229 meseci}

Citat:

--SOULMaTe--:
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?

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)...

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

Odgovor na temu

--SOULMaTe--
Nemanja Skoric
Novi Sad

Član broj: 1464
Poruke: 173
*.pat-pool.nsad.sbb.co.yu.

Profil

Re: Sabotaza najefikasnije?

^{23.06.2005. u 00:44 - pre 229 meseci}

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 :)

Don’t do drugs, sleep deprivation is better.

Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.dial.InfoSky.Net.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..

Profil

Re: Sabotaza najefikasnije?

^{23.06.2005. u 09:18 - pre 229 meseci}

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.

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

Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
195.252.87.*

Profil

Re: Sabotaza najefikasnije?

^{23.06.2005. u 14:20 - pre 229 meseci}

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...

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

Odgovor na temu