Graf partial si subgraf

Graf partial si subgraf

Se citesc de la tastatura m perechi de numere intregi reprezentand extremitatile muchiilor unui graf neorientat G cu n varfuri si m muchii si m1 perechi de numere intregi reprezentand extremitatile muchiilor unui graf neorientat G1 cu n1 varfuri si m1 muchii. Sa se verfice daca G1 este graf partial al lui G.

#include <iostream.h>

int a[20][20],gp[20][20],n,m,n1,m1;

void citire_graf(int a[20][20],int n,int m)

void afisare_matrice(int a[20][20],int n)

int verificare()

void main()

Fie un graf neorientat G cu n varfuri a carui matrice de adiacenta se citeste de la tastatura. Multimea m de numere intregi retine varfurile unui graf G1 pentru care se citesc extremitatile muchiilor de la tastatura si se construieste vectorul de muchii. Sa se verifice daca G1 este subgraf a lui G.

#include<iostream.h>

struct muchie;

typedef struct muchie muchie;

int a[50][50];

muchie v[50];

int n,nm,nn;

int m[50];

void citire_graf()

void citire_subgraf()

cout<<'Introduceti numarul de muchii al subgrafului:';

cin>>nm;

cout<<'Introduceti muchiile subgrafului:';

for(int i=1;i<=nm;i++)

int verificare()

void main()

Pentru un graf G cu n varfuri si un numar natural p dat, sa se construiasca un subgraf al lui G avind exact p varfuri. Se vor preciza varfurile si muchiile subgrafului determinat.

Solutie: Se construieste o multime, fie aceasta A, care initial contine extremitatile primei muchii. Mai folosim o multime, fie aceasta B, care initial contine indicii tuturor muchiilor cu exceptia primeia. Se adauga treptat in A cate un varf y cu proprietatea ca exista o muchie care trece prin y si cealalta extremitate a acestei muchii se gaseste deja in A. Pe masura ce gasim o astfel de muchie, o scoatem din multimea B. La sfarsit se enumera varfurile din A si muchiile care au ambele extremitati in A.

#include<iostream.h>

struct muchie;

typedef struct muchie muchie;

int a[50],b[50];

int n,p,m,na,nb;

muchie v[100];

void citire_graf()

void subgraf()

nr=2;

do

else

if(v[j].y==i)

j++;

}

}

i++;

}

}

while(nr!=p);

//Adauga subgrafului toate muchiile care au ambele extremitati in multimea sa de varfuri a

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

}

}

void tipar_subgraf()

cout<<'Muchiile subgrafului:';

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

void main()

Tema:

Sa se scrie un program care pentru un graf dat G cu n varfuri si un numar natural k, sa se determine subgraful G1 cu un numar maxim de varfuri si cu proprietatea ca orice varf al sau are gradul cel putin k. In cazul in care problema nu are solutie sa se scrie un mesaj corespunzator.

Sa se rezolve toate cele trei problemele de mai sus, insa se va folosi reprezentarea grafurilor sub forma de liste de adiacenta.