Relazione di raggiungibilità
Se tra i vertici e esiste un cammino dico che sono raggiungibili:
Oss E’ una relazione di equivalenza su (riflessiva, simmetrica e transitiva).
Le classi di equivalenza sono chiamate componenti connesse, sono i sottografi connessi massimali del grafo :
definisco il numero di componenti connesse di un grafo .
Prop Se allora esiste un cammino semplice tra ed .
Dim Costruisco il cammino semplice a partire dalla passeggiata da ad , infatti se non è semplice significa che c’è una ripetizioni di archi, quindi di vertici, ovvero tale che:
posso rimuovere il blocco compreso tra questo stesso vertice , ottengo una nuova passeggiata senza che il vertice si ripetea. Faccio lo stesso per tutti i vertici ripetuti, per induzione arrivo ad un cammino senza ripetizioni di vertici, ovvero semplice.
Metrica
Definiamo una metrica sull’insieme dei vertici , ovvero
quindi è uno spazio metrico.
Oss Sia un sottografo di , allora
Oss Se allora esiste un cammino semplice lungo che li collega: se non è semplice posso accorciarlo, ma è il minimo per definizione!
Def Sia un grafo connesso, si definisce Eccentricità di un vertice :
Da questa definizione seguono altre due.
Def Sia un grafo connesso, si definisce il raggio del grafo il numero:
il raggio di un grafo è il valore minimo di eccentricità. I vertici del grafo di minima eccentricità vengono detti centro del grafo. Analogamente Def Sia un grafo connesso, si definisce il diametro del grafo il numero:
i vertici di massima eccentricità vengono detti periferia del grafo.
Vale la seguente disugualianza tra le quantità definite
Proposizione Sia un grafo connesso, allora vale:
Dim La prima disuglianza è vera per definizione. Per dimostrare la seconda,siano tali che . Scegliamo un vertice nel centro del grafo , allora vale:
Remark Anche nel caso non connesso valgono queste disugualianze, ma ogni eccentricità risulta infinita…