Graphes et réseauxPoignées de main et fêtes
Vous avez été invité à une fête d'anniversaire extravagante. Vous et l'hôte inclus,
Le soir, alors que les invités se préparent à partir, tout le monde se serre la main. Combien de poignées de main y a-t-il au total?
Nous pouvons représenter les poignées de main à l'aide d'un graphique: chaque personne est
Il est maintenant facile de compter le nombre d'arêtes dans le graphique. Nous constatons que là-bas avec ${hnd} personnes, il y a ${hnd*(hnd-1)/2} poignées de main.
![](/content/graph-theory/images/party.jpg)
Plutôt que de compter toutes les arêtes dans les grands graphiques, nous pourrions également essayer de trouver une formule simple nous indiquant le résultat pour tout nombre d'invités.
Chacune des
${handshakeTable(n)}
Malheureusement, cette réponse n’est pas tout à fait correcte: nous avons compté chaque poignée de main
Par exemple,
Les graphiques de poignées de mains sont spéciaux car chaque sommet est connecté à tous les autres sommets. Les graphes avec cette propriété sont appelés graphes complets. Le graphe complet à 4 sommets est souvent abrégé en
Nous venons de montrer qu'un graphe complet avec
![](/content/graph-theory/images/flags.jpg)
Un autre jour, vous êtes invité à un événement de speed dating pour
Dans ce cas, le graphe correspondant est constitué de deux ensembles distincts de sommets. Chaque sommet est connecté à tous les sommets
Le graphe biparti avec deux ensembles de taille x et y est souvent écrit sous la forme