operazioni matriciali per enumerare tutti i percorsi attraverso n-partite grafico

Question

ho un n-partite grafico (non orientato), dato come una matrice di adiacenza, per esempio questa qui:

 
    a b c d 
a 0 1 1 0 
b 0 0 0 1 
c 0 0 0 1 
d 0 0 0 0 

Vorrei sapere se c'è un insieme di operazioni matriciali che posso applicare a questa matrice, che si tradurrà in una matrice che "elenca" tutti i percorsi (di lunghezza n, cioè attraverso tutte le partizioni) in questo grafico. Per l'esempio sopra, ci sono i percorsi a-> b-> d e a-> c-> d. Perciò, desidero ottenere la seguente matrice come risultato:

 
a b c d 
1 1 0 1 
1 0 1 1 

Il primo percorso contiene nodi A, B, D ed il secondo nodi A, c, d. Se necessario, la matrice dei risultati potrebbe avere alcune linee tutte 0, come qui:

 
a b c d 
1 1 0 1 
0 0 0 0 
1 0 1 1 
0 0 0 0 

Grazie!

P.S. Ho esaminato gli algoritmi per il calcolo della chiusura transitiva, ma in genere questi indicano solo se esiste un percorso tra due nodi e non direttamente quali nodi si trovano su quel percorso.

Answer 1

Una cosa che puoi fare è calcolare l'ennesima potenza della tua matrice A. Il risultato ti dirà quanti percorsi ci sono di lunghezza n da qualsiasi vertice a qualsiasi altro.

Ora, se sei interessato a conoscere tutti i vertici lungo il percorso, non penso che usare le operazioni puramente a matrice sia la strada da percorrere. Tenendo presente che si dispone di un grafico n-suddiviso, impostare una struttura dati come segue: (Ricordare che i costi dello spazio saranno costosi per tutti tranne i valori piccoli)

Ogni colonna avrà una voce di ciascuno dei nodi nel nostro grafico. La n-esima colonna conterrà 1 in se questo nodo è raggiungibile all'n-esima iterazione dal nostro vertice iniziale designato o set iniziale, e zero altrimenti. Ogni voce di colonna conterrà anche un elenco di puntatori posteriori ai vertici nella colonna n-1 che ha portato a questo vertice nella colonna n. (Questo è come l'algoritmo viterbi, tranne per il fatto che dobbiamo mantenere una lista di backpointer per ogni voce piuttosto che una sola.) La complessità di ciò è (m^2) * n, dove m è il numero di vertici nel grafico, e n è la lunghezza del percorso desiderato.

Sono un po 'confuso dalla matrice superiore: con un grafico non idratato, mi aspetto che la matrice di adiacenza sia simmetrica.

Answer 2

No, non esiste un modo matrice puro per generare tutti i percorsi. Si prega di utilizzare algoritmi combinatori puri.

'Una cosa che puoi fare è calcolare l'ennesima potenza della tua matrice A. Il risultato ti dirà quanti percorsi ci sono di lunghezza n da qualsiasi vertice a qualsiasi altro.'

Il potere di matriax genera percorsi non percorsi.