Conectividad (teoría de grafos)

La conectividad de vértices, nodos o puntos de un grafo ${\displaystyle G}$, denotada ${\displaystyle \kappa (G)}$, es el número mínimo ${\displaystyle \kappa }$ para el que el grafo tiene un corte de nodos-${\displaystyle \kappa }$.[2] Así, si el grafo es inconexo, entonces ${\displaystyle \kappa (G)=0}$, porque no hay que quitar ningún vértice; si el grafo tiene un punto de corte, entonces ${\displaystyle \kappa (G)=1}$, porque basta quitar un único vértice para que el grafo se vuelva inconexo, y así sucesivamente. Además, para cualquier valor ${\displaystyle k\leq \kappa (G)}$, el grafo se dice que es ${\displaystyle k}$-conexo o ${\displaystyle k}$-conectado por nodos. Note que un grafo completo ${\displaystyle K_{n}}$ no tiene puntos de corte, y que la única forma de desconectarlo es quitando ${\displaystyle n-1}$ vértices, con lo que se obtiene el grafo trivial. Por lo tanto, κ${\displaystyle (K_{n})=n-1}$.[1]

Análogamente, la conectividad de aristas o conectividad lineal, ${\displaystyle \lambda (G)}$, es el número mínimo ${\displaystyle \lambda }$ para el que el grafo tiene un corte de aristas-${\displaystyle \lambda }$.[2] Además, para cualquier valor ${\displaystyle l\leq \lambda (G)}$, el grafo se dice que es ${\displaystyle l}$-linealmente conexo.[1]

Dado un grafo dirigido, un par de vértices está:[1]

• débilmente conectado, si están unidos por un semicamino (es decir, un camino que no considera la dirección de las aristas);
• unilateralmente conectado, si están unidos por un camino que va desde uno hasta el otro;
• fuertemente conectado, si están unidos por al menos dos caminos, uno que va desde uno hasta el otro, y viceversa;
• recursivamente conectado, si están fuertemente conectados y el camino desde uno hasta el otro usa los mismos vértices y aristas que los del camino inverso.

Si se cumple alguno de estos tipos de conexiones, entonces se cumplen todos los tipos anteriores.[1]

Un grafo no dirigido en que todos sus vértices están conectados por un camino es un grafo conexo. Para un grafo dirigido, se distingue entre los siguientes tipos de conectividad:[1]

• débilmente conexo, si todos los pares de vértices están débilmente conectados;
• unilateralmente conexo, si todos los pares de vértices están unilateralmente conectados;
• fuertemente conexo, si todos los pares de vértices están fuertemente conectados;
• recursivamente conexo, si todos los pares de vértices están recursivamente conectados.

En análisis de redes sociales, la conectividad de una red social es un concepto importante,[1] dado que está relacionado con el concepto de cohesión social, estudiado en áreas de las ciencias sociales como la sociología o la psicología. La noción de conectividad se relaciona con propiedades de los lazos interpersonales. Para redes sociales representadas como grafos ponderados, los conceptos de camino a nivel c y accesibilidad a nivel c se utilizan para estudiar subgrupos cohesivos para relaciones valoradas.[1]

• Grafo conexo
• Componente (teoría de grafos)
• Cohesión social

• Harary, F. (1969). Graph theory. Reading, MA: Addison-Wesley.
• Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-84-7476-631-8. OCLC 871814053.