Teoria Grafurilor – Reprezentarea grafurilor

Definitii

Matricea de adiacenta este o matrice a cu n linii si n coloane, in care elementele a[i, j], se definesc astfel:
a[i, j] = { 1, daca ∃ muchia [i, j], unde i ≠ j
a[i, j] =   0, in caz contrat }

Lista vecinilor nodului x cuprinde toate nodurile care sunt extremitati ale muchiilor ce trec prin nodul x.

Elemente de teorie

Reprezentari

O metoda de reprezentare a unui graf neorientat foarte folosita este matricea de adiacenta. Aceasta are proprietatea ca a[i, j] = a[j, i] oricare ar fi i, j ∈ {1, 2, 3, …, n}, cu i ≠ j. Adica matriea de adiacenta a este simetrica fata de diagonala principala.

Fiecare muchie a grafului poate fi privita ca o inregistrare cu doua componente: cele doua varfuri care constituie extremitatile muchiei. Notand aceste extremitati cu x si y, putem defini tipul de date “Muchie“, astfel:

Varianta C++:

struct Muchie{
int x, y;
}

Astfel ca putem reprezenta graful si ca un “vector de muchii”, adica un vector cu elemente de tipul Muchie:

Varianta C++:

Muchie v[25];

Exemplu:

Matricea de adiacenta:

Lista vecinilor:

Vectorul de muchii U = {(1, 2), (2, 3), (2, 4), (3, 4), (5, 6)}

Aplicatii

Construirea matricei de adiacenta pe baza muchiilor citite de la tastatura

Varianta C++:

void citire_graf(int a[10][10], int &n, int &m)
{
  int x, y;
  cout << "Numarul de varfuri: "; cin >> n;
  cout << "Numarul de muchii: "; cin >> m;
  for(int i = 1; i <= n; i++)
  {
    for(int j = 1; j <= n; j++)
    {
      a[i][j] = 0;
    }
  }
  
  for(int i = 1; i <= m; i++)
  {
    cout << "Muchia numarul: " << i;
    do
    {
      cin >> x >> y;
    }
    while(x < 1 || x > n || y < 1 || y > n || x == y)
    a[x][y] = 1;
    a[y][x] = 1;
  }
}

Determinarea muchiilor unui graf pornind de la matricea de adiacenta

Varianta C++:

void afisare_graf()
{
  cout << "Muchiile sunt: ";
  for(int i = 1; i < n; i++)
  {
    for(int j = i + 1; j <= n; j++)
    {
      if(a[i][j] == 1)
        cout << i << " " << j << "\n";
    }
  }
}

Citirea matricei de adiacenta de la tastatura

Varianta C++:

void citire_matrice(int a[10][10], int &n)
{
  cout << "Numarul de varfuri: "; cin >> n;
  for(int i = 1; i <= n; i++)
    a[i][i] = 0;
  for(int i = 1; i < n; i++)
  {
    for(int j = i + 1; j <= n; j++)
    {
      cout << "Scrieti 1 respectiv 0, daca muchia (" << i << ", " << j << ") exista sau nu: ";
      do
      {
        cin >> a[i][j];
      }
      while(a[i][j] != 0 && a[i][j] != 1);
      
      a[j][i] = a[i][j];
    }
  }
}

Citirea matricei de adiacenta dintr-un fisier text

Varianta C++:

#include <fstream>
ifstream fin("fisier.in");
void citire_matrice(int a[10][10], int &n)
{
  fin >> n;
  for(int i = 1; i < n; i++)
  {
    for(int j = i + 1; j <= n; j++)
    {
      fin >> a[i][j];
      a[j][i] = a[i][j];
    }
  }
  fin.close();
}

Determinare gradului unui varf X folosind matricea de adiacenta

Varianta C++:

int grad(int a[10][10], int x)
{
  int grad_nod = 0;
  for(int i = 1; i <= x; i++)
  {
    if(a[x][i] == 1)
      grad_nod ++;
  }
  return grad_nod;
}