¿Cómo resolvería este problema gráfico de la teoría apretón de manos en Python?

Question

Me gradué de la universidad el año pasado con un título en psicología, sino también Tomé un montón de matemáticas para la diversión. Hace poco recibí el libro "introductoria teoría de grafos" por Gary Chartrand poner al día mis matemáticas y pasar un buen rato. Aquí es un ejercicio del libro que estoy encontrando en particular confundiendo:

Supongamos que usted y su marido asistió una fiesta con otros tres casado parejas. Varios apretones de manos tomaron sitio. Nadie dio la mano a sí mismo (O ella) o con su (o ella) cónyuge, y nadie dio la mano la misma persona más de una vez. Después todo el protocolo de enlace se completó, supongamos que se le pidió a cada persona, incluyendo su marido, cuántas manos él o ella había sacudido. Cada persona dio una respuesta diferente. a) ¿Cuántas manos ¿Ha agitado? b) ¿Cuántas manos hicieron su batido marido?

Ahora, he estado razonamiento acerca de esto por un tiempo, y tratando de dibujar gráficos de ejemplo que podrían ilustrar una solución, pero ya voy con las manos vacías. Mi lógica es la siguiente: hay 8 vértices diferentes en el gráfico, y 7 de ellos tienen diferentes grados. Los valores para los grados deben por lo tanto ser 0, 1, 2, 3, 4, 5, 6, y x. El # de grados para una pareja casada es (0, 6). Desde todos los gráficos tienen un número par de vértices impares, x debe ser o 5, 3, o 1.

¿Cuál es su solución a este problema? Y, si pudiera resolverlo de pitón, ¿cómo hacerlo?

(python is fun.)

Saludos.

Answer 1

Lo bueno de este problema es que realmente no necesita para resolver el gráfico si no quiere. Esté muy cerca. Usted calculó que una pareja tiene multiplicidades (6,0). El resto de los vértices no se diferencian el uno del otro con respecto a la primera pareja y tiene las mismas reglas para que el subgrafo. Así las multiplicidades del gráfico secundario son 0,1,2,3,4, X y hay alguna pareja con multiplicidades (4,0). Esa pareja tiene multiplicidades (5,1) en el gráfico completo. Así como usted iterar a través del proceso que concluirá sus parejas tienen multiplicidades (6,0), (5,1), (4,2), (3,3). Y, por supuesto, debe tener multiplicidad x = 3 para que su marido sacudió 3 manos.

Answer 2

creo que esta lista de adyacencia representa una solución:

1 ->  {}
2 ->  {3, 4, 5, 6, 7, 8}
3 ->  {2, 5, 6, 7, 8}
4 ->  {2}
5 ->  {2, 3, 7, 8}
6 ->  {2, 3}
7 ->  {2, 3, 5}
8 ->  {2, 3, 5}

Tenga en cuenta que cada vértice aún está casada con el vértice inferior a sí mismo. Estás 8.

Yo como que intuyó la solución. Pensó por unos minutos y luego se dio cuenta de que cada pareja debe tener un grado combinado de 6 para que esto funcione. A continuación, sólo descubierto la manera que debería funcionar.

Lo que Steven está diciendo es que usted ha deducido que debe haber un par de grados (0,6) y todos los demás (1, 2, 3, 4, 5, x). Consideremos ahora el subgrafo creado por la eliminación de la primera pareja. El "marido" no estrechar la mano de alguien, por lo que tendrá ningún efecto. La "esposa" sacudió de todos, por lo que tendrá que restar 1 a todos los demás grados. Por lo tanto, usted tiene un gráfico con (0, 1, 2, 3, 4, x-1), en los que se aplican las mismas reglas. A partir de aquí, se puede utilizar el mismo proceso de pensamiento que utilizó para determinar la existencia de la (0,6) par de averiguar la existencia de un (1,5) pareja. En realidad va a ser (0,4), pero hay que añadir al menos 1 al final, porque este es el subgrafo sin contar la primera pareja.

Solo sigue repitiendo hasta que esté a alguien y el término x, y usted debe obtener x = 3.