Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  


AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Graf partial si subgraf

c

+ Font mai mare | - Font mai mic





DOCUMENTE SIMILARE

Trimite pe Messenger
Operatori si expresii - Instructiunea de atribuire
LISTE - Sortare prin selectie
Controlling the Groups: AddToGroup, CreateGroup
O colectie de programe utile
Intrari/iesiri in C/C++
crearea unei liste liniare si determinarea primului element par
Instructiunea alternativa (IF)
Tipuri de date predefinite
Functii virtuale si polimorfism
Tablouri

TERMENI importanti pentru acest document

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.






Politica de confidentialitate



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1725
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2022 . All rights reserved

Distribuie URL

Adauga cod HTML in site