Théorie des graphes - Connectivité
Il est possible de parcourir un graphe d'un sommet à un autre est déterminé par la manière dont un graphe est connecté. La connectivité est un concept de base de la théorie des graphes. La connectivité définit si un graphique est connecté ou déconnecté. Il comporte des sous-sujets basés sur l'arête et le sommet, appelés connectivité d'arête et connectivité de sommet. Laissez-nous les discuter en détail.
Connectivité
On dit qu'un graphique est connected if there is a path between every pair of vertex. De chaque sommet à n'importe quel autre sommet, il devrait y avoir un chemin à parcourir. Cela s'appelle la connectivité d'un graphe. Un graphe avec plusieurs sommets et arêtes déconnectés est dit déconnecté.
Example 1
Dans le graphique suivant, il est possible de voyager d'un sommet à n'importe quel autre sommet. Par exemple, on peut traverser du sommet 'a' au sommet 'e' en utilisant le chemin 'ab-e'.
Example 2
Dans l'exemple suivant, le passage du sommet 'a' au sommet 'f' n'est pas possible car il n'y a pas de chemin entre eux directement ou indirectement. C'est donc un graphe déconnecté.
Couper le sommet
Soit «G» un graphe connexe. Un sommet V ∈ G est appelé un sommet coupé de «G», si «G-V» (Supprimer «V» de «G») aboutit à un graphe déconnecté. La suppression d'un sommet coupé d'un graphique le divise en deux ou plusieurs graphiques.
Note - La suppression d'un sommet coupé peut rendre un graphique déconnecté.
Un graphe connexe 'G' peut avoir au plus (n – 2) sommets coupés.
Example
Dans le graphique suivant, les sommets «e» et «c» sont les sommets coupés.
En supprimant «e» ou «c», le graphique deviendra un graphique déconnecté.
Sans 'g', il n'y a pas de chemin entre le sommet 'c' et le sommet 'h' et bien d'autres. Il s'agit donc d'un graphe déconnecté avec un sommet coupé comme «e». De même, «c» est également un sommet coupé pour le graphique ci-dessus.
Bord coupé (pont)
Soit «G» un graphe connexe. Une arête 'e' ∈ G est appelée arête coupée si 'G-e' aboutit à un graphe déconnecté.
Si la suppression d'une arête dans un graphique entraîne la création de deux ou plusieurs graphiques, cette arête est appelée arête de coupe.
Example
Dans le graphique suivant, l'arête de coupe est [(c, e)].
En supprimant l'arête (c, e) du graphe, il devient un graphe déconnecté.
Dans le graphique ci-dessus, la suppression de l'arête (c, e) divise le graphique en deux qui n'est rien d'autre qu'un graphique déconnecté. Par conséquent, l'arête (c, e) est une arête coupée du graphique.
Note - Soit 'G' un graphe connexe à 'n' sommets, alors
une arête coupée e ∈ G si et seulement si l'arête 'e' ne fait partie d'aucun cycle de G.
le nombre maximum d'arêtes coupées possible est «n-1».
chaque fois que des arêtes coupées existent, des sommets coupés existent également car au moins un sommet d'une arête coupée est un sommet coupé.
s'il existe un sommet de coupe, alors une arête de coupe peut exister ou non.
Couper l'ensemble d'un graphique
Soit 'G' = (V, E) un graphe connexe. Un sous-ensemble E 'de E est appelé un ensemble coupé de G si la suppression de toutes les arêtes de E' de G fait que G se déconnecte.
Si la suppression d'un certain nombre d'arêtes d'un graphe le rend déconnecté, ces arêtes supprimées sont appelées l'ensemble de coupes du graphe.
Example
Jetez un œil au graphique suivant. Son ensemble de coupes est E1 = {e1, e3, e5, e8}.
Après avoir supprimé l'ensemble de coupes E1 du graphique, il apparaîtrait comme suit -
De même, il existe d'autres ensembles de coupes qui peuvent déconnecter le graphique -
E3 = {e9} - Le plus petit ensemble de coupes du graphique.
E4 = {e3, e4, e5}
Connectivité Edge
Soit «G» un graphe connexe. Le nombre minimum d'arêtes dont la suppression rend «G» déconnecté est appelé connectivité de bord de G.
Notation - λ (G)
En d'autres termes, le number of edges in a smallest cut set of G est appelée la connectivité de périphérie de G.
Si 'G' a une arête coupée, alors λ (G) vaut 1. (connectivité d'arête de G.)
Example
Jetez un œil au graphique suivant. En supprimant deux arêtes minimales, le graphe connecté est déconnecté. Par conséquent, sa connectivité de bord (λ (G)) est de 2.
Voici les quatre façons de déconnecter le graphique en supprimant deux arêtes -
Connectivité Vertex
Soit «G» un graphe connexe. Le nombre minimum de sommets dont la suppression rend «G» déconnecté ou réduit «G» en un graphe trivial est appelé sa connectivité de sommet.
Notation - K (G)
Example
Dans le graphique ci-dessus, la suppression des sommets «e» et «i» rend le graphique déconnecté.
Si G a un sommet coupé, alors K (G) = 1.
Notation - Pour tout graphe connexe G,
K (G) ≤ λ (G) ≤ δ (G)
Connectivité des sommets (K (G)), connectivité des bords (λ (G)), nombre minimum de degrés de G (δ (G)).
Example
Calculer λ (G) et K (G) pour le graphique suivant -
Solution
À partir du graphique,
δ (G) = 3
K (G) ≤ λ (G) ≤ δ (G) = 3 (1)
K (G) ≥ 2 (2)
En supprimant les arêtes {d, e} et {b, h}, nous pouvons déconnecter G.
Par conséquent,
λ (G) = 2
2 ≤ λ (G) ≤ δ (G) = 2 (3)
De (2) et (3), la connectivité des sommets K (G) = 2