Vai al contenuto

1.3 Connettività

Parte 1 · Grafi · Capitolo 1 · Capitolo 1: Grafi · Dispensa, volume 1 (PDF) · Esercizi: Grafi · App: Ricerca su grafo: BFS e DFS

Definizione 1.10: grafo connesso e componenti connessi

Sia \(G=(V,E)\) un grafo non orientato.

  • Due vertici \(u\) e \(v\) sono connessi se \(G\) ha un percorso da \(u\) a \(v\); il grafo \(G\) è connected se ogni due vertici sono collegati.

  • Un componente connesso di \(G\) è un sottoinsieme massimo \(U \subseteq V\) di vertici connessi a coppie.

Un grafo orientato è debolmente connesso se il suo grafo non orientato sottostante è connesso e il suo grafo connesso i componenti sono quelli del grafo non orientato sottostante.

Definizione 1.11: raggiungibilità e componenti fortemente connessi

Sia \(G=(N,A)\) un grafo diretto.

  • Un nodo \(j\) è raggiungibile da \(i\) se \(G\) ha un percorso diretto da \(i\) a \(j\); l'insieme dei nodi raggiungibile da \(i\), \(i\) compreso, è indicato con \(R(i)\).

  • I nodi \(i\) e \(j\) sono fortemente connesso se \(j \in R(i)\) e \(i \in R(j)\); il grafo è fortemente connesso se ogni due nodi sono fortemente connessi.

  • Un componente fortemente connesso di \(G\) è un sottoinsieme massimo \(S \subseteq N\) di coppie fortemente connesse nodi connessi.

Proposizione 1.12: i componenti sono classi di equivalenza

Essere connessi è una relazione di equivalenza su \(V\) ed essere fortemente connessi è una relazione di equivalenza su \(N\). Da qui la partizione di componenti connessi \(V\) e la partizione di componenti fortemente connessi \(N\).

Dimostrazione

Dimostriamo le tre proprietà per la connessione forte; il caso non orientato è lo stesso con i percorsi al posto di percorsi diretti.

  1. Riflessivo: il percorso \(i\) di lunghezza \(0\) mostra che \(i \in R(i)\).

  2. Simmetrico: la definizione è simmetrica in \(i\) e \(j\).

  3. Transitivo: un percorso diretto da \(i\) a \(j\)Z seguito da uno da \(j\) a \(h\) è una passeggiata diretta da Da \(i\) a \(h\), che contiene un percorso diretto da Lemma 1.6. Lo stesso vale da \(h\) a \(i\).

Le classi di equivalenza sono i sottoinsiemi massimi di elementi correlati a coppie, cioè i componenti. □

  • Il grafo invertito \(G'=(N,A')\) ha l'arco \((j,i)\) per ogni arco \((i,j) \in A\). Il nodo \(i\) è raggiungibile da \(j\) in \(G\) se e solo se \(j\) è raggiungibile da \(i\) in \(G'\); indichiamo con \(R'(i)\) l'insieme dei nodi raggiungibili da \(i\) in \(G'\).

  • Con Definizione 1.11, il componente fortemente connesso che contiene \(i\) è

    \[ S(i)=R(i) \cap R'(i). \]

Esempio 1.6: componenti del grafo di riferimento

Nel grafo di riferimento:

\[ R(1)=\{1,2,3,4,5,6\}, \qquad R(2)=\{2,3,4,5,6\}, \qquad R(6)=\{6\}. \]

Nel grafo invertito \(R'(3)=\{1,2,3,4,5\}\) e \(R(3)=\{2,3,4,5,6\}\), quindi \(S(3)=\{2,3,4,5\}\). Il fortemente connesso i componenti sono

\[ \{1\}, \qquad \{2,3,4,5\}, \qquad \{6\}. \]

Figura 4

Il grafo è debolmente connesso, con una componente connessa, ma non è fortemente connesso: nessun nodo è raggiungibile from node \(6\).

Le componenti connesse e le componenti fortemente connesse sono le classi di due relazioni di equivalenza. Il Il componente fortemente connesso di \(i\) è \(R(i) \cap R'(i)\): i nodi raggiungibili da \(i\) che possono anche raggiungere \(i\).

Avanti: 1.4 Alberi e foreste