Glossaire

Sélectionnez l'un des mots clés à gauche…

Graphes et réseauxPoignées de main et fêtes

Temps de lecture: ~15 min

Vous avez été invité à une fête d'anniversaire extravagante. Vous et l'hôte inclus, ${hnd} personnes sont présentes.

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 et chaque poignée de main 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.

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 ${n} personnes présentes à la fête serre la main avec ${n-1} autres. Cela fait ${n} × ${n-1} = ${n×(n-1)} poignées de main au total. Pour les n personnes, le nombre de poignées de main serait de .

${handshakeTable(n)}

Malheureusement, cette réponse n’est pas tout à fait correcte: nous avons compté chaque poignée de main , une fois pour chacune des deux personnes impliquées.

Par exemple, les deux premiers les entrées de la rangée supérieure sont en fait les mêmes. Le nombre correct de poignées de main pour ${n} invités est ${n} × ${n-1}2 = ${n*(n-1)/2}.

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 K4, le graphe complet à 5 sommets est appelé K5, etc.

Nous venons de montrer qu'un graphe complet avec n sommets, Kn, a n×n12 arêtes.

Un autre jour, vous êtes invité à un événement de speed dating pour ${m} garçons et ${f} filles. Il y a beaucoup de petites tables et chaque garçon passe 5 minutes avec chacune des filles. Combien de « rencontres » individuelles y a-t-il au total?

Dans ce cas, le graphe correspondant est constitué de deux ensembles distincts de sommets. Chaque sommet est connecté à tous les sommets , mais à aucun des sommets . Les graphes présentant cette présentation sont appelés graphes bipartis.

Le graphe biparti avec deux ensembles de taille x et y est souvent écrit sous la forme Kx,y. Il a arêtes, ce qui signifie qu'il y a dans l'exemple ci-dessus ${m} × ${f} = ${m×f} rencontres.