Probleme de grafuri

Probleme de grafuri:

Se citeste un graf orientat prin introducerea numarului de noduri si a muchiilor (ca pereche de noduri) din fisierul arce.txt, sa se creeze un fisier (matrice.txt) care sa contina pe prima linie numarul de noduri din graf si pe urmatoarele linii matricea de adiacenta.

# include <stdio.h>

# include <conio.h>

/* programul citeste din arce.in numarul de noduri ale grafului

precum si o lista de arce

pe baza eceste liste se creeaza matricea de adiacenta corespunzatoare

care se salveaza ca adiacenta.out

variabile folosite:

n - numarul de noduri din graf

char a[100][100] matricea de adiacenta

i si j indecsi in matricea de adiacenta

f - fisierul de intrare

g - fisierul de iesire

*/

int main(void)

if ((g=fopen('matrice.txt','w'))==NULL)

fscanf f,'%d',&n);

fprintf g, '%dn', n);

while (!feof(f))

fclose f);

printf 'n graful citit are %d noduri!',n);

printf 'n matricea sa de adiacenta este:n');

for(i=0;i<n;i++)

printf 'n');

fprintf g, 'n');

}

fclose g);

getch );

return 0;

}

Se citeste un graf orientat ca matrice de adiacenta din fisierul matrice.txt, sa se creeze un nou graf prin contractia unor noduri (adica 2 noduri adiacente se vor uni intr-un singur nod)

# include <stdio.h>

# include <conio.h>

/* programul citeste din matrice.txt numarul de noduri ale grafului

precum si o matrice de adiacenta.

programul genereaza un fisier contract.txt

variabile folosite:

n - numarul de noduri din graf

char a[100][100] matricea de adiacenta

i si j indecsi in matricea de adiacenta

x si y nodurile care se contacta

f - fisierul de intrare (adiacenta.txt)

g - fisierul de iesire (contract.txt)

*/

int main(void){

int n,a[100][100],i,j,x,y;

FILE *f, *g;

if ((f=fopen('matrice.txt','r'))==NULL)

if ((g=fopen('contract.txt','w'))==NULL)

fscanf f,'%d',&n);

for(i=0;i<n;i++)

for(j=0;j<n;j++)

fscanf f,'%d',&a[i][j]);

fclose f);

printf 'n=%dn',n);

for(i=0;i<n;i++)

printf 'x=');

scanf '%d',&x);

printf 'y=');

scanf '%d',&y);

if(a[x][y]==0) else else

if (i==x)

for(i=x;i<n;i++)

for(j=0;j<n;j++)

a[i][j]=a[i+1][j];

for(i=0;i<n;i++)

for(j=x;j<n;j++)

a[i][j]=a[i][j+1];

n=n-1;

printf 'n matricea de adiacenta corespunzatoare noului graf este:n');

fprintf g, '%dn', n);

for(i=0;i<n;i++)

printf 'n');

fprintf g, 'n');

}

}

fclose g);

getch );

return 0;

}

Se citeste un graf orientat ca matrice de adiacenta din fisierul matrice.txt, sa se afiseze varfurile cu care un varf dat este vecin.

# include <stdio.h>

# include <conio.h>

/* programul citeste din matrice.txt numarul de noduri ale grafului

precum si o matrice de adiacenta.

programul genereaza o lista cu vecinii unui varf dat

variabile folosite:

n - numarul de noduri din graf

char a[100][100] matricea de adiacenta

i si j indecsi in matricea de adiacenta

v - varful pentru care cautam vecinii

f - fisierul de intrare (adiacenta.txt)

g - fisierul de iesire (contract.txt)

*/

int main(void) {

int n,a[100][100],i,j,v;

FILE *f;

if ((f=fopen('matrice.txt','r'))==NULL)

fscanf f,'%d',&n);

for(i=0;i<n;i++)

for(j=0;j<n;j++)

fscanf f,'%d',&a[i][j]);

fclose f);

printf 'n=%dn',n);

for(i=0;i<n;i++)

printf 'v=');

scanf '%d',&v);

printf 'In nodul %d intra arce din nodurile:',v);

for(i=0;i<n;i++)

if (a[i][v]==1)

printf 'n');

printf 'Din nodul %d ies arce in nodurile:',v);

for(i=0;i<n;i++)

if (a[v][i]==1)

getch );

return 0;

}

