Conectividad (teoría de grafos)
En matemáticas e informática , la conectividad es uno de los conceptos básicos de la teoría de grafos : solicita el número mínimo de elementos (nodos o aristas) que deben eliminarse para separar los nodos restantes en dos o más subgrafos aislados . [1] Está estrechamente relacionado con la teoría de los problemas de flujo de red . La conectividad de un gráfico es una medida importante de su capacidad de recuperación como red.
En un grafo no dirigido G , dos vértices u y v son llamados conectado si G contiene un camino de u a v . De lo contrario, se denominan desconectados . Si los dos vértices están conectados adicionalmente por un camino de longitud 1 , es decir, por un solo borde, los vértices se denominan adyacentes .
Se dice que un gráfico está conectado si cada par de vértices del gráfico está conectado. Esto significa que hay un camino entre cada par de vértices. Un gráfico no dirigido que no está conectado se llama desconectado . Por lo tanto, un grafo G no dirigido se desconecta si existen dos vértices en G de manera que ningún camino en G tenga estos vértices como puntos finales. Se conecta una gráfica con un solo vértice. Un gráfico sin bordes con dos o más vértices está desconectado.
Un gráfico dirigido se llama débilmente conectado si al reemplazar todos sus bordes dirigidos con bordes no dirigidos se produce un gráfico conectado (no dirigido). Se conecta de manera unilateral o unilateral (también llamado semiconnected ) si contiene un camino dirigido desde u a v o un camino dirigido desde v a u para cada par de vértices u, v . [2] Está fuertemente conectado , o simplemente fuerte, si contiene una ruta dirigida de u a v y una ruta dirigida de v a upara cada par de vértices u, v .
Un componente conectado es un subgrafo conectado máximo de un gráfico no dirigido. Cada vértice pertenece exactamente a un componente conectado, al igual que cada borde. Un gráfico está conectado si y solo si tiene exactamente un componente conectado.
Un corte de vértice o un conjunto de separación de un gráfico conectado G es un conjunto de vértices cuya eliminación hace que G esté desconectado. La conectividad de vértice κ ( G ) (donde G no es un gráfico completo ) es el tamaño de un corte de vértice mínimo. Un gráfico se llama k -conectado al vértice o k -conectado si su conectividad de vértice es k o mayor.
