Clasa a XI-a lecția 13

From Algopedia
Revision as of 08:20, 12 February 2020 by Bella (talk | contribs) (→‎Arbore. Pădure)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

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:

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ță:

File: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.

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 
#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;
}

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 
#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;
}

Lista de muchii

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

File: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, File: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

#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;
}

Implementare cu vectori STL

#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;
}

Aplicatie: Listavecini

Liste alocate dinamic
#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;
}
Liste implementate cu vectori STL
#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;
}
/* 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;
}

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:

Graf partial, subgraf, graf complementar:

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.

Î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:

File: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