Eliminación de vértices de grado 2 de un gráfico

Question

Considere la posibilidad de un mapa de un sistema fluvial. Cada punto en el río de la línea es un gráfico de vértice. Algunos puntos de grado 1, en el inicio y el final de un río, algunos tienen un grado > 2, donde los ríos de combinación (o más raramente, dividir) y una carga de vértices los puntos se tienen grado 2 como un río que serpentea a lo largo. Este gráfico se genera a partir de las coordenadas espaciales del río.

Sin embargo, el grado 2 vértices no son pertinentes a la topología de la red fluvial, así que quiere eliminar. Voy a terminar con una especie de "esqueleto" del gráfico, con sólo los vértices de grado 1 o >2 conectado pero sin título-2 vértices.

¿Esta transformación tiene un nombre? No puedo encontrar nada de un poco de investigación, pero a veces puede ser difícil de conseguir a través de toda la teoría de grafos jerga (camarillas, inducida por subdiagramas, etc, etc).

Yo estoy usando la R y la igraph paquete. Yo he programado un proceso iterativo que en repetidas ocasiones se elimina un único grado-2 nodo y se une a sus vecinos hasta sin título-2 vértices son a la izquierda, pero me pregunto si hay un truco que me falta.

Ya quiero que sea más general que sólo las redes fluviales (que son propensos a ser, pero no necesariamente de los árboles) me vas a tener que pensar qué hacer con un gráfico circular donde todos los vértices son de grado 2. Creo que no quiero terminar con un vértice arbitrario con un borde a sí mismo.

De todos modos, tal vez alguien sepa exactamente lo que es esto...

Answer 1

Parece ser que existen varios nombres para esta operación.

Si uno tiene dos aristas $xy$$yz$, la operación de extracción de $xy$ $yz$ mientras que la adición de $xz$ se llama el levantamiento de los bordes $\{xy,yz\}$. Así uno puede repetidamente levante los bordes adyacentes a los vértices de grado 2.

Esto también se conoce como el suavizado de aquí, donde la atenuación es descrito de la misma manera. Así se podría definir la operación de suavizado de un gráfico, como repetidamente el suavizado de los vértices de grado 2.

Answer 2

Mi método incremental fue lento, así que se me ocurrió con un algoritmo que funciona un poco más rápido.

1. Comience con la gráfica de G

2. Tomar el subgrafo de G de grado=2 vértices. Esto tiene que ser desconectado conjunto de simples cadenas (es decir, de dos grados=1 vértices conectados por cero o más grado=2 vértices) o solo (grado cero) vértices

3. Para cada una de las cadenas,

   1. encontrar a los vecinos de los extremos de la cadena de G (esto depende de la gráfica de los valores de ID que se propaga en el subgrafo proceso)

   2. agregar una nueva arista en G, conectando los extremos

   3. eliminar todos los vértices de G en la cadena de

Nota la mejora de la velocidad viene de eliminar potencialmente muchos vértices a la vez y hacer menos aristas. No es realmente un algoritmo de mejora.

Todavía necesita pensar acerca de cómo manejar los bucles y varias aristas y así sucesivamente, pero a riesgo de convertir este en un programa de preguntas y tener que pateó a StackOverflow voy a parar ahora.

Answer 3

No creo que hay un truco que te falta.

Suponiendo que un grafo dirigido, el algoritmo es la siguiente:

Initialize a queue Q of all the vertices

While Q is not empty:
  Pop the top of Q into N

  If N does not have an one incoming and one outgoing edge:
    Continue to the next item in Q

  If N has been seen:
    Continue to the next item in Q

  Mark N as Seen

  Let Up be the node which points into N
  Let Down be the node which N points to

  Create an edge Up-Down with Weight=Weight[Up]+Weight[Down]

  Remove the edges Up-N and N-Down

Se puede ver que cada nodo se agrega a Q sólo una vez y todos los nodos son finalmente eliminado de la Q.

Por lo tanto, el algoritmo se ejecuta en O(N) de tiempo. No hay manera que usted puede hacer mejor que esto. El algoritmo alternativo que usted sugiere en su respuesta puede trabajar más rápido, pero esto es sólo porque de los detalles de implementación.