Question

1. Elaboraţi procedura introducerii unui graf în memoria calculatorului în formă de:
1) matrice de incidenţă (orientat),
2) matrice de adiacenţă (graf neorientat, graf orientat).
2. Folosind procedurile menţionate elaboraţi programul care va permite:
1) introducerea grafului reprezentat sub oricare din cele trei forme cu posibilităţi de corecţie a datelor
2) extragerea informaţiei la display.
dau coroana ca fiind cel mai bun raspuns de nota 10 in Limbajul C++/C# codul 100% functional fara greseli

Answer 1

Răspuns:

Procedurile pentru includerea unui graf în memoria calculatorului în formă de matrice de incidență sau matrice de adiacență.

Pentru graf orientat, matricea de incidență este o matrice cu n linii și m coloane, unde n reprezintă numărul de noduri, iar m reprezintă numărul de muchii. Elementul de pe linia i și coloana j va fi 1 dacă nodul i este sursă pentru muchia j, -1 dacă nodul i este destinația pentru muchia j, și 0 în caz contrar. De exemplu, dacă graful are nodurile 1, 2 și 3, iar muchiile sunt (1,2), (2,3) și (3,1), matricea de incidență ar fi:

  1  2  3

+---------

1 |  1  0 -1

2 |  0  1  0

3 | -1  0  1

Matricea de adiacență pentru un graf orientat este o matrice cu n linii și n coloane, unde n reprezintă numărul de noduri. Elementul de pe linia i și coloana j va fi 1 dacă există o muchie de la nodul i la nodul j, și 0 în caz contrar. De exemplu, matricea de adiacență pentru graful de mai sus ar fi:

  1  2  3

+---------

1 |  0  1  0

2 |  0  0  1

3 |  1  0  0

Pentru graf neorientat, matricea de adiacență este o matrice cu n linii și n coloane, unde n reprezintă numărul de noduri. Elementul de pe linia i și coloana j va fi 1 dacă există o muchie între nodurile i și j, și 0 în caz contrar. De exemplu, dacă graful are nodurile 1, 2 și 3, iar muchiile sunt (1,2), (2,3) și (3,1), matricea de adiacență ar fi:

  1  2  3

+---------

1 |  0  1  1

2 |  1  0  1

3 |  1  1  0

Iată un program care permite introducerea și afișarea unui graf sub oricare din cele trei forme, cu posibilitatea de corectare a datelor:

# functia pentru citirea unui numar intreg de la tastatura

def read_int(prompt):

  while True:

      try:

          return int(input(prompt))

      except ValueError:

          print("Valoarea introdusa nu este un numar intreg.")

# functia pentru citirea unui graf in forma de matrice de adiacenta

def read_adjacency_matrix():

  n = read_int("Introduceti numarul de noduri: ")

  adjacency_matrix = []

  for i in range(n):

      row = []

      for j in range(n):

          row