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

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 ?

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.

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.