¿Cómo determinar si un grafo tiene un juego perfecto?

Question

Estoy practicando para un desafío matemático y se preguntó si, en el siguiente gráfico se tiene un perfecto maridaje. He probado a conectar al azar de los nodos, pero no podía encontrar una manera de conectar el nodo de tal manera que resultaría en un perfecto maridaje, así que estoy asumiendo que no es posible.

Pero, ¿cómo sabe que no es realmente posible? Hay un rápido (estructurado) para determinar si hay una perfecta coincidencia o no, y cómo?

Sólo me di cuenta de que el número de nodos debe ser, incluso, que es verdadero en este caso, ya que hay 42 nodos.

Answer 1

No hay ningún tipo de vinculación:

Observamos que al quitar el $12$ rojo los vértices, en el gráfico se divide en $14$ componentes, cada uno de ellos tener un número impar de vértices.

Si hubo un maridaje perfecto, cada uno de los componentes tiene un par de conectar a alguna red vértice, pero hay muy pocos de ellos.

Esta condición en impar de componentes, de hecho, caracteriza maridaje perfecto y se llama la Tutte teorema.

Answer 2

Considere los dos de la izquierda-la mayoría de los hexágonos. El borde entre ellos está en un perfecto maridaje, o no. Si es así, entonces los otros vértices en estos 2 hexágonos necesita para formar parejas para un perfecto maridaje. Si el centro del borde no está en la coincidencia, entonces el perímetro debe ser alternativamente involucrados en la coincidencia de todos en torno a los dos hexágonos.

De cualquier manera, nos quite los dos hexágonos y una serie de forzado de los bordes para incluir antes tenemos que omitir uno de los vértices en el segundo hexágono.

No perfecto maridaje.

---

Yo estaba tratando de traducir mi demostración en el vértice de eliminación de la prueba de formulario utilizado por user2345215, porque sabía que no tenía la necesidad de ambos lados de la gráfica... y aquí está:

La izquierda tres vértices marcados determinar que los dos LH h debe ser autónomo para realizar una coincidencia, entonces el siguiente marcado cuatro vértices adjuntar a la forzada "se mueve". La división de la gráfica es de 7 vértices eliminado para dejar 9 impar-vértice-recuento de las secciones, incluyendo la de 21 de vértices de la sección de la derecha.