[es] - Cepanje najbolje?

BIG FOOT

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

Profil

Cepanje najbolje?

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

U grafu treba pronaći minimalan broj čvorova, čijim brisanjem tačke A i B postaju odvojene. (cepanje). Kako?

Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.10.*

+1 Profil

Re: Cepanje najbolje?

^{14.06.2005. u 18:46 - pre 229 meseci}

Hmmm... Samo prvo moras da mi das ogranicenje za broj cvorova da bi znao u kom opsegu da trazim. Ja sam prethodnih dana resavao (i resio) slican problem, gde treba da izbacis sto manje ivica da cvorovi A i B budu nepovezani. Verujem da je i ovo nesto slicno, mada sad nemam vremena da razmislim, pa cu ti se javiti veceras.
A odakle je zadatak?!

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
*.rcub.bg.ac.yu.

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

Profil

Re: Cepanje najbolje?

^{14.06.2005. u 20:05 - pre 229 meseci}

Ovaj problem se zove "minimum node cut" problem. Svodi se na network flow algoritam. Postupak je sledeci:

Napravis od datog neusmerenog grafa usmereni, tako sto svaku ivicu pretvoris u dve nove, po jednu za svaki smer. Svakoj od tih ivica dodelis beskonacnu (tj. dovoljno veliku) tezinu. Sada svaki cvor iscepas na dva nova, ulazni i izlazni, tako da u ulazni samo ulaze ivice, a iz izlaznog samo izlaze. Ova dva nova cvora povezes u oba smera, i svakoj od te dve ivice dodelis vrednost 1. Sada obelezis izlazni A cvor kao source i ulazni B kao sink, i pustis network flow algoritam (vidi top temu). Rezultat je bas minimum node cut. Nadam se da je i jasno zasto ?

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

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249

+96 Profil

Re: Cepanje najbolje?

^{15.06.2005. u 10:24 - pre 229 meseci}

Jel' može ovako: Prvo pronađemo sve moguće različite putanje koji vode iz A u B. Dobijemo skup uređenih n-torki različitih veličina. Sada sve što treba da uradimo je da pronađemo minimalan skup tačaka takvih da je presek sa svakom n-torkom različit od praznog skupa. Bez mnogo razmišljanja ovde bih ubacio grubu silu, tj. isprobavanje svake moguće kombinacije.

Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.10.*

+1 Profil

Re: Cepanje najbolje?

^{15.06.2005. u 12:27 - pre 229 meseci}

Pa, to se otprlike svodi na ovo sto je Srki objasnio, samo sto on ne primenjuje "grubu silu". To trazenje razlicitnih puteva je u stvari Flow...

Da, ja se izvinjavam kada sam rekao da sam radio slican zadatak kada treba da izaberes sto je manje ivica tako da cvorovi A i B budu nepovezani. Naravno to je MinCut. Nego zadatak glasi ovako:

Treba obojiti sve ivice u grafu, tako da je ukupan broj boja max, pri cemu je ispunjen uslov: ukoliko se izbace ivice bilo koje (jedne) od boja, cvorovi A i B postaju nepovezani.

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

Odgovor na temu