Noduri critice intr-un graf

Folosind algoritmul pentru nodurile critice :

Considerăm că avem un graf (neorientat și conex) cu N noduri si M muchii. Un nod al grafului se numește critic dacă prin eliminarea lui din graf (și a muchiilor adiacente cu acest nod), graful nu mai rămâne conex. Ne punem problema de a determina care sunt nodurile critice ale unui graf (aceasta este o problemă care apare des în practică, deoarece multe structuri pot fi modelate cu ajutorul grafurilor, iar nodurile critice pot reprezenta punctele vulnerabile ale acestor structuri).

Pași de execuție

Se face o parcurgere DF dintr-un nod oarecare al grafului, pe care îl vom numi în continuare nod rădăcină. Știm că o parcurgere DF determină un arbore parțial de acoperire al grafului, având rădăcină în nodul rădăcină. În cadrul parcurgerii, vom calcula nivelul pe care se află fiecare nod (nivelul rădăcinii este 1, iar nivelul fiecărui nod este egal cu nivelul nodului tată plus 1). Ca urmare a unei parcurgeri DF, muchiile grafului pot fi împărțite în două categorii : muchii ce fac parte din arborele DF (muchii înainte sau muchii directe) și muchii ce nu fac parte din acest arbore (muchii de întoarcere, muchii înapoi sau muchii inverse). Pentru fiecare nod vom calcula, pe langa nivelul acestuia, și nivelul minim la care poate ajunge nodul respectiv mergând numai pe muchii directe din subarborele său din cadrul arborelui DF și folosind ca ultima muchie o muchie inversă. Acestă valoare, pe care o vom numi nivelul minim accesibil este egală cu minimul dintre urmatoarele 3 valori :

• nivelul nodului curent
• minimul dintre nivelurile nodurilor cu care este legat nodul curent printr-o muchie inversă
• minimul dintre nivelurile minime accesibile ale fiiilor nodului curent din cadrul arborelui DF

Se poate observa ușor că un nod (diferit de rădăcină) este critic dacă are cel puțin un fiu pentru care nivelul minim accesibil este mai mare sau egal cu nivelul nodului. Rădăcina este nod critic dacă are cel puțin 2 fii.

=== Implementare in C ===

#include "stdio.h"

int n, a[20][20], viz[20];

void citire()
{ FILE * f = fopen("neorientat","r");
fscanf(f,"%d", &n); int i,j;
while(!feof(f))
{ fscanf(f,"%d %d", &i, &j);
a[i][j]=1; a[j][i]=1;
a[i][i]=1; a[j][j]=1; }
}

/* Determinarea nodurilor critice pt graf neorientat */

void df(int vf)
{ int i; viz[vf]=1;
for(i=1; i<=n; i++)
if(a[vf][i]==1 && viz[i]==0)
df(i);
}

int conex()
{ int i, p=0;
for (i=1; i<=n; i++)
if(viz[i]==0)
{ df(i); p++; }
if(p==1)
return 1;
return 0;
}


int main()
{ int i,j;
citire();
printf("Noduri critice: ");
for(i=1;i<=n;i++) //elimin fiecare nod
{ for(j=1;j<=n;j++)
if(a[i][j]==1)
{ a[i][j]=2; a[j][i]=2; }
if(i==n)
df(i-1);
else
df(i+1);
if(!conex())
printf("%d ", i) ;
for(j=1;j<=n;j++)
if(a[i][j]==2)
{ a[i][j]=1; a[j][i]=1; }
for(j=1;j<=n;j++)
viz[j]=0;
}
printf("\n");
return 0;
}