Sui grafi

[giulia.sim1]

Carissimi,
ho un grafo semplice non orientato, pesato, completo.
Se elimino gli archi con peso Il problema che vorrei affrontare è il seguente:
noto il peso di ciascun arco, nota la soglia S, trovare il numero N dei sottografi non collegati (N può essere anche 0)

(Se possibile trovare anche il numero di nodi in ciascun sottografo)


Dato che di grafi non so molto, potreste darmi qualche indicazione o testo per orientarmi? magari (sicuramente!) è un problema noto e già risolto


Grazie!

[qqwert]

Non capisco esattamente quello che stai chiedendo... vuoi sapere se esiste un modo per conoscere a priori le informazioni che chiedi (che francamente non credo possa esistere) oppure vuoi sapere un algoritmo per la determinazione delle componenti sconnesse?

[giulia.sim1]

"qqwert":Non capisco esattamente quello che stai chiedendo... vuoi sapere se esiste un modo per conoscere a priori le informazioni che chiedi (che francamente non credo possa esistere) oppure vuoi sapere un algoritmo per la determinazione delle componenti sconnesse?

*se possibile* vorrei, data la matrice di adiacenza, calcolare il numero di componenti sconnesse (cioè i grafi non connessi da nessun arco)

se non è possibile avere questa informazione direttamente, allora va bene qualche indicazione circa l0algoritmo da adottare

Grazie!

[qqwert]

L'unica cosa che mi viene in mente è questa: indicando con Q il numero di nodi del grafo e con A la matrice di adiacenza dopo il "filtraggio" (cioè dopo aver tolto gli elementi con peso inferiore alla soglia), calcoli la matrice $\sum_{i=1}^(Q-1) A^i$. Nella matrice così trovata se nel posto con indici i,j trovi uno zero, allora i nodi i e j appartengono a componenti sconnesse.
Pur essendo piuttosto convinto della correttezza di quanto ho scritto, devo avvertirti che è frutto di miei calcoli (anche se sicuramente non sarò stato il primo a fare un ragionamento del genere, qualora sia corretto), quindi usalo a tuo rischio e pericolo
Inoltre immagino che tu non voglia applicare tutto ciò a grafi di 6 nodi (anche perché in quel caso basta disegnarsi il grafo a mano ), quindi sarai costretta a far fare dei calcoli a un pc. Nel caso di implementazione che io sappia la matrice di adiacenza è solitamente piuttosto sconsigliata.
Un ultima cosa: se per qualche motivo tu usassi pesi che possono assumere valori negativi, quanto ho scritto va a farsi benedire!
Spero di esserti stato utile

[giulia.sim1]

Grazie molte!
testerò il metodo.

Su it.scienza.matematica mi hanno consigliato anche questo metodo

http://en.wikipedia.org/wiki/Connected_ ... aph_theory)

domani farò alcune prove.


thanks!