Acasa Tehnologie Grafuri izomorfe

Grafuri izomorfe

by Dragos Schiopu

>Verifica daca 2 grafuri sunt sau nu izomorfe.

//verifica daca 2 grafuri sunt sau nu izomorfe
#include <stdio.h>
#include <conio.h>
int a[20][20],b[20][20],c[20],n,ok=0;

void afisare(int x[20][20], int dim)
{
int i,j;
printf("Afisare matrice:n");
for(i=1;i<=dim;i++)
{
for(j=1;j<=dim;j++)
printf(" %d ", x[i][j]);
printf("n");
}
}

void tipar (int k)
{
int t=1;
for(int i=1; i<=k;i++)
for(int j=1;j<=k;j++)
if(a[i][j]!=b[c[i]][c[j]]) t=0;
if(t==1) ok=1;
}

int valid (int k)
{
int i, ok=1;
for(i=1;i<=k-1;i++)
if(c[i]==c[k]) ok=0;
return ok;
}

void bktr (int k)
{
int i;
for(i=1;i<=n;i++)
{
c[k]=i;
if(valid (k)==1)
if(k==n) tipar(k);
else bktr(k+1);
}
}

void main()
{
int i,j;
FILE *f=fopen("C:date3.txt","r");
FILE *g=fopen("C:date4.txt","r");

fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
fscanf(f,"%d",&a[i][j]);
fclose(f);
afisare(a,n);

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
fscanf(g,"%d",&b[i][j]);
fclose(g);
afisare(b,n);

bktr(1);
if(ok==1) printf("Izomorf");
else printf("Nu e izomorf!");
getch();
}

date3.txt
5
0 1 0 0 0
1 0 1 1 0
0 1 0 0 0
0 1 0 0 1
0 0 0 1 0

date4.txt
5
0 1 0 0 0
1 0 1 0 1
0 1 0 1 0
0 0 1 0 0
0 1 0 0 0

s-ar putea sa-ti placa