Grafuri neorientate – euleriene

Fiind dat un graf neorientat, să se determine dacă este eulerian, iar dacă răspunsul este afirmativ, să se determine toate ciclurile euleriene care încep dintr-un nod dat.

Pentru a rezolva această problemă, vom parcurge următorii paşi:
• se determină dacă graful este conex
• se determină dacă fiecare nod are grad par


#include "stdio.h"
#include "conio.h"
int a[10][10],viz[10],n,m;
//parcurgere in adâncime
void df_r(int nod)
{
  int k;
  //afişăm nodul curent ca vizitat
  printf("%d ",nod);
  //marcăm nodul curent ca vizitat
  viz[nod]=1;
  //pentru fiecare nod k
  for(k=1;k <= n;k++)     //dacă există muchie între nodul curent şi nodul k şi nodul k nu a fost incă vizitat,     //apelăm funcţia recursivă de vizitare depth first df_r având ca parametru nodul k     if(a[nod][k] && !viz[k])       df_r(k); }

void main()
{
  int x,y,in,nr_n_viz=0,par=0,grad,i,j;
  printf("Introdu nr de noduri:");
  scanf("%d",&n);
  printf("Introdu nr de muchii:");
  scanf("%d",&m);
  for(i=1;i <= n;i++)     for(j=1;j <= n;j++)       a[i][j]=0;   for(i=1;i <= m;i++)   {     printf("De la nodul:");     scanf("%d",&x);     printf("la nodul:");     scanf("%d",&y);     a[x][y]=a[y][x]=1;   }   printf("Introdu nodul de la care se porneşte:");   scanf("%d",&in);   df_r(in);   for(i=1;i <= n;i++)     nr_n_viz+=viz[i];   //verificăm dacă graful este conex contorizând numărul nodurilor vizitate   if(nr_n_viz!=n)     //dacă numărul nodurilor vizitate nu este egal cu numărul total de noduri     printf("Graful nu e conex! \n");   else   {     printf("Graful este conex!\n");     //determinăm dacă toate nodurile au gradele pare     for(i=1;i <= n;i++)     {       grad=0;       for(int j=1;j <= n;j++)         grad+=a[i][j];       if(grad%2 != 0)         par=1;     }     if(par)       printf("Exista noduri cu grade impare !\n");     else       printf("Avem un graf eulerian!\n");   }   getch(); }

Leave a Reply

Your email address will not be published. Required fields are marked *

20 − 3 =

Time limit is exhausted. Please reload CAPTCHA.