# Algoritmiii Ford Fulkerson si Edmonds-Karp
** UVA 10735
** PKU 2391

# Algoritmul lui Dinic

# Algoritmul lui Dinic si algoritmul lui Karzanov
** "Tero":http://infoarena.ro/problema/tero

# Taietura minima in graf / conexiune de muchii
** Hardware Store
** SPOJ Optmark

** 'Drumuri2':problema/drumuri2
** Joc (finala .campion 2006)
# Cuplaj in graf bipartit

** SGU 234, 190

# Algoritm de flux maxim pentru cuplaj
** CEOI 2002 Guards
** PKU 2226

** PKU 3189
# Algoritmul Hopcroft-Karp
** 'Java':problema/java

** Baltica 2001 Knights

# Suport in graf bipartit
** 'Felinare':problema/felinare
** SGU 234

          mareste fluxul f de-a lungul drumului p
      returneaza f
==

 
Ce este un drum de ameliorare? Un drum de ameliorare este un drum de la sursa la destinatie care are proprietatea ca fiecare muchie are cap[i]-flux[i] > 0,
sau mai bine zis, "se mai poate pompa lichid prin conductele ce compun drumul".
 
Conform acestei metode se poate implementa un algoritm cu o complexitate ce depinde de capacitati (marim fluxul cu o unitate la fiecare pas).
 
Edmonds si Karp au dat urmatorul algoritm ce are complexitate O(N *M^2):
Drumul de ameliorare il vom determina folosind un BFS (cautare in latime) si in loc sa marim fluxul cu o singura unitate, vom mari fluxul cu valoarea minima dintre capacitatile de pe drumul de amelioarare. Se observa intuitiv ca dupa saturarea unui drum de ameliorare se satureaza cel putin o muchie. Dupa O(M) saturari de drumuri se observa ca cel mai scurt drum de la sursa la destinatie trebuie sa creasca. Asadar dupa O(N*M) astfel de operatii destinatia nu va mai fi accesibila din sursa si prin urmare avem fluxul maxim. Cum fiecare operatie (din cele O(N*M) ) au complexitate O(M+N) (BFS) rezulta complexitatea finala O(N* M^2).
 
 
==code(c) |
#include <cstdio>
#define N 128
#define oo 0x3f3f3f3f //infinit
int cap[N][N], flux[N][N];
int t[N];
int n, m;
 
int bfs (int source, int sink)
{
	int Q[N + 1], p = 0, q = 0;
	bool use[N];
	memset (use, 0, sizeof (use));
	memset (t, 0, sizeof (t));
	Q[0] = source;
	use[source] = 1;
 
	while (p <= q)
	{
		int u = Q[p++]; //scoatem primul element din coada
 
		for (int i = source;i <= sink;++i) // pt fiecare nod ( adiacent )
			if (!use[i]) // nu am folosit nodul
				if (cap[u][i] - flux[u][i] > 0) // mai putem pompa?
				{
					Q[++q] = i; // inseram nodul i in coada
					t[i] = u;
					use[i] = 1;
				}
	}
 
	if (t[sink])
             return 1;
	return 0;
}
 
int edmond-karp (int source, int sink)
{
	int flow = 0; //fluxul
	int i, min;
 
	while (bfs (source, sink)) // cat timp mai exista un drum de ameliorare
	{
		min = oo;
		for (i = sink; i; i = t[i])
			if (cap[ t[i] ][i] - flux[ t[i] ][i] < min)
                               min = cap[ t[i] ][i] - flux[ t[i] ][i];
                //calculam minimul dintre capacitatile ramase de pe drum
 
		for (i = sink ; i; i = t[i])
			flux[ t[i] ][i] += min, //adaugam minimul la fluxul de pe arcele de pe drum
			flux[i][ t[i] ] -= min; //scadem minimul de pe arcele inverse
 
		flow += min; // adaugam minimul la flux
	}
      return flow;
}
 
==
 
 
h2. 2. Algoritmul lui Dinic si algoritmul lui Karzanov
 
h3. Algoritmul lui Dinic
 
In cadrul fiecarui ciclu while al algoritmului Edmond-Karp determinam un singur drum de ameliorare. In cadrul algoritmului lui Dinic se determina nu un singur drum, ci un numar maximal (nu neaparat maxim) de drumuri de ameliorare. Practic ne uitam la nodurile adiacente destinatiei si daca se poate ajunge in destinatie din acel nod atunci saturam drumul respectiv.
 
== code(c) |
int dinic(int source, int sink)
{
	int flow=0; //fluxul
	int i, min,j;
 
	while(bfs(source, sink)) // cat timp mai exista un drum de ameliorare
	{
 
		for(j=source;j<sink;++j)
			if(cap[j][sink]-flux[j][sink] > 0)
			{
 
				min=oo;
 
				if(cap[j][sink]-flux[j][sink] < min) min=cap[j][sink]-flux[j][sink];
 
				for(i=j; i; i=t[i])
					if(cap[t[i]][i]-flux[t[i]][i] < min) min=cap[t[i]][i]-flux[t[i]][i];
 //calculam minimul dintre capacitatile de pe drum
 
				if(min == oo) continue;
 
				flux[j][sink]+=min;
				flux[sink][j]-=min;
 
				for(i=j ; i; i=t[i])
					flux[t[i]][i]+=min, //adaugam minimul la fluxul de pe arcele de pe drum
					flux[i][t[i]]-=min; //scadem minimul de pe arcele inverse
 
				flow+=min; // adaugam minimul la flux
			}
	}
     return flow;
}
==
 
