¿Existen condiciones necesarias y suficientes para la existencia de un circuito, o un conjunto disjunto de circuitos, que pase una vez por cada vértice en un grafo dirigido?
Respuestas
¿Demasiados anuncios?
Según el texto clásico "Computers and Intractability, A Guide to the Theory of NP-Completeness" de Garey y Johnson, el siguiente problema:
Partición en subgrafos hamiltonianos
Dado un grafo dirigido $G=(V,A)$ , puede dividir los vértices en conjuntos disjuntos $V_1, V_2, \dots, V_k$ para algunos $k$ tal que cada $V_i$ contiene al menos tres vértices y induce un subgrafo de $G$ que contiene un Circuito Hamiltoniano.
es NP-Completo, por reducción a partir de 3SAT.
El libro también menciona que si permitimos que cada $V_i$ contener al menos dos vértices, entonces esto se puede resolver en tiempo polinómico utilizando técnicas de Emparejamiento.
John Fouhy
Puntos
759
Una colección de ciclos disjuntos que cubren todos los vértices de un grafo (no dirigido) se conoce como factor 2. Este documento hace referencia a un criterio de Tutte para la existencia de éstas, que, parafraseando a los autores, en cierto sentido resuelve completamente el problema. Es el Teorema 1 de la página 2, que apunta a "Los factores de los grafos" de Tutte (1952).
Lorin Hochstein
Puntos
11816
No creo que se conozca ninguno. Una búsqueda rápida en la web dio un artículo de Gutin y Yeo que también remite al capítulo 1 del Dígrafos - Teoría, algoritmos y aplicaciones de Bang-Jensen y Gutin (Springer Monographs, ISBN: 978-1-84800-997-4).
En cualquier caso, si hubiera condiciones necesarias y suficientes, entonces tomar cualquier grafo y sustituir cada arista por un par de aristas dirigidas que van de un lado a otro te daría una caracterización de los grafos hamiltonianos, si no me confundo mucho, que no se sabe.
