DETERMINAREA CENTRULUI UNUI GRAF ORIENTAT

Se presupune ca se da graful orientat ponderat G=(N,A) si se cere sa se determine cel mai central nod al sau.

Pentru a defini termenul de "cel mai central nod" trebuie definit termenul de "excentricitate " a unui nod.

Excentricitatea unui nod x apartinand lui N este :max {drumurile minime de la y la x}, unde y apartine lui N. Centrul unui graf G este nodul a carui excentricitate este minima.

Utilizand algoritmul lui Floyd, determinarea centrului unui graf G se poate realiza simplu.Presupunand ca COST este matricea ponderilor arcelor grafului, se procedeaza astfel :

1.Se determina cu ajutorul procedurii Floyd matricea drumurilor minime corespunzatoare tuturor perechilor de noduri.

2.Se determina excentricitatile nodurilor i,gasind valoarea maxima de pe fiecare coloana i a matricei.

3.Se cauta nodul cu excentricitatea minima.Acesta este centrul grafului G.