¿Cuáles son algunas de las medidas de conectividad en grafos?

Question

Yo no soy un matemático (yo soy un ingeniero que trabaja en la mejora de sus matemáticas), así que pido disculpas de antemano si mi pregunta es trivial.

Considere la posibilidad de un gráfico de $N$ nodos, con algunos que se definen como criterio para saber si dos nodos están conectados o no. ¿Cuáles son algunas de las medidas de la gráfica de la conexión? No puedo pensar en varias medidas, pero no estoy seguro de cuáles tienen más sentido matemático:

1. Si todo el gráfico está conectado o no. Esta es, sin embargo, un binario medida, y no la captura de gran cantidad de información.
2. El tamaño de la más grande intra-conectado sub gráfico ($0 \leq n \leq N$). Esto, sin embargo, no le dice nada acerca de lo que está ocurriendo en el resto de la gráfica.
3. El número de intra-conectado (pero no inter-conectado) sub-gráficos en el gráfico ($0 \leq n \leq N$).
4. Cada nodo $i\in \{1,2,\dots,N\}$ es asignado un 'score' $s_i\in\{1,2,\dots,N\}$, que mide cómo muchos otros nodos está conectado. Los gráficos', de conexión, a continuación se mide como el promedio de estas calificaciones, es decir,$\sum_i s_i / N$, que se encuentra en el intervalo de $[0,N]$.

El tipo de preguntas que me interesa son como: Es de 4. un matemático de sonido medir? Puede dar lugar a anomalías? Hay mejores medidas que son más robustos?

Por favor, perdóname si no soy lo suficientemente riguroso en mis explicaciones. Como ingeniero, me han sido entrenados para pensar en "intuitivo" (y no formal) de los términos, que a menudo puede ser una gran ayuda, pero otras veces es un obstáculo.

Answer 1

Probablemente la más común de las medidas de conectividad son el borde de la conectividad y el vértice de la conectividad. El vértice de la conectividad, o simplemente la conectividadde un grafo es el número mínimo de vértices usted tiene que quitar antes de que usted puede esperar para desconectar el gráfico. Un grafo se llama $k$-vértice-conectado, o sólo $k$-conectado, si su conectividad es, al menos,$k$. Arista-conectividad y $k$-edge-conectado se definen de manera similar.

Como un ejemplo, supongamos que tenemos un árbol de $T$, con al menos 3 vértices. En un árbol, cualquiera de los dos vértices están conectados por exactamente una ruta de acceso. En particular, la eliminación de cualquier no-interna (es decir, no uno de los extremos) parte de cualquier camino de $T$ desconecta el grafo. Por lo tanto, $T$ tiene el vértice y arista-conectividad $1$. (Necesitamos al menos 3 vértices aquí para garantizar que se nos puede encontrar una ruta de acceso con el interior de los vértices, aunque con 2 vértices todavía tenemos arista-conectividad $1$. Por convención, el árbol con dos vértices tiene conectividad $1$.)

Como otro ejemplo, se puede demostrar (¡inténtelo!) que un ciclo de longitud mayor de 3 ha de borde y el vértice de la conectividad $2$. (Como con los árboles, para un 3-ciclo---no hay tal cosa como un 1 - o 2-ciclo---, el borde de la conectividad todavía tiene sentido y es $2$, pero para el vértice de la conectividad tenemos que recurrir a la convención: tan sólo tenemos que asignar la conectividad $2$).

Answer 2

A veces en matemáticas convertir la pregunta en su cabeza lleva a definiciones útiles. En este caso, nos podemos preguntar cómo algunos extremos son necesarios para eliminar con el fin de desconectar un gráfico. Si no hay un único borde de la eliminación da una desconectado gráfico, decimos que la gráfica es doblemente conectado, etc.

Hay un tema llamado detección de la comunidad que suelto en términos intenta identificar subconjuntos de vértices de un grafo que están más estrechamente relacionados dentro de ellos mismos que de los de otras partes.

Answer 3

La "puntuación" de hablar de en (4) se suele llamar el grado o la valencia de un nodo. El grado medio es, simplemente, $2E/N$ donde $E$ es el número de aristas en el grafo, porque la suma de los grados de todos los nodos cantidades a contar todos los bordes de dos veces. Esta es sin duda una buena medida de frente: en el menor valor posible $0$, el gráfico es sólo un montón de nodos sin bordes; en el mayor valor posible a $N-1$, cada nodo está conectado a todos los otros. Sin embargo, mientras que él no diga usted cómo "denso" que muestra el gráfico, no nos dice nada acerca de la conectividad en el binario sentido... a menos que el valor es muy pequeño o muy grande. Más precisamente, un gráfico con el grado promedio de menos de $2-2/N$ debe ser desconectado; un gráfico con el grado promedio de más de $N-3+2/N$ debe estar conectado.

El artículo de la Wikipedia sobre la conectividad de los gráficos menciona algunas otras medidas que estoy seguro de que usted va a encontrar interesante. Veo algunas otras respuestas están llegando en los que se describen en más detalle.