Teoría de grafos - Conectividad
La posibilidad de atravesar una gráfica de un vértice a otro depende de cómo se conecta una gráfica. La conectividad es un concepto básico en la teoría de grafos. La conectividad define si un gráfico está conectado o desconectado. Tiene subtemas basados en borde y vértice, conocidos como conectividad de borde y conectividad de vértice. Discutámoslos en detalle.
Conectividad
Se dice que una gráfica es connected if there is a path between every pair of vertex. Desde cada vértice hasta cualquier otro vértice, debería haber algún camino que recorrer. Eso se llama conectividad de un gráfico. Se dice que un gráfico con múltiples vértices y aristas desconectados está desconectado.
Example 1
En el siguiente gráfico, es posible viajar de un vértice a cualquier otro vértice. Por ejemplo, uno puede atravesar desde el vértice 'a' al vértice 'e' usando la ruta 'ab-e'.
Example 2
En el siguiente ejemplo, no es posible atravesar desde el vértice 'a' al vértice 'f' porque no hay una ruta entre ellos directa o indirectamente. Por tanto, es un gráfico desconectado.
Cortar vértice
Sea 'G' un gráfico conectado. Un vértice V ∈ G se llama vértice de corte de 'G', si 'G-V' (Eliminar 'V' de 'G') da como resultado un gráfico desconectado. Quitar un vértice cortado de un gráfico lo divide en dos o más gráficos.
Note - Eliminar un vértice cortado puede hacer que un gráfico se desconecte.
Un gráfico conectado 'G' puede tener como máximo (n – 2) vértices de corte.
Example
En el siguiente gráfico, los vértices 'e' y 'c' son los vértices cortados.
Al eliminar 'e' o 'c', el gráfico se convertirá en un gráfico desconectado.
Sin 'g', no hay camino entre el vértice 'c' y el vértice 'h' y muchos otros. Por lo tanto, es un gráfico desconectado con vértice cortado como 'e'. De manera similar, 'c' también es un vértice de corte para el gráfico anterior.
Corte de borde (puente)
Sea 'G' un gráfico conectado. Una arista 'e' ∈ G se denomina arista de corte si 'G-e' da como resultado un gráfico desconectado.
Si eliminar un borde en un gráfico da como resultado dos o más gráficos, entonces ese borde se llama Corte de borde.
Example
En el siguiente gráfico, el borde de corte es [(c, e)].
Al eliminar el borde (c, e) del gráfico, se convierte en un gráfico desconectado.
En el gráfico anterior, eliminar el borde (c, e) divide el gráfico en dos, que no es más que un gráfico desconectado. Por tanto, el borde (c, e) es un borde cortado del gráfico.
Note - Sea 'G' un gráfico conectado con 'n' vértices, luego
un borde de corte e ∈ G si y solo si el borde 'e' no es parte de ningún ciclo en G.
el número máximo de bordes de corte posibles es 'n-1'.
siempre que existan bordes cortados, también existen vértices cortados porque al menos un vértice de un borde cortado es un vértice cortado.
si existe un vértice de corte, entonces puede existir o no un borde de corte.
Cortar conjunto de un gráfico
Sea 'G' = (V, E) una gráfica conectada. Un subconjunto E 'de E se denomina conjunto cortado de G si la eliminación de todos los bordes de E' de G hace que G se desconecte.
Si eliminar un cierto número de bordes de un gráfico lo desconecta, esos bordes eliminados se denominan conjunto de corte del gráfico.
Example
Eche un vistazo al siguiente gráfico. Su conjunto de corte es E1 = {e1, e3, e5, e8}.
Después de eliminar el conjunto de cortes E1 del gráfico, aparecería de la siguiente manera:
De manera similar, hay otros conjuntos de cortes que pueden desconectar el gráfico:
E3 = {e9}: conjunto de corte más pequeño del gráfico.
E4 = {e3, e4, e5}
Conectividad perimetral
Sea 'G' un gráfico conectado. El número mínimo de bordes cuya eliminación hace que 'G' se desconecte se denomina conectividad de borde de G.
Notation - λ (G)
En otras palabras, el number of edges in a smallest cut set of G se llama conectividad de borde de G.
Si 'G' tiene un borde cortado, entonces λ (G) es 1. (conectividad de borde de G.)
Example
Eche un vistazo al siguiente gráfico. Al eliminar dos bordes mínimos, el gráfico conectado se desconecta. Por lo tanto, su conectividad de borde (λ (G)) es 2.
Aquí están las cuatro formas de desconectar el gráfico quitando dos bordes:
Conectividad de vértice
Sea 'G' un gráfico conectado. El número mínimo de vértices cuya eliminación hace que 'G' se desconecte o reduzca 'G' a un gráfico trivial se llama conectividad de vértice.
Notation - K (G)
Example
En el gráfico anterior, eliminar los vértices 'e' e 'i' hace que el gráfico se desconecte.
Si G tiene un vértice cortado, entonces K (G) = 1.
Notation - Para cualquier gráfico G conectado,
K (G) ≤ λ (G) ≤ δ (G)
Conectividad de vértice (K (G)), conectividad de borde (λ (G)), número mínimo de grados de G (δ (G)).
Example
Calcule λ (G) y K (G) para el siguiente gráfico:
Solution
Del gráfico,
δ (G) = 3
K (G) ≤ λ (G) ≤ δ (G) = 3 (1)
K (G) ≥ 2 (2)
Eliminando los bordes {d, e} y {b, h}, podemos desconectar G.
Por lo tanto,
λ (G) = 2
2 ≤ λ (G) ≤ δ (G) = 2 (3)
De (2) y (3), conectividad de vértice K (G) = 2