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

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 n × (n – 1)n × (n + 1)n².

${handshakeTable(n)}

Malheureusement, cette réponse n’est pas tout à fait correcte: nous avons compté chaque poignée de main deux foisune foistrois fois, 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×n−12 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?

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