Se citeste un graf orientat ca matrice de adiacenta din fisierul matrice.txt, sa se determine gradele fiecarui nod precum si cel mai mare grad.

# include <stdio.h>

# include <conio.h>

/* programul citeste din matrice.txt numarul de noduri ale grafului

precum si o matrice de adiacenta.

programul calculaeza gradele interioare si exeterioare pentru fiecare varf in parte

variabile folosite:

n - numarul de noduri din graf

char a[100][100] matricea de adiacenta

structura grad pentru a memora gradele unghiurilor

gr - un tabel cu gradele

i si j indecsi in matricea de adiacenta

minin, minex, maxin, maxex memoreaza minimele si maximele gradelor

f - fisierul de intrare (adiacenta.txt)

*/

struct grad gr[100];

int main(void) {

int n,a[100][100],i,j,minin, minex, maxin, maxex;

FILE *f;

if ((f=fopen('matrice.txt','r'))==NULL)

fscanf f,'%d',&n);

for(i=0;i<n;i++)

for(j=0;j<n;j++)

fscanf f,'%d',&a[i][j]);

fclose f);

for(i=0;i<n;i++)

for(j=0;j<n;j++)

for(i=0;i<n;i++)

minin maxin=gr[0].in;

minex maxex=gr[0].ex;

for(i=1;i<n;i++)

printf 'Grad minim interior=%dn',minin);

printf 'Grad maxim interior=%dn',maxin);

printf 'Grad minim exterior=%dn',minex);

printf 'Grad maxim exterior=%dn',maxex);

getch );

return 0;

}

Se citeste un graf orientat ca matrice de adiacenta din fisierul matrice.txt, Determinati w⁺(A)-multimea arcelor incidente cu A catre exterior, w^- (A)-multimea arcelor incidente cu A catre interior si vecinii lui A, unde A este o submultime de varfuri ale grafului.

# include <stdio.h>

# include <conio.h>

int main(void){

static int n,a[100][100],i,j,m,A[100],k,v[100];

FILE *f;

if ((f=fopen('matrice.txt','r'))==NULL)

fscanf f,'%d',&n);

for(i=0;i<n;i++)

for(j=0;j<n;j++)

fscanf f,'%d',&a[i][j]);

fclose f);

printf 'n=%dn',n);

for(i=0;i<n;i++)

printf 'varfurile subgrafului:n',m);

do

if(A[j]==1)

A[j 1;

} while (1);

printf 'Multimea arcelor incidente catre interior este:');

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if (A[j] && !A[i] && a[i][j]==1) printf('(%d, %d);',i,j);

printf 'n');

printf 'Multimea arcelor incidente catre exterior este:');

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if (!A[j] && A[i] && a[i][j]==1) printf('(%d, %d);',i,j);

printf 'n');

printf 'Multimea vecinilor lui A este:');

for(i=0;i<n;i++)

for(j=0;j<n;j++)

for(i=0;i<n;i++)

if(v[i]) printf('%d ',i);

getch );

return 0;

}

Se citeste un graf orientat ca matrice de adiacenta din fisierul matrice.txt. Verificati daca un graf este neorientat sau total orientat (daca un arc de la nodul x la nodul y nu un arc de la y la x)

# include <stdio.h>

# include <conio.h>

/* programul citeste din matrice.txt numarul de noduri ale grafului

precum si o matrice de adiacenta.

programul verifica daca graful este neorientat adica matricea de adiacenta este simetrica

si verifica daca este total orientat adica nu exista arce neorientate in graf

variabile folosite:

n - numarul de noduri din graf

char a[100][100] matricea de adiacenta

i si j indecsi in matricea de adiacenta

ok - un semafor

f - fisierul de intrare (matrice.txt)

*/

int main(void){

int n,a[100][100],i,j,ok;

FILE *f;

if ((f=fopen('matrice.txt','r'))==NULL)

fscanf f,'%d',&n);

for(i=0;i<n;i++)

for(j=0;j<n;j++)

fscanf f,'%d',&a[i][j]);

fclose f);

printf 'n=%dn',n);

for(i=0;i<n;i++)

ok=1;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if (a[i][j]!=a[j][i])

if (ok==1) printf('n graful este neorientat');

else printf('n graful este orientat!');

ok=1;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if (a[i][j]==1 && a[j][i]==1)

if (ok==1) printf('n graful este total orientat!');

else printf('n graful nu este total orientat!');

getch );

return 0;

}