Maksimalno odsecanje

С Википедије, слободне енциклопедије
Maksimalno odsecanje

Za graf, maksimalno odsecanje je odsecanje čija je veličina barem jednaka veličini bilo kog drugog odsecanja. Problem pronalaženja maksimalnog odsecanja u grafu poznat je kao Problem maksimalnog odsecanja.

Problem se može predstaviti na sledeći način. Želimo da pronađemo podskup S skupa čvorova grafa, takav da je broj ivica između čvorova iz S i komplementarnog podskupa što veći mogući.

Naprednija verzija ovog problema zove se težinsko maksimalno odsecanje. U ovoj verziji svakoj ivici pridružen je broj, tj. njena težina, a cilj je postići maksimalnu težinu ivica između S i njegovog komplementa, a ne njihov maksimalan broj. Ovaj problem je često, ali ne uvek, ograničen tako da su težine ivica samo pozitivne vrednosti, zato što negativne vrednosti težina mogu promeniti pripodu samog problema.


Složenost izračunavanja[уреди | уреди извор]

Problem odlučivanja, koji sledi, vezan za maksimalna odsecanja proučava se u okviru teorijske informatike:

Dat je graf G i prirodni broj k, odrediti da li u G postoji odsecanje čija je veličina barem k.

Za ovaj problem je poznato da je NP-kompletan. Lako je videti da je problem u NP: odgovor da je lako dokazati obezbeđivanjem dovoljno velikog odsecanja. NP kompletnost se može pokazati, na primer, transformacijom iz maksimum 2-zadovoljivosti ( koji je restrikcija problema maksimalne zadovoljivosti).[1] Verzija problema odlučivanja sa težinama bila je jedan od Karpovih 21 NP-kompletnih problema;[2] Karp je pokazao NP-kompletnost redukcijom sa problema particionisanja.

Kanonska optimizaciona varijanta gore navedenog problema odlučivanja poznata je kao Problem maksimalnog odsecanja ili Maksimalno odecanje i definisana je kao:

Dat je graf G, pronaći maksimalno odsecanje.

Algoritmi polinomijalnog vremena[уреди | уреди извор]

Pošto je Problem maksimalnog odsecanja NP-težak, nisu poznati uopšteni algoritmi polinomijalnog vremena za ovaj problem.

Međutim, kod planarnih grafova, Problem maksimalnog odsecanja je dual Problemu ispitivanja puta (problem nalaženja najkraće putanje, kojom se svaka ivica grafa posećuje barem jednom), u smislu da su ivice koje ne pripadaju maksimalnom odsecanju grafa G duali ivica koje se ponavljaju u optimalnom ispitivanju puta dualnog grafa grafa G. Optimalno ispitivanje puta formira samopresecajuću krivu koja deli ravan na dva podskupa, podskup tačaka za koje je winding broj krive paran i podskup za koje je taj broj neparan. Ova dva podskupa formiraju odsecanje koje uključuje sve ivice čiji duali imaju neparan broj pojavljivanja u putu. Problem ispitivanja puta se može rešiti u polinomijalnom vremenu, a ova dualnost daje mogućnost da se kod planarnih grafova i Problem maksimalnog odsecanja takođe može rešiti u polinomijalnom vremenu.[3]


Algoritmi aproksimizacije[уреди | уреди извор]

Problem maksimalnog odsecanja je APX-težak,[4] što znači da ne postoji šema aproksimizacije u polinomijalnom vremenu, proizvoljno blizu optimalnom rešenju, za njega, osim u slučaju P = NP. Stoga, svaki algoritam aproksimizacije u polinomijalnom vremenu ima koeficijent aproksimizacije striktno manje od jedan.

Postoji jednostavan nasumični 0,5-algoritam aproksimizacije: za svaki čvor bacanjem novčića utvrditi kojoj ga particiji treba dodeliti.[5][6] Očekujemo da polovina ivica budu ivice odsecanja. Nasumičnost algoritma se može izbeći primenom metoda uslovnih verovatnoća; dakle postoji i jednostavan deterministički 0.5-algoritam aproksimizacije polinomijalnog vremena. [7][8] Jedan takav algoritam počinje sa proizvoljnom particijom čvorova datog grafa i pomera čvorove jedan po jedan, u više koraka, sa jedne strane particije na drugu, poboljšavajući rešenje svakim korakom, sve dok se mogu napraviti poboljšanja ovog tipa. Broj iteracija je najviše zato što algoritam poboljšava odsecanje barem za jednu ivicu svakim korakom. Po završetku algoritma, najmanje polovina ivica vezanih za sve čvorove pripada odsecanju, jer bi inače pomeranje čvorova poboljšalo odsecanje. Stoga odsecanje uključuje najmanje ivica.

Aproksimizacioni algoritam polinomijalnog vremena sa najboljim koeficijentom aproksimizacije je metod Goemans-a i Williamson-a koristeći semidefinitno programiranje i nasumično zaokruživanje koji daje koeficijent aproksimizacije , gde je .[9][10] Ako je unique games pretpostavka tačna, ovo je najbolji mogući koeficijent aproksimizacije za maksimalno odsecanje.[11] Bez takvih nedokazanih pretpostavki, dokazano je da je NP-teško aproksimizovati vrednost maksimalnog odsecanja sa koeficijentom aproksimizacije boljim od .[12][13]

Maksimalni bipartitivni podgraf[уреди | уреди извор]

Odsecanje je bipartitivni graf. Problem maksimalnog odsecanja je u suštini isti kao problem pronalaženja bipartitivnog podgrafa sa najviše ivica.

Neka je graf i neka je bipartitivni podgraf od G. Onda postoji particija (S, T) V takva da svaka ivica u X ima jednu tačku u S a drugu u T. Drugim rečima, postoji odsecanje u H takvo da skup ivica odsecanja sadrži X. Dakle postoji odsecanje u grafu G takvo da je skup ivica odsecanja nadskup od X.

Obrnuto, neka je graf i neka je X skup ivica odsecanja. Onda je math>H=(V,X)</math> bipartitivni podgraf od H.

Ukratko, ako postoji bipartitivni graf sa k ivica, postoji odsecanje sa barem k ivica odsecanja, i ako postoji odsecanje sa k ivica, postoji i bipartitivni graf sa k ivica.

Stoga je problem pronalaženja maksimalnog bipartitivnog podgrafa suštinski isti kao problem pronalaženja maksimalnog odsecanja.[14]

Reference[уреди | уреди извор]

Literatura[уреди | уреди извор]

  • Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco (2003), Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer .
Maximum cut (optimisation version) is the problem ND14 in Appendix B (pp. 399).
Maximum cut (decision version) is the problem ND16 in Appendix A2.2.
Maximum bipartite subgraph (decision version) is the problem GT25 in Appendix A1.2.

Spoljašnje veze[уреди | уреди извор]