Taietura minima in graf cu costuri

(Categoria Grafuri, Autor Andrei Grigorean)

Articolul de fata isi propune sa studieze problema gasirii unei taieturi minime intr-un graf neorientat cu costuri. Algoritmul prezentat este simplu atat ca implementare, cat si ca demonstrare a corectitudinii, iar timpul sau de executie este la fel de bun ca al oricarui algoritm cunoscut pana in momentul de fata.

Introducere

Conectivitatea este una din problemele clasice in teoria grafurilor, avand multe aplicatii practice, iar gasirea unei taieturi minime intr-un graf cu costuri este fundamentala in algoritmica. Pentru a fi mai precisi, ea consta in partitionarea unui set de noduri in doua multimi nevide, astfel incat suma costurilor muchiilor dintre cele doua multimi sa fie minima. Metodele clasice de abordare a acestei probleme sunt in stransa legatura cu gasirea unui flux maxim intr-o retea de transport. Ford si Fulkerson [1956] au enuntat teorema flux maxim - taietura minima, care arata dualitatea dintre fluxul maxim al unei retele de transport si taietura minima ce poate fi facuta astfel incat sursa si destinatia retelei sa se afle in multimi diferite. Gasirea unei taieturi minime fara sa fie specificate 2 noduri care sa se afle in multimi diferite, se poate face fixand un nod sursa, iar destinatia luand pe rand toate valorile diferite de sursa, in final alegandu-se optimul.