h2. Grafuri bipartite
 Cuplaj maxim, Multime independentă maximală, Suport minim
 
 
 
 
 
Un graf bipartit este un graf G = (V, E) în care mulţimea V poate fi partiţionată în două mulţimi, V1 şi V2 astfel încât orice muchie (u, v) C E implică fie că u C V1 şi v  C V2 fie că u C V2  şi v C V1. Cu alte cuvinte, toate muchiile merg de la mulţimea V1 la mulţimea V2 sau invers.
 
Proprietăţile grafurilor bipartite sunt:
1.	G este 2-colorabil (adică nodurile pot fi colorate în 2 culori astfel încât orice muchie sa aiba noduri colorate diferit)
2.	G nu are cicluri de lungime impară
 
În grafurile bipartite anumite probleme care erau NP pe grafuri normale, se pot rezolva în timp polinomial. Exemple de astfel de probleme sunt: cuplaj maxim, mulţime independentă maximală şi suport minim.
 
h3. Cuplaj Maxim
 
Fiind dat un graf neorientat G = (V, E),  un cuplaj este o submulţime de muchii M astfel încât pentru toate vârfurile v  C V, există cel mult o muchie în M incidentă în v. Spunem că un vârf v C V este cuplat de cuplajul M dacă există cel mult o muchie în M incidentă în v; altfel spunem ca v este neconectat. Un cuplaj maxim  este un cuplaj de cardinalitate maximă.
 
 !flux-si-cuplaj?cuplaj1.jpg!
 
În imagine: un graf bipartit G = (V, E) cu partiţia vârfurilor V = L U R. (a) Un cuplaj de cardinalitate 2. (b) Un cuplaj maxim de cardinalitate 3.
 
Pentru a determina cuplajul maxim vom transforma graful bipartit într-o reţea de transport adaugând un nod sursa (s)si un nod destinaţie (t) şi vom pune capacitate 1 pe toate muchiile.
 
Reţeaua de transport corespunzătoare grafului de mai sus:
 
 !flux-si-cuplaj?cuplaj2.jpg!
 
Cuplajul maxim va fi chiar fluxul maxim în această reţea. Nu ne rămâne decât să rulăm unul din algoritmii cunoscuţi precum Edmonds-Karp, Dinic… Complexitatea obţinută va fi O(V *  E) deoarece orice cuplaj în graful bipartit are cardinalitate cel mult min(V1, V2).
 
Un algoritm performant pentru determinarea cuplajului maxim este Algoritmul Hopcroft-Karp. Acest algoritm în loc să determine un singur drum de ameliorare la fiecare pas, el determină un numar maximal (nu neapărat maxim) de drumuri distincte. Astfel se poate demonstra că numarul de paşi necesari este cel mult sqrt(V) . Prin urmare complexitatea va deveni O(E*sqrt(V)).
 
 
h2. 10. Suport Minim
 
Într-un graf bipartit un suport minim reprezintă o mulţime de noduri cu cardinal minim pentru care orice muchie a grafului este adiacentă cu cel puţin unul dintre nodurile mulţimii. Conform Teoremei lui Koning într-un graf bipartit cuplajul maxim şi suportul minim sunt egale.
Pentru a calcula suportul minim vom porni de la un cuplaj maxim. Nodurile din prima mulţime care aparţin cuplajului vor fi incluse în suportul minim, iar pentru cele care nu aparţin cuplajului vom folosi o funcţie recursiva care în momentul în care gaseşte o muchie care nu are cel puţin un nod în suport, adauga nodul din V2 şi şterge nodul din stânga cu care este cuplat nodul respctiv şi apelează recursiv pentru nodul din stânga.
 
 
Funcţia recursiva arata astfel:
 
 
== code(c) |
void support(int n)
{
    vector<int>::iterator it;
 
    for(it=a[n].begin(); it!=a[n].end(); ++it)
    //pentru fiecare nod *it(din dreapta) adiacent lui n
	if(!sr[*it]) // daca nu e in suport
	{
	    sr[*it]=1;  // il adaug in suport
	    sl[l[*it]]=0;
    // sterg din suport nodul din stanga cu care este cuplat *it
	    support(l[*it]); // apelez recursiv pentru nodul din stanga
	}
}
 
==
 
h2. Mulţime independentă maximală
 
Într-un graf bipartit o mulţime independentă maximală reprezintă o mulţime de noduri astfel încât oricare 2 noduri din mulţime să nu fie legate printr-o muchie iar orice muchie din graf să aiba unul din noduri în mulţimea independentă.
O proprietate interesantă a unei mulţimi independente maximale este aceea că ea este fie o clică maximală fie un subgraf complet în graful complementar.
Mulţimea independentă maximală este complementul oricărui suport minim în sensul că daca avem un suport minim, o mulţime independentă maximală va fi formată din nodurile care nu aparţin suportului minim.