Matemáticas - Teoría de grafos

cobertura de vértices (en inglés, vertex cover) o simplemente cobertura de un grafo, es un conjunto de vértices tales que cada aristadel grafo es incidente a al menos un vértice del conjunto.

El problema de encontrar la menor cobertura de vértices en un grafo se denomina problema de la cobertura de vértices. En teoría de la complejidad computacional se ha demostrado que este es un problema NP-completo.

La cobertura de vértices y aristas está muy relacionada con los conjuntos independientes yapareamientos o matchings.

Ejemplos de coberturas de vértices (conformadas por los vértices en rojo).

Ejemplos de coberturas de vértices mínimas.

Una cobertura de vértices para un grafo G es un conjunto de vértices V en los que cada arco de G incide al menos en un nodo de V. Lacobertura de vértices mínima es la más pequeña de las coberturas de vértices. El número de cobertura de vértices ${\displaystyle \omega _{V}(G)\,}$ para un grafo G es el tamaño de la cobertura de vértices mínima.

• Para cualquier grafo, el conjunto de todos sus vértices es trivialmente una cobertura de vértices.
• Un grafo bipartito completo ${\displaystyle G_{m,n}\,}$ tiene ${\displaystyle \omega _{V}(G_{m,n})=\min \lbrace m,n\rbrace \,}$ y ${\displaystyle \omega _{E}(G_{m,n})=\max \lbrace m,n\rbrace \,}$.

coeficiente de agrupamiento (mencionado en la literatura también como clustering coefficient) de un vértice en un grafocuantifica qué tanto está de agrupado (o interconectado) con sus vecinos. Se puede decir que si el vértice está agrupado como unclique (grafo completo) su valor es máximo, mientras que un valor pequeño indica un vértice poco agrupado en la red. Duncan J. Watts y Steven Strogatz fueron los primeros en idear este coeficiente, en 1998¹ para determinar si un grafo es una red de mundo pequeño. Se suele representar formalmente como ${\displaystyle C_{i}}$. En algunas ocasiones dentro del mundo de la teoría de redes se denomina a este coeficiente también como transitividad.

Definición Formal

Un grafo ${\displaystyle G=(V,E)}$ formalmente consiste en un conjunto de vértices ${\displaystyle V}$ y en un conjunto de enlaces ${\displaystyle E}$ entre ellos. Un enlace ${\displaystyle e_{ij}}$ conecta dos vértices ${\displaystyle i}$ y ${\displaystyle j}$. La vecindad de vértices N para un vértice ${\displaystyle v_{i}}$ se define como aquellos vértices inmediatamente conectados de tal forma que:

${\displaystyle N_{i}=\{v_{j}\}:e_{ij}\in E\lor e_{ji}\in E.}$

El grado, que se representa como ${\displaystyle k_{i}}$ de un vértice, es definido como el número de vértices enlazados con uno dado. En esta expresión además se tiene que ${\displaystyle |N_{i}|}$.

El coeficiente de agrupamiento ${\displaystyle C_{i}}$ para un vértice ${\displaystyle v_{i}}$ está dado por la proporción entre los enlaces conectados con sus vecinos dividido entre el número de enlaces existentes en un clique en el que la conectividad es máxima. Para un grafo dirigido, ${\displaystyle e_{ij}}$ es distinto de ${\displaystyle e_{ji}}$, y por lo tanto para cada vecino ${\displaystyle N_{i}}$ hay ${\displaystyle k_{i}(k_{i}-1)}$ enlaces que podrían existir entre los vértices de la vecindad (${\displaystyle k_{i}}$ es el grado del vértice i para el total (entrantes + salientes)). De esta forma el grado de agrupamiento en los grafos dirigidos está dado por:

${\displaystyle C_{i}={\frac {|\{e_{jk}\}|}{k_{i}(k_{i}-1)}}:v_{j},v_{k}\in N_{i},e_{jk}\in E.}$

Un grafo no dirigido tiene la propiedad de que tanto los enlaces ${\displaystyle e_{ij}}$ y ${\displaystyle e_{ji}}$ son considerados idénticos. Por lo tanto, si un vértice ${\displaystyle v_{i}}$posee ${\displaystyle k_{i}}$ vecinos, entonces existirían ${\displaystyle {\frac {k_{i}(k_{i}-1)}{2}}}$ enlaces entre los vértices de su vecindad. De esta forma el coeficiente de agrupamiento de grafos no dirigidos pueden ser definidos como:

${\displaystyle C_{i}={\frac {2|\{e_{jk}\}|}{k_{i}(k_{i}-1)}}:v_{j},v_{k}\in N_{i},e_{jk}\in E.}$

Sea ${\displaystyle \lambda _{G}(v)}$ el número de triángulos en ${\displaystyle v\in V(G)}$ para un grafo no dirigido ${\displaystyle G}$. Esto es, ${\displaystyle \lambda _{G}(v)}$ es el número de sub-grafos de ${\displaystyle G}$con tres enlaces y tres vértices, uno de los cuales es ${\displaystyle v}$. Sea ${\displaystyle \tau _{G}(v)}$ el número de tripletes en ${\displaystyle v\in G}$. Esto es, ${\displaystyle \tau _{G}(v)}$ es núemro de sub-grafos (no necesariamente inducidos) con dos enlaces y 3 vértices, uno de los cuales es ${\displaystyle v}$ y tal que ${\displaystyle v}$ es incidente a ambos enlaces. De esta forma se puede definir también el coeficiente de agrupamiento como

