Grafi connessi e relazioni binarie.

[Obionekenobi1]

Se ho una matrice che mi rappresenta un grafo, come faccio da essa a capire se esso non è connesso? La mia prof. fa il prodotto della matrice per se stessa, va a controllare negli zeri di questa nuova matrice e se a tutti questi zeri corrispondono degli 1 nella vecchia matrice, allora il grafo è connesso. Ma come faccio a capire se non lo è??

[angus89]

Io conosco un metodo generale per contare il numero di componenti connesse di un grafo.
Di conseguenza se questo numero è 1 hai finito, il grafo è connesso.
Non so se lo hai fatto a lezione, ma tanto per curiosità tua personale, o chissà, ti può servire in futuro, vale il seguente risultato.

Dato un grafo $G$, detta $H$ la sua matrice di adiacenza (quella che tu chiami "matrice che rappresenta in grafo") e data $D$ la matrice diagonale con elementi sulla diagonale $(D)_{i,i}=deg(v_i)$ (ovvero alla posizione i-esima sulla diagonale c'è il grado del nodo i-esimo), allora definisco la matrice laplaciana come $L=D-H$ e vale che la dimensione del nucleo di questa matrice è pari al numero di componenti connesse del grafo.

NB: il vettore $(1,1,1,...,1)$ è nel nucleo che quindi ha dimensione almeno 1.


Se ti interessa ti faccio vedere qualche trucchetto per andare avanti...se non ti interessava...va bè ormai l'ho scritto...