Pentru a intelege aceasta problema, trebuie sa stii ce este o matrice de adiacenta. Matricea de adiacenta este o matrice patrata nxn, unde n este numarul de noduri din graf si fiecare element din matrice Aij are doua valori:
0-daca nu exista o muchie intre nodurile i,j(daca j=i atunci Aii intotdeauna este 0)
1-daca exista o muchie intre nodurile i si j
pentru ca Aij si Aji reprezinta legaturile intre nodurile i si j, aceste valori sunt egale in cazul grafurilor neorientate, din moment ce acolo directia nu conteaza.
Un nod izolat nu are muchii de legatura cu nici un alt nod. Sa zicem ca nodul i este un nod izolat. Atunci Aij=0, indiferent valoarea lui j. Atunci suma elementelor de forma Aij va fi 0
Un nod terminal are o singura muchie de legatura cu alt nod. Sa zicem ca nodul k ar fi un nod terminal.Atunci suma valorilor de tip Akj va fi 1, din moment ce o singura valoare j corespunde unui nod care se leaga de nodul k. Asadar, poti face un program care sa foloseasca asta pentru a vedea aceste noduri.
Am inclus un fisier ce arata un graf cu un nod izolat: 4 si un nod terminal: 6
Matricea de adiacenta pentru graf este:
0 1 0 0 0 1 0
1 0 1 0 1 0 1
0 1 0 0 0 0 1
0 0 0 0 0 0 0
0 1 0 0 0 0 1
1 0 0 0 0 0 0
1 1 1 0 1 0 0
Si observi ca pe linia 4 ai numai 0, si pe linia 6 ai o singura valoare de 1, pe restul ai cel putin doua valori de 1, deci nu sunt noduri izolate sau terminale
Bun, acum acesta e codul:
#include <iostream>
using namespace std;
int main(){
int adiacenta[20][20],terminale[20],izolate[20];
int n,i,j,muchii,nr_nod_term=0,nr_nod_izolate=0;
cout<<"Introduceti nr de noduri: ";
cin>>n;
cout<<"Introduceti matricea de adiacenta a grafului: \n";
for (i=0;i<n;i++){
for(j=0;j<n;j++){
cin>>adiacenta[i][j];
}
}
for(i=0;i<n;i++){
muchii=0;
for(j=0;j<n;j++){
if(adiacenta[i][j]>0){
muchii++;
}
}
if(muchii==0){
izolate[nr_nod_izolate]=i+1;
nr_nod_izolate++;
}
else if(muchii==1){
terminale[nr_nod_term]=i+1;
nr_nod_term++;
}
}
if(nr_nod_term==0){
cout<<"Nu exista noduri terminale\n";
}
else{
cout<<"Noduri terminale: ";
for(i=0;i<nr_nod_term;i++){
cout<<terminale[i]<<" ";
}
}
if(nr_nod_izolate==0){
cout<<"Nu exista noduri izolate\n";
}
else{
cout<<"Noduri izolate: ";
for(i=0;i<nr_nod_izolate;i++){
cout<<izolate[i]<<" ";
}
}
return 0;
}