${\displaystyle C_{i}={\frac {\lambda _{G}(v)}{\tau _{G}(v)}}.}$

Es muy simple mostar que de las dos definiciones precedentes son similares, ya que:

${\displaystyle \tau _{G}(v)=C({k_{i}},2)={\frac {1}{2}}k_{i}(k_{i}-1).}$

Esta medida es igual a 1 si cada vecino está conectado a ${\displaystyle v_{i}}$ está conectada igualmente a cada uno de los otros vértices en la vecindad, y 0 si no hay vértices que están conectados a ${\displaystyle v_{i}}$ que conectan a otro vértice que es conectado a ${\displaystyle v_{i}}$. El coeficiente de agrupamiento de la red se calcula mediante Watts y Strogatz como la media de los coeficientes de agrupamiento de todos los vértices de la red:

${\displaystyle {\bar {C}}={\frac {1}{n}}\sum _{i=1}^{n}C_{i}.}$

Un grafo se considera como mundo pequeño si el coeficiente de agrupamiento de la red ${\displaystyle {\bar {C}}}$ es significantemente mayor que el que pueda ofrecer un grafo aleatorioconstruido con el mismo conjunto de vértices, y si al mismo tiempo posee una distancia media de pequeño valor.

Empleos

Se suele emplear el coeficiente de agrupamiento en la detección automática de tópicos.

Ejemplo de coeficiente de agrupamiento en un grafo no dirigidoen el que se considera el nodo sombreado como el nodo ${\displaystyle i}$. Los segmentos de líneas negras son enlaces que conectan vecinos de ${\displaystyle i}$, y los segmentos punteados son enlaces inexistentes.

Dado un grafo ${\displaystyle \Gamma }$, la conectividad algebraica de un grafo es el segundo autovalor más pequeño no nulo de la matriz laplaciana ${\displaystyle {\mathcal {L}}(\Gamma )}$¹—por ello se le signa como ${\displaystyle \lambda _{2}}$—. También se denomina salto espectral, gap o parámetro de Fiedler.²

Este autovalor es mayor que cero si y sólo si ${\displaystyle \Gamma }$ es un grafo conexo. La medida de este valor refleja la conectividad del grafo en general, y se ha utilizado para el análisis de la sincronización de nodos en redes. A medida que ${\displaystyle \lambda _{2}}$ se hace más pequeño el grafo adquiere una estructura más modular.

En los modelos para la sincronización de nodos en redes, como el modelo de Kuramoto, la matriz laplaciana surge de manera natural (a través del laplaciano discreto), por lo que la conectividad algebraica da una idea de la facilidad con la que la red se sincronizará. Sin embargo, otras medidas, tales como la media de la distancia también se puede utilizar,³ y, de hecho, la conectividad algebraica está estrechamente relacionado con el inverso de la distancia media.⁴

Al autovector asociado a ${\displaystyle \lambda _{2}}$ se le denomina ${\displaystyle {\vec {u}}_{2}}$ vector de Fiedler , y se usa para la partición de grafos. Por ejemplo, sea:

grafo	matriz laplaciana
	${\displaystyle \left({\begin{array}{rrrrrr}2&-1&0&0&-1&0\\-1&3&-1&0&-1&0\\0&-1&2&-1&0&0\\0&0&-1&3&-1&-1\\-1&-1&0&-1&3&0\\0&0&0&-1&0&1\\\end{array}}\right)}$

El vector de Fiedler es

(0.415, 0.309, 0.069, -0.221, 0.221, -0.794).

Los valores negativos se asocian con el nodo 6, y el punto de articulación entre vecinos, el nodo 4, mientras que los valores positivos están asociados con los otros nodos. El signo de los valores en el vector de Fiedler puede ser utilizado para dividir el gráfos en componentes: {1, 2, 3, 5} y {4, 6}. Por otra parte, el valor de 0,069 (que es cercana a cero) se pueden colocar en una clase propia, la partición del grafo en tres componentes: {1, 2, 5}, {3} y {6 4}.

Este autovalor ha sido investigado ampliamente por ser un invariante muy importante. El principio de Courant-Fischer dice que:⁵

${\displaystyle \lambda _{2}^{\Gamma }=\min _{\begin{array}{r}{\vec {u}}\perp {\vec {1}}\\{\vec {u}}\neq {\vec {0}}\end{array}}{\frac {({\hat {\mathcal {L}}}{\vec {u}},{\vec {u}})}{({\vec {u}},{\vec {u}})}}}$

Fiedler obtiene otra expresión para grafos con pesos ${\displaystyle a_{\mu \nu }}$ no nulos:

${\displaystyle \lambda _{2}^{\Gamma }=2n\min _{\begin{array}{r}{\vec {u}}\perp {\vec {1}}\\{\vec {u}}\neq {\vec {0}}\end{array}}{\frac {\sum _{\mu \nu }{a_{\mu \nu }(u_{\mu }-u_{\nu })^{2}}}{\sum _{\mu \nu }{(u_{\mu }-u_{\nu })^{2}}}}}$

Aplicaciones

La conectividad algebráica da un límite inferior al diámetro de un grafo ${\displaystyle \Gamma }$:

${\displaystyle {\mathtt {diam}}(\Gamma )\geqslant {\frac {4}{n\lambda _{2}^{\Gamma }}}}$