Comment voulez-vous résoudre cette théorie graphique problème de poignée de main en python?

Question

Je suis diplômé collège l'année dernière avec un diplôme en psychologie, mais j'ai aussi pris beaucoup de maths pour le plaisir. J'ai récemment reçu le livre « Théorie des graphes d'introduction » par Gary Chartrand pour rafraîchir mes maths et avoir du plaisir. Voici un exercice du livre que je trouve particulièrement befuddling:

  

Supposons que vous et votre mari assisté   une partie avec trois autres mariés   des couples. Plusieurs poignées de main ont   endroit. Personne ne lui serra la main avec lui-même   (Ou elle-même) ou avec son (ou ses)   conjoint, et personne ne serra la main   la même personne plus d'une fois. Après   toutes les poignées de main a été achevée,   supposons que vous avez demandé à chaque personne,   y compris votre mari, combien de mains   il ou elle avait secoué. Chaque personne a   une réponse différente. a) Combien de mains   Avez-vous secoué? b) Combien de mains ont   votre shake mari?

Maintenant, j'ai raisonne à ce sujet pendant un certain temps, et en essayant de dessiner des graphiques exemples qui pourraient illustrer une solution, mais je suis à venir les mains vides. Ma logique est la suivante: il y a 8 sommets différents dans le graphique, et 7 d'entre eux ont des degrés différents. Les valeurs pour les degrés doivent donc être 0, 1, 2, 3, 4, 5, 6, et x. Le nombre de degrés pour un couple marié est (0, 6). Étant donné que tous les graphiques ont un nombre pair de sommets impairs, x doit être soit 5, 3 ou 1.

Quelle est votre solution à ce problème? Et, si vous pouvez le résoudre en python, comment voulez-vous faire?

(python is fun.)

Vive.

Answer 1

La chose agréable au sujet de ce problème est que vous n'avez pas vraiment besoin de résoudre le graphique si vous ne voulez pas. Vous êtes en fait très proche. Vous pensé qu'un couple a multiplicités (6,0). Le reste des sommets ne sont pas différenciés les uns des autres par rapport au premier couple et vous avez les mêmes règles pour ce sous-graphe. Ainsi, les multiplicités sous-graphe sont 0,1,2,3,4, x et il y a un certain couple avec multiplicités (4,0). Ce couple a multiplicités (5,1) dans le graphique complet. Donc, comme vous itérer le processus que vous conclurez vos couples ont multiplicités (6,0), (5,1), (4,2), (3,3). Et bien sûr, vous devez avoir la multiplicité x = 3 pour que votre mari a secoué 3 mains.

Answer 2

Je pense que cette liste de contiguïté représente une solution:

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}

Notez que chaque sommet même est mariée au sommet un de moins que lui-même. Vous êtes 8.

Je sorte de la solution intuitionnée. Réfléchit pendant quelques minutes, puis réalisé que chaque couple doit avoir un diplôme combiné de 6 pour que cela fonctionne. Ensuite, il suffit compris comment cela devrait fonctionner.

Qu'est-ce que Steven dit est que vous avez déduit qu'il doit y avoir un couple avec degrés (0,6) et tout le monde (1, 2, 3, 4, 5, x). Considérons maintenant le sous-graphe créé en supprimant ce premier couple. Le « mari » n'a pas serrer la main de quelqu'un, alors il aura aucun effet. La « femme » a secoué tout le monde est, vous aurez donc besoin de soustraire 1 de tous les autres degrés. Donc, vous avez un graphique avec (0, 1, 2, 3, 4, x-1), où appliquent les mêmes règles. De là, vous pouvez utiliser le même processus de pensée que vous avez utilisé pour déterminer l'existence de la (0,6) En couple pour comprendre l'existence d'un couple (1,5). Il va en fait être (0,4), mais vous devez ajouter 1 à la fin parce que c'est le sous-graphe sans compter les deux premières.

Juste continuez à répéter jusqu'à ce que vous êtes en bas à quelqu'un et le terme x, et vous devriez obtenir x = 3.