Bella: /* Arbore. Pădure */

2020-02-12T08:20:51Z

Arbore. Pădure

New page

= Grafuri neorientate =

=== Definitii ===
Se numește '''graf neorientat''' o pereche ordonată de mulțimi G=(X,U), unde:

* '''X''' este o mulțime finită și nevidă de elemente numite '''vârfuri''' sau '''noduri''';
* '''U''' este o mulțime finită de submulțimi cu două elemente din X, numite '''muchii'''.
Vom nota în continuare vârfurile cu valori între 1 și n – unde n este numărul de vârfuri din graf, iar muchiile cu (x,y) sau [x,y], unde x și y sunt vârfuri și se numesc '''extremitățile muchiei'''.

'''Vecin al unui vârf x''' este orice vârf y cu proprietatea că există muchia (x,y).

'''Varfuri adiacente''' sunt două vârfuri între care există muchie.

'''Muchi incidente''' sunt două muchii care au o o extremitate comună. Un vârf este incident cu o muchie dacă vârful este extremitate a acelei muchii.

Mulțimea muchiilor are proprietatea de simetrie: dacă (x,y) este muchie, atunci și (y,x) este muchie.

Conform definiției:

* într-un graf neorientat nu există muchie de la un vârf la el însuși;
* intre două vârfuri distincte există cel mult o muchie.

Exemplu: Fie G = (X,U), unde:

[[Image:graf-neorientat.png]]

X={1,2,3,4,5,6,7,8,9,10,11}
U={(1,4),(1,5),(2,3),(2,8),(3,11),(4,5),(4,9),(7,10),(8,11)}

=== Gradul unui varf ===
'''Grad al unui vârf''' = numărul de vârfuri adiacente cu acesta (sau numărul de muchii incidente cu acesta). Gradul unui vărf x se notează '''d(x)''' .

'''Observații:'''

* un vârf cu gradul 0 se numește izolat. În graful de mai sus, vârful 6 este izolat.
* un vârf cu gradul 1 se numește terminal. În graful de mai sus, vârful 9 este vârf terminal.
* gradul maxim al unui vârf într-un graf cu n vârfuri este n-1.
'''Teoremă''': Într-un graf neorientat, '''suma gradelor tuturor vârfurilor este dublul numărului de muchii.
'''
'''Consecințe:'''

* Suma gradelor tuturor vârfurilor este număr par.
* Într-un graf neorientat, numărul de vârfuri de grad impar este întotdeauna par.
* Întrebare: Este posibil ca într-un grup de 5 persoane, fiecare persoană să aibă exact 3 prieteni?

== Reprezentarea grafurilor neorientate ==

=== Matricea de adiacență ===
Pentru un graf neorientat '''G = (X,U)''' cu '''n''' vârfuri, matricea de adiacență este o matrice cu n linii și n coloane ce contine elemente din multimee {0,1} astfel:
Ai,j = 1 dacă (i,j) ∈ U - adica exista muchie de la nodul i la nodul j
0 dacă (i,j) ∉ U
Exemplu: Pentru graful neorientat de mai jos avem următoarea matrice de adiacență:

[[Image:graf-neorientat-1.png]]

0 1 0 0 1
1 0 0 0 1
0 0 0 0 0
0 0 0 0 1
1 1 0 1 0

'''Observații:'''

* matricea de adiacență este '''simetrică''' față de diagonala principală;
* elementele de '''pe diagonala principală sunt 0''';
* gradul unui vârf '''x''' este egal cu numărul de elemente 1 de pe linia (sau coloana) x;
* suma tuturor elementelor din matricea de adiacență a unui graf neorientat este egală cu dublul numărului de muchii din graf.

==== [https://www.pbinfo.ro/?pagina=probleme&id=412 Adiacenta] ====
Se dă numarul de noduri '''n''', numarul de muchii '''m''' si lista muchiilor unui graf neorientat. Să se afișeze matricea de adiacență a grafului.

'''adiacenta.in'''
5 8
1 4
1 3
3 5
4 5
2 4
1 2
4 2
3 4
'''adiacenta.out'''

0 1 1 1 0
1 0 0 1 0
1 0 0 1 1
1 1 1 0 1
0 0 1 1 0

<syntaxhighlight>
#include <iostream>
#include <fstream>
using namespace std;

ifstream fin( "adiacenta.in" );
ofstream fout( "adiacenta.out" );

int n, m, x, y;
int a[101][101];

int main(){
fin >> n >> m;
for( int i = 1; i <= m; i++ ){
fin >> x >> y;
a[x][y] = a[y][x] = 1;
}

for( int j = 1; j <= n; j++ ){
for( int i = 1; i <= n; i++ )
fout << a[i][j]<<" ";
fout << '\n';
}

return 0;
}
</syntaxhighlight>

==== [https://www.pbinfo.ro/?pagina=probleme&id=413 Adiacenta1] ====
Se dă lista muchiilor unui graf neorientat. Să se afișeze matricea de adiacență a grafului.

'''adiacenta.in'''
1 4
1 3
3 5
4 5
2 4
1 2
4 2
3 4
'''adiacenta.out'''

0 1 1 1 0
1 0 0 1 0
1 0 0 1 1
1 1 1 0 1
0 0 1 1 0
<syntaxhighlight>
#include <iostream>
#include <fstream>
using namespace std;

ifstream in("adiacenta1.in");
ofstream out("adiacenta1.out");

int n, m, x, y, maxim;
int a[101][101];

int main(){
while( !in.eof() ){
in >> x >> y;
a[x][y] = a[y][x] = 1;
if( x > maxim )
maxim = x;
if(y > maxim)
maxim = y;
}
for( int j = 1; j <= maxim; j++ ){
for( int i = 1; i <= maxim; i++ )
out << a[i][j] << " ";
out << endl;
}
return 0;
}
</syntaxhighlight>

=== Lista de muchii ===
Lista de muchii a unui graf neorientat reprezintă o mulțime ce conține toate muchiile din graf.

[[Image:graf-neorientat-1.png]]

Pentru graful de mai sus, lista de muchii este:

U={[1,2],[1,5],[2,5],[4,5]}

Pentru reprezentarea în memorie putem folosi:

* un tablou unidimensional cu elemente de tip struct {int I,J;}
* două tablouri unidimensionale cu elemente de tip int
* o listă alocată dinamic

=== Lista de adiacențe (de vecini) ===
Pentru un graf neorientat cu '''G=(X,U)''' se va memora numărul de vârfuri '''n''' și apoi, pentru fiecare vârf '''x''', lista vârfurilor adiacente cu '''x''', adică a vârfurilor '''y''' cu proprietatea că există muchia '''(x,y)'''.

Pentru graful alăturat,
[[Image:graf-neorientat-1.png]]

listele de adiacență sunt:
1: 2 5
2: 1 5
3: vidă
4: 5
5: 1 2 4
Ordinea in care nodurile sunt memorate in lista depinde de ordinea in care au fost introduse muchiile. de exemplu, daca prima muchie va fi (4,5) in lista lui 4 primul nod va fi 5 si in lista lui 5 primul nod va fi 4 (daca adaugarea se face la sfarsitul listei, adica fiecare lista este o coada ).

La reprezentarea în memorie trebui avut în vedere că dimensiunile listelor de vecini sunt variabile. De aceea, este neeficientă utilizarea unor tablouri alocate static. Astfel, putem folosi:

* un șir de n liste simplu (dublu) înlănțuite alocate dinamic.
* un șir de n vectori din STL;

==== Implementare cu liste alocate dinamic ====
<syntaxhighlight>
#include <bits/stdc++.h>
using namespace std;
ifstream fin( "listavecini.in" );
ofstream fout( "listavecini.out" );

struct nod {
int info;
nod *adr;
}* L[100];

void adauga ( nod *p, int val ){
nod *c = p;
nod *d = new nod;
d -> info = val;
d->adr = c->adr;
c->adr = d;
p->info ++;
}

void tipar( nod *p ){ // tiparesc lista
while( p ){
fout << p->info << " ";
p = p->adr;
}
fout << "\n";
}
int main() {
int n, i, j, x, y;

fin >> n;
// pe prima poz a fiecarei liste vom pune numarul de elemente, initial 0
for( i = 1; i <= n; i++ ){
L[i] = new nod;
L[i]->info = 0;
L[i]->adr = 0;

}
while ( fin >> x >> y ) {
adauga ( L[x], y ); // in lista lui x adaugam nodul y
adauga ( L[y], x ); // in lista lui y adaugam nodul x
}

for ( i = 1; i <= n; i++ ) {
tipar(L[i]);
}
return 0;
}

</syntaxhighlight>

==== Implementare cu vectori STL ====
<syntaxhighlight>
#include <bits/stdc++.h>
using namespace std;
vector< int > g[100];

int main() {
FILE *fin, *fout;
int n, i, j, x, y, m;
ifstream fin( "listeadiacenta.in", "r" );
ofstream fout( "listeadiacenta.out", "w" );
fscanf( fin, "%d", &n );

// presupunand ca muchiile nu se repeta
while ( fscanf( fin, "%d%d", &x, &y ) == 2 ) {
g[x].push_back( y ); // in lista lui x adaugam nodul y
g[y].push_back( x ); // in lista lui y adaugam nodul x
}

for ( i = 1; i <= n; i++ ) {
fout << g[i].size() << " "; // afisam nr de vecini ai nodului i
for ( j = 0; j < g[i].size(); j++ ) // afisam vecinii nodului i; acestia nu vor fi afisati in ord crescatoare
fout << g[i][j] << " ";;
fout << "\n" ;
}
return 0;
}

</syntaxhighlight>

===Aplicatie: [https://www.pbinfo.ro/?pagina=probleme&id=414 Listavecini]===
===== Liste alocate dinamic =====
<syntaxhighlight>
#include <bits/stdc++.h>
using namespace std;
ifstream fin( "listavecini.in" );
ofstream fout( "listavecini.out" );

struct nod {
int info;
nod *adr;
}* L[100];

void adauga ( nod *p, int val ){
nod *c = p;
nod *d = new nod;
d->info = val;
while( c->adr && c->adr->info <= val ) // parcurg lista pana dau de un element mai mic sau egal cu val
c = c -> adr;
// inserez intre c si c->adr doar daca val e diferita de cea din c
if( c == p || ( c != p && c->info != val ) ){ // daca val nu e in list
d->adr = c->adr; // adaug val intre nodurile c si c->adr
c->adr = d;
p->info ++;
}
}
void tipar( nod *p ){ // tiparesc lista
while( p ){
fout << p->info << " ";
p = p->adr;
}
fout << "\n";
}
int main() {
int n, i, j, x, y;

fin >> n;
// pe prima poz a fiecarei liste vom pune numarul de elemente, initial 0
for( i = 1; i <= n; i++ ){
L[i] = new nod;
L[i]->info = 0;
L[i]->adr = 0;

}
while ( fin >> x >> y ) {
adauga ( L[x], y ); // in lista lui x adaugam nodul y
adauga ( L[y], x ); // in lista lui y adaugam nodul x
}

for ( i = 1; i <= n; i++ ) {
tipar(L[i]);
}
return 0;
}
</syntaxhighlight>
===== Liste implementate cu vectori STL =====
<syntaxhighlight>
#include <bits/stdc++.h>
using namespace std;
vector< int > g[100];

int main() {
int n, i, j, x, y, m;
ifstream fin( "listavecini.in" );
ofstream fout( "listavecini.out" );
fin >> n;

while ( fin >> x >> y ) {
g[x].push_back( y ); // in lista lui x adaugam nodul y
g[y].push_back( x ); // in lista lui y adaugam nodul x
}
/***********************************************************************/
// numai pentru ca muchiile se pot repeta trebuie sa eliminam dublurile
// si pentru ca ni se cere afisarea in ordine a nodurilor, sortam listele de adiacenta
for ( i = 1; i <= n; i++ ){ // daca trebuie sa parcurg vecinii in ordine
sort( g[i].begin(), g[i].end() ); // sortam lista de vecini a nodului i
j = 0;
while (j < g[i].size() - 1 ) // verific lista i sa nu contina dubluri
if( g[i][j] == g[i][j+1] ) // daca am o dublura, pe poz j am acelasi elem ca pe poz j+1
g[i].erase(g[i].begin() + j ); // sterg din lista i elementul de pe poz j
else
j++;
}
/************************************************************************/
for ( i = 1; i <= n; i++ ) {
fout << g[i].size() << " "; // afisam nr de vecini ai nodului i
for ( j = 0; j < g[i].size(); j++ ) // afisam vecinii nodului i
fout << g[i][j] << " ";;
fout << "\n" ;
}
return 0;
}
</syntaxhighlight>

<syntaxhighlight>
/* varianta cu insert sort: listele de adiacenta le vom construi direct sortate;
daca un element mai exista in lista, nu se mai adauga.
*/
#include <bits/stdc++.h>
using namespace std;
vector< int > g[100];
void adauga ( vector <int> &v, int val ){
int p = v.size() - 1; // pornim de la ultimul element al listei
while( p >= 0 && v[p] > val ) // parcurg lista pana dau de un element mai mic sau egal cu val
p --;

if( p == -1 || v[p] != val ) // daca val pe care m-am oprit nu e egala cu cea pe care vreau sa o inserez
v.insert( v.begin()+ p + 1, val ); // adaug val in lista pe pozitia p+1
}

int main() {
int n, i, j, x, y;
ifstream fin( "listavecini.in" );
ofstream fout( "listavecini.out" );
fin >> n;

while ( fin >> x >> y ) {
adauga ( g[x], y ); // in lista lui x adaugam nodul y
adauga ( g[y], x ); // in lista lui y adaugam nodul x
}

for ( i = 1; i <= n; i++ ) {
fout << g[i].size() << " "; // afisam nr de vecini ai nodului i
for ( j = 0; j < g[i].size(); j++ ) // afisam vecinii nodului i
fout << g[i][j] << " ";;
fout << "\n" ;
}
return 0;
}
</syntaxhighlight>

== Graf parțial. Subgraf. Graf complementar ==

'''Definiție'''. Fie G=(X, U) un graf neorientat. Se numeşte '''graf parțial''' al grafului G, graful neorientat G1=(X, U1), unde U1 ⊆ U.

Din definiție rezultă:

Un graf parțial al unui graf neorientat G=(V,U), are aceeaşi mulțime de vârfuri ca şi G, iar mulțimea muchiilor este o submulțime a lui U sau chiar U.
Fie G=(X, U) un graf neorientat. Un graf parțial al grafului G se obține păstrând vârfurile şi
eliminând eventual nişte muchii (se pot elimina şi toate muchiile sau chiar nici una).

'''Definiție.''' Fie G=(X, U) un graf neorientat. Se numeşte '''subgraf''' al grafului G graful neorientat G1=(X1,U1) unde X1 ⊆ X iar U1 conține toate muchiile din U care au extremitățile în X1.

Din definiție rezultă:

Fie G=(X,U) unraf neorientat. '''Un subgraf''' al grafului G, se obține ştergând eventual anumite
vârfuri şi odată cu acestea şi muchiile care le admit ca extremitate (nu se pot şterge toate vârfurile deoarece s-ar obține un graf cu mulțimea vârfurilor vidă).

'''Definiție.''' Fie G=(X, U) un graf neorientat. Se numeşte '''graf complementar''' al grafului G, graful neorientat G1=(X, U1), cu proprietatea că două vârfuri x și y sunt adiacente în G1 dacă și numai dacă nu sunt adiacente în G.

'''Graf initial''':

[[Image:graf-neorientat-2.png]]

'''Graf partial, subgraf, graf complementar:'''

[[Image:graf-neorientat-2-graf-partial.png]]
[[Image:graf-neorientat-2-subgraf.png]][[Image:graf-neorientat-2-complementar.png]]

Observații. Un graf neorientat oarecare poate avea mai multe grafuri parțiale și subgrafuri, dar un unic graf complementar. Mai precis:

Teoremă: Fie G un graf neorientat cu n vârfuri și m muchii. Atunci:

* graful G admite '''2m grafuri parțiale'''; ( cate submultimi ale multimii muchiilor )
* graful G admite '''2n–1 subgrafuri'''; ( cate submultimi ale multimii nodurilor, mai putin submultimea vida )
* graful G admite un unic graf complementar.
Justificare:

Să ne amintim că o mulțime cu a elemente are 2a submulțimi, inclusiv mulțimea vidă și mulțimea inițială. Atunci:

*orice submulțime a mulțimii muchiilor induce un graf parțial. Sunt m muchii, deci 2m submulțimi, deci tot atatea grafuri parțiale.
*orice submulțime a mulțimii vârfuri induce un subgraf, mai puțin mulțimea vidă – un graf nu poate avea 0 vârfuri. Similar ca mai sus, sunt 2n–1 subgrafuri.
*graful complementar este unic determinat, deoarece complementara unei submulțimi față de o mulțime dată este unic determinată.

== Graf nul. Graf complet. Graf regulat ==
'''Definiție:''' Un graf neorientat se numește '''graf nul''' dacă mulțimea muchiilor este vidă.

Într-un graf nul toate vârfurile sunt izolate.

Definiție. Fie G=(X, U) un graf neorientat. Graful G se numește '''graf complet''' dacă oricare două vârfuri
distincte ale sale sunt adiacente. Un graf complet cu n vârfuri se notează Kn.

Exemplu: Graful următor este graful '''K5'''.

[[Image:graf-neorientat-complet.png]]

Într-un graf complet cu n vârfuri sunt C2n = n∗(n−1)/2 muchii și fiecare vârf are gradul n-1.

Propoziție: Sunt 2n∗(n−1)/2 grafuri neorientate distincte cu n vârfuri.

Definiție: Un graf în care toate nodurile au acelaşi grad se numește graf regulat.

Exemplu: Graful de mai jos este regulat.

== Arbore. Pădure ==
'''Definiție:''' Se numește arbore un '''graf conex și aciclic'''.

'''Exemplu''': Graful următor este arbore:

[[Image:graf-arbore.png]]

Observații:

Un arbore cu '''n''' vârfuri are '''n-1''' muchii.
Un arbore este un graf conex și minimal cu această proprietate; dacă s-ar mai elimina o muchie, graful nu ar mai fi conex.
Un arbore este un graf aciclic și maximal cu această proprietate; dacă s-ar mai adăuga o muchie, s-ar obține un ciclu.
Un graf parțial care este arbore se numește arbore parțial.

'''Definiție:'''Un graf care nu conține cicluri se mai numește '''pădure'''. Într-o pădure fiecare componentă conexă este arbore.

== Laborator ==
* [https://www.pbinfo.ro/probleme/2707/matad matad]
* [https://www.pbinfo.ro/probleme/416/grade grade]
* [https://www.pbinfo.ro/probleme/430/izolate izolate]
* [https://www.pbinfo.ro/probleme/417/gradmax gradmax]
* [https://www.pbinfo.ro/probleme/418/subgraf subgraf]
* [https://www.pbinfo.ro/probleme/419/subgraf1 subgraf1]

Clasa a XI-a lecția 13 - Revision history

Bella: /* Arbore. Pădure */