Teoria dei grafici - Connettività
Se è possibile attraversare un grafico da un vertice all'altro è determinato dal modo in cui un grafico è connesso. La connettività è un concetto di base nella teoria dei grafi. La connettività definisce se un grafico è connesso o disconnesso. Ha argomenti secondari basati su bordo e vertice, noti come connettività edge e connettività vertice. Cerchiamo di discuterli in dettaglio.
Connettività
Si dice che sia un grafico connected if there is a path between every pair of vertex. Da ogni vertice a qualsiasi altro vertice, dovrebbe esserci un percorso da attraversare. Questa è chiamata connettività di un grafico. Si dice che un grafo con più vertici e bordi scollegati sia disconnesso.
Example 1
Nel grafico seguente, è possibile viaggiare da un vertice a qualsiasi altro vertice. Ad esempio, si può passare dal vertice "a" al vertice "e" utilizzando il percorso "ab-e".
Example 2
Nell'esempio seguente, l'attraversamento dal vertice "a" al vertice "f" non è possibile perché non esiste alcun percorso tra di loro direttamente o indirettamente. Quindi è un grafico disconnesso.
Cut Vertex
Sia "G" un grafo connesso. Un vertice V ∈ G è chiamato vertice tagliato di 'G', se 'G-V' (Elimina 'V' da 'G') risulta in un grafo disconnesso. La rimozione di un vertice tagliato da un grafico lo suddivide in due o più grafici.
Note - La rimozione di un vertice tagliato può rendere un grafico scollegato.
Un grafo connesso 'G' può avere al massimo (n – 2) vertici tagliati.
Example
Nel grafico seguente, i vertici "e" e "c" sono i vertici tagliati.
Rimuovendo "e" o "c", il grafico diventerà un grafico disconnesso.
Senza 'g', non c'è percorso tra il vertice 'c' e il vertice 'h' e molti altri. Quindi è un grafo disconnesso con vertice tagliato come "e". Allo stesso modo, 'c' è anche un vertice tagliato per il grafico sopra.
Bordo tagliato (ponte)
Sia "G" un grafo connesso. Un arco 'e' ∈ G è detto bordo tagliato se 'G-e' risulta in un grafo disconnesso.
Se rimuovendo un bordo in un grafico si ottengono due o più grafici, quel bordo viene chiamato bordo tagliato.
Example
Nel grafico seguente, il bordo tagliato è [(c, e)].
Rimuovendo il bordo (c, e) dal grafico, diventa un grafico disconnesso.
Nel grafico sopra, la rimozione del bordo (c, e) spezza il grafico in due che non è altro che un grafico disconnesso. Quindi, il bordo (c, e) è un bordo tagliato del grafico.
Note - Sia 'G' un grafo connesso con 'n' vertici, quindi
un bordo tagliato e ∈ G se e solo se il bordo 'e' non fa parte di alcun ciclo in G.
il numero massimo di bordi tagliati possibile è 'n-1'.
ogniqualvolta esistono bordi tagliati, esistono anche vertici tagliati perché almeno un vertice di un bordo tagliato è un vertice tagliato.
se esiste un vertice tagliato, allora un bordo tagliato può o non può esistere.
Taglia insieme di un grafico
Sia 'G' = (V, E) un grafo connesso. Un sottoinsieme E 'di E è chiamato un insieme tagliato di G se la cancellazione di tutti gli archi di E' da G fa disconnettere G.
Se l'eliminazione di un certo numero di bordi da un grafico ne causa la disconnessione, tali bordi eliminati vengono chiamati il gruppo di tagli del grafico.
Example
Dai un'occhiata al grafico seguente. Il suo set di taglio è E1 = {e1, e3, e5, e8}.
Dopo aver rimosso il set di taglio E1 dal grafico, apparirà come segue:
Allo stesso modo, ci sono altri gruppi di taglio che possono disconnettere il grafico -
E3 = {e9} - Il più piccolo insieme di sezioni del grafico.
E4 = {e3, e4, e5}
Connettività Edge
Sia "G" un grafo connesso. Il numero minimo di bordi la cui rimozione rende 'G' scollegato è chiamato connettività degli spigoli di G.
Notation - λ (G)
In altre parole, il file number of edges in a smallest cut set of G è chiamata la connettività edge di G.
Se 'G' ha un bordo tagliato, allora λ (G) è 1. (connettività del bordo di G.)
Example
Dai un'occhiata al grafico seguente. Rimuovendo due bordi minimi, il grafico connesso viene disconnesso. Quindi, la sua connettività di bordo (λ (G)) è 2.
Ecco i quattro modi per scollegare il grafico rimuovendo due bordi:
Vertex Connectivity
Sia "G" un grafo connesso. Il numero minimo di vertici la cui rimozione rende "G" scollegato o riduce "G" a un grafo banale è chiamato la sua connettività di vertice.
Notation - K (G)
Example
Nel grafico sopra, la rimozione dei vertici "e" e "i" rende il grafico scollegato.
Se G ha un vertice tagliato, allora K (G) = 1.
Notation - Per qualsiasi grafo G connesso,
K (G) ≤ λ (G) ≤ δ (G)
Connettività al vertice (K (G)), connettività ai bordi (λ (G)), numero minimo di gradi di G (δ (G)).
Example
Calcola λ (G) e K (G) per il grafico seguente:
Solution
Dal grafico,
δ (Sol) = 3
K (G) ≤ λ (G) ≤ δ (G) = 3 (1)
K (G) ≥ 2 (2)
Eliminando i bordi {d, e} e {b, h}, possiamo scollegare G.
Perciò,
λ (G) = 2
2 ≤ λ (G) ≤ δ (G) = 2 (3)
Da (2) e (3), la connettività dei vertici K (G) = 2