Tag: algoritm

Posted on by

Determinarea drumul optim într-un graf / drum hamiltonian, folosind matricea de atingere. (Chan)

O rezolvare pentru problema:

Să se întocmească un program care determină drumul optim într-un graf, folosind matricea de atingere.

consta in determinarea unui drum hamiltonian într-un graf orientat (fără circuite).
Se poate executa un algoritm cu 2 pasi (Chan)

  • Pasul 1. Se construieşte matricea conexă terminală T pornind de lamatricea tranziţiilor M.
    Se determină câte elemente din T sunt nenule; dacă numărul acestora este n(n-1)/2, atunci graful conţine un drum hamiltonian.
  • Pasul 2. Din matricea T se construieşte T_prim.

    • Continue reading Determinarea drumul optim într-un graf / drum hamiltonian, folosind matricea de atingere. (Chan)