Ordenar los vértices de un grafo para que los pares adyacentes estén conectados

Question

Se me dan fatal este tipo de problemas de matemáticas discretas, así que me planteo aquí el siguiente problema: Dado un gráfico conectado $G$ con vértices V[i], encontrar un ordenamiento P[] de sus vértices tal que exista una arista entre V[P[1]] y V[P[2]], y exista una arista entre V[P[3]] y V[P[4]], etc. Básicamente, el ordenamiento debe ser tal que cada par sucesivo de vértices en el ordenamiento esté conectado por una arista. Supongamos que existe una solución. Sólo necesito algún algoritmo para resolver este problema, y ni siquiera tiene que ser necesariamente tan eficiente, ya que el gráfico tendrá como máximo algo así como 30 vértices.

Para los curiosos: el contexto de este problema está en generar la ordenación de los índices de una matriz dispersa para garantizar la existencia de una factorización LDL^T de bloque 2x2. El gráfico corresponde al patrón no nulo de un bloque diagonal de la matriz con diagonal cero, y necesito garantizar que todos los bloques 2x2 son de rango completo.

Answer 1

Lo que quieres es un Trayectoria hamiltoniana . Averiguar si existen para un gráfico dado es NP-completo, así que no esperes ningún inteligente algoritmo a la superficie. Sin embargo, el caso de 30 vértices podría resolverse por fuerza bruta.

Editar : oops, no me fijé en que sólo había que alinear cada dos pasos de la secuencia con una arista. En ese caso lo que quieres es un cobertura mínima de los bordes o un coincidencia perfecta/casi perfecta que se puede encontrar en un tiempo polinómico -- véase el artículo de Wikipedia enlazado.

Si tienes un número impar de vértices, supongo que puedes permitirte que el último vértice de la ordenación no toque ninguna arista específica; una aproximación completamente ingenua a esto sería iterar a través de los vértices hasta encontrar uno tal que el gráfico menos ese vértice pueda ser cubierto por $\frac{|V|-1}{2}$ bordes.

Answer 2

Esto es problema de coincidencia máxima , resoluble en tiempo polinómico por El algoritmo de Edmond .