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 : pide 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 redes . La conectividad de un gráfico es una medida importante de su resiliencia como red.
En un grafo no dirigido G , dos vértices u y v se llaman conectados 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 llaman adyacentes .
Se dice que un grafo es conexo si todos los pares de vértices del grafo son conexos. Esto significa que hay un camino entre cada par de vértices. Un grafo no dirigido que no es conexo se llama desconectado . Por lo tanto, un grafo G no dirigido es desconectado si existen dos vértices en G tales que ningún camino en G tiene estos vértices como puntos finales. Un grafo con un solo vértice es conexo. Un gráfico sin bordes con dos o más vértices está desconectado.
Un grafo dirigido se llama débilmente conectado si al reemplazar todas sus aristas dirigidas con aristas no dirigidas se produce un grafo conectado (no dirigido). Es unilateralmente conexo o unilateral (también llamado semiconexo ) si contiene un camino dirigido de u a v o un camino dirigido de v a u para cada par de vértices u, v . [2] Es fuertemente conexo , o simplemente fuerte, si contiene un camino directo de u a v y un camino directo de v a upara cada par de vértices u, v .
Un componente conexo es un subgrafo conexo máximo de un grafo no dirigido. Cada vértice pertenece exactamente a un componente conectado, al igual que cada borde. Un grafo es conexo si y solo si tiene exactamente una componente conexa.
Un conjunto de corte o separación de vértices de un grafo conexo G es un conjunto de vértices cuya eliminación hace que G sea desconectado. La conectividad de vértice κ ( G ) (donde G no es un gráfico completo ) es del tamaño de un corte de vértice mínimo. Un grafo se llama k -vertex-connected o k -connected si su conectividad de vértice es k o mayor.
