Esercizi sui Grafi

Pubblicato il 01-04-2022.

Invariant Distribution

Ho un grafo il cui condensation graph ha almeno un sink. Per calcolare l'invariant distrinution devo prima calcolare gli extremals. Per ogni sink, il relativo extremal è un vettore i cui elementi sono nulli, eccetto nelle posizioni associate ai nodi del sink. I valori vanno calcolati ponendo che la loro somma deve essere unitaria e che l'extremal deve essere esso stesso invariante di P trasposto. L'invariant distribution è la combinazione convessa degli extremals.

Centralità dei Grafi Bilanciati

Se un grafo è bilanciato, la centralità di un nodo è il suo peso relativo alla somma di tutti i pesi.

Stubborn Nodes nei Grafi ad Albero

Posizionare uno stubborn node alla radice di un albero impone asintoticamente il suo valore a tutto l'albero. Posizionare due stubborn nodes adiacenti divide il grafo.

Autovalori del Laplaciano

Per il teorema di Gershgorin, tutti gli autovalori di L, eccetto quello nullo,

hanno parte reale positiva. Siccome la media distribuita a tempo continuo ha l'opposto di L come matrice dinamica, il sistema converge sempre al consenso, poichè gli autovalori hanno tutti parte reale negativa.