Come si risolvere questo problema grafico teoria stretta di mano in Python?

Question

Mi sono laureato all'università l'anno scorso con una laurea in psicologia, ma ho anche preso un sacco di matematica per divertimento. Recentemente ho avuto il libro "introduttiva teoria dei grafi" di Gary Chartrand per rispolverare la mia matematica e divertirsi un po '. Ecco un esercizio dal libro che sto trovando particolarmente befuddling:

  

Supponiamo che tu e tuo marito partecipato   una festa con altri tre sposati   coppie. Diversi strette di mano hanno preso   posto. Nessuno strinse la mano a se stesso   (O lei stessa) o con il suo (o lei)   coniuge, e nessuno le mani scosse con   la stessa persona più di una volta. Dopo   tutto l'handshake è stato completato,   supponiamo che lei ha chiesto ogni persona,   compreso il vostro marito, quante mani   lui o lei aveva scosso. Ogni persona ha dato   una risposta diversa. a) Quante mani   lo si agita? b) quante mani hanno fatto   vostro shake marito?

Ora, sto ragionamento su questo per un po ', e cercando di disegnare grafici di esempio che potrebbe illustrare una soluzione, ma sto arrivando a mani vuote. Mia logica è questa: ci sono 8 vertici differenti nel grafico, e 7 di loro hanno gradi differenti. I valori per i gradi devono quindi essere 0, 1, 2, 3, 4, 5, 6, e x. L'° gradi per una coppia sposata è (0, 6). Poiché tutti i grafici hanno un numero pari di vertici dispari, x deve essere o 5, 3 o 1.

Qual è la soluzione a questo problema? E, se si potesse risolvere in pitone, come lo faresti?

(python is fun.)

Saluti.

Answer 1

La cosa bella di questo problema è che non si ha realmente bisogno per risolvere il grafico se non si vuole. Lei è in realtà molto vicino. È pensato che una coppia ha molteplicità (6,0). Il resto dei vertici sono indifferenziati gli uni dagli altri per quanto riguarda la prima coppia e si ha le stesse regole per quel sottografo. Così i molteplicità sub-grafico sono 0,1,2,3,4, x e c'è qualche coppia con molteplicità (4,0). Quella coppia ha molteplicità (5,1) nel grafico completo. Quindi, come si scorre attraverso il processo si concluderà vostre coppie hanno molteplicità (6,0), (5,1), (4,2), (3,3). E, naturalmente, è necessario disporre di molteplicità x = 3 in modo tuo marito strinse 3 mani.

Answer 2

Credo che questa lista di adiacenza rappresenta una soluzione:

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}

Si noti che ogni vertice è sposato anche al vertice uno in meno per sé. Sei 8.

I tipi di intuito la soluzione. Pensò su per qualche minuto e poi si rese conto che ogni coppia deve avere un grado combinato di 6 per questo al lavoro. Poi basta capito come che dovrebbe funzionare.

Che Steven sta dicendo è che hai dedotto che ci deve essere una coppia con gradi (0,6) e tutti gli altri (1, 2, 3, 4, 5, x). Consideriamo ora il sottografo creato rimuovendo quella prima coppia. Il "marito" non stringere la mano a nessuno, quindi non avrà alcun effetto. La "moglie" scosse di tutti, quindi è necessario sottrarre 1 da tutti gli altri gradi. Quindi, avete un grafico con (0, 1, 2, 3, 4, x-1), in cui si applicano le stesse regole. Da qui, è possibile utilizzare lo stesso processo di pensiero è stato utilizzato per determinare l'esistenza del (0,6) Coppia di capire l'esistenza di una (1,5) coppia. Sarà effettivamente essere (0,4), ma è necessario aggiungere 1 alla fine perché questo è il sottografo senza contare la prima coppia.

Basta continuare a ripetere fino a quando sei giù a qualcuno e il termine x, e si dovrebbe ottenere x = 3.