Tags:
create new tag
view all tags

Chiusura Transitiva di un Grafo

Si calcoli la chiusura transitiva di un grafo diretto (cioe' con archi orientati) con al pi¨ 32 nodi.

  • Il grafo dev'essere rappresentato sotto forma di matrice di adiacenza.
  • La matrice di adiacenza di un grafo Ŕ una matrice a valori in {0,1} in cui esiste un 1 alle coordinate i,j se e solo se l'arco i->j Ŕ presente nel grafo.
  • Dato che il grafo contiene al pi¨ 32 nodi Ŕ possibile rappresentare tutta una riga della matrice di adiacenza come una stringa di 32 bits, ossia una word.
  • Per rappresentare tutta la matrice saranno quindi necessarie al pi¨ 32 words (una per riga).

La chiusura transitiva di un un grafo si calcola come segue:

  • per ogni tripla i,j,k con j,j,k tra 1 e numnodi
    • se esistono l'arco i->j e l'arco j->k si inserisce (se manca) l'arco i->k
  • se nel passo precedente si Ŕ inserito almeno un arco si ripete il passo

Esempio

Il grafo a -> b -> c -> d si trasforma in due passi come segue:

-> a b c d
a 0 1 0 0
b 0 0 1 0
c 0 0 0 1
d 0 0 0 0
-> a b c d
a 0 1 1 0
b 0 0 1 1
c 0 0 0 1
d 0 0 0 0
-> a b c d
a 0 1 1 1
b 0 0 1 1
c 0 0 0 1
d 0 0 0 0

Svolgimento:

  • scrivere una procedura di input che permetta di inserire gli archi del grafo creando la matrice di adiacenza
    • chiede il numero di nodi N (tra 1 e 32)
    • chiede il numero di archi da inserire (tra 1 e N*N)
    • per ogni arco chiede il primo nodo ed il secondo
  • scrivere una procedura di output che stampa la matrice di adiacenza del grafo:
    • per ogni riga si stampi un asterisco nella colonna corrispondente a ciascun 1 presente nella riga
  • scrivere il programma (per controllare le procedure di I/O) che:
    • chiede il grafo e costruisce la matrice di adiacenza
    • stampa la matrice di adiacenza del grafo
  • scrivere il programma che:
    • chiede il grafo e costruisce la matrice di adiacenza
    • calcola la chiusura transitiva del grafo
    • stampa la matrice di adiacenza del grafo

Se avete domande sul testo del progetto, fatele su DomandePrimoProgetto2002

-- AndreaSterbini - 26 Mar 2002

Edit | Attach | Watch | Print version | History: r4 < r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r4 - 2002-03-30 - AndreaSterbini






 
  • Help
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2022 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback