componente connessa (II)

al contrario di ciò che io e d.m. facciamo di solito, ieri mi è capitato di dover utilizzare un risultato di teoria dei grafi per dimostrare una proposizione di analisi funzionale.


Proposizione

Sia G un grafo. Allora esistono



sottografi disgiunti e disconnessi di G, tale che ciascuno di essi è connesso.
Tale famiglia è univocamente determinata.

Dimostrazione

Si consideri la relazione R sull'insieme dei nodi di G definita da aRb se e solo se esiste un cammino (finito) da a a b.
R è una relazione di equivalenza, infatti
1) aRa, grazie al cammino triviale (a,a).
2) aRb implica bRa. Si prenda il cammino di lunghezza n



Il cammino inverso



ha lunghezza n e congiunge b ad a.
3) Se aRb e bRc allora, aRc. Infatti, siano



due cammini di lunghezza rispettivamente n e m, congiungenti il nodo a al nodo b e il nodo b al nodo c. Allora il cammino



ha lunghezza n+m e congiunge il nodo a al nodo c.

Si denoti N l'insieme dei nodi e si consideri l'insieme quoziente N/R. Allora gli elementi di N/R sono le componenti connesse del grafo. L'unicità è conseguenza dell'unicità dell'insieme quoziente, q.e.d.