Teorema di Kirchhoff
Ciao, avrei una domanda riguardo all'enunciato del teorema di Kirchhoff.
Sia \(G\) un grafo connesso con \(n \) vertici, e siano \(\lambda_1, \ldots, \lambda_{n-1} \) gli autovalori non nulli della matrice Laplaciana di \(G \). Allora il numero di alberi ricoprenti di \(G \) è dato da
\[ \frac{1}{n} \prod\limits_{k=1}^{n-1} \lambda_k \]
La mia domanda è come mai si è sicuri che vi siano esattamente \( n -1 \) autovalori non nulli, ed esattamente uno nullo?
Sia \(G\) un grafo connesso con \(n \) vertici, e siano \(\lambda_1, \ldots, \lambda_{n-1} \) gli autovalori non nulli della matrice Laplaciana di \(G \). Allora il numero di alberi ricoprenti di \(G \) è dato da
\[ \frac{1}{n} \prod\limits_{k=1}^{n-1} \lambda_k \]
La mia domanda è come mai si è sicuri che vi siano esattamente \( n -1 \) autovalori non nulli, ed esattamente uno nullo?
Risposte
La molteplicità dell'autovalore zero della matrice Laplaciana è uguale al numero di componenti connesse, vedi qui.
Grazie per il riferimento, Martino.
È una cosa in cui sono inciampato un paio di volte, ma non ho mai avuto l’opportunità di approfondire.
È una cosa in cui sono inciampato un paio di volte, ma non ho mai avuto l’opportunità di approfondire.
Grazie mille!
Prego 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo