Ho un problema di Algoritmi e Strutture dati sui grafi che non riesco a risolvere:
Dato un grafo G(V, E) la potenza k-esima di G è un grafo Gk(Vk, Ek) tale che ogni arco (x, y) di G appartiene a Gk se e solo se esiste un percorso di k archi che collegano i due nodi x e y nel grafo di partenza G.
La mia idea era quella di usare un algoritmo greedy controllando se ogni coppia di nodi (x,y) di G direttamente collegati, siano separati amche da k archi. Il problema è che non so come capire se due nodi di un grafo sono separati da k nodi oppure no.
Grazie mille in anticipo
Di fatto bisogna effettivamente calcolare la potenza del grafo o meglio della matrice di adiacenza del grafo.
Una spiegazione più dettagliata a pag 222.
5 Mi Piace
Grazie mille della risposta, mi hai risolto il problema!