Grafi e retiStrette di mano e appuntamenti

Per i grafi di grandi dimensioni, invece di contare tutti gli spigoli, potremmo provare a trovare una semplice formula che ci dice il risultato per qualsiasi numero di ospiti. Ognuna delle ${n} persone alla festa stringe la mano a ${n-1} altre. Ciò rende ${n} × ${n-1} = ${n×(n-1)} strette di mano in totale. Per n persone, il numero di strette di mano sarebbe n×n−1n×n+1n2.

Purtroppo questa risposta non è del tutto corretta. Notare come le prime due voci nella riga superiore sono in realtà le stesse, invertite. In effetti, abbiamo contato ogni stretta di mano due volteuna voltatre volte, per ciascuna delle due persone coinvolte. Ciò significa che il numero corretto di strette di mano per ${n} ospiti è ${n}×${n-1}2=${n*(n-1)/2}.

I grafi delle strette di mano sono speciali perché ogni vertice è collegato ad ogni altro vertice. I grafi con questa proprietà sono chiamati grafi completi. I grafi completi con 4 vertici sono spesso abbreviati come K4, i grafi completi con 5 vertici sono noti come K5 e così via. Abbiamo appena dimostrato che un grafo completo con n vertici, Kn, ha n×n−12 spigoli.

Un altro giorno, sei invitato ad un evento di speed dating per ${m} ragazzi e ${f} ragazze. Ci sono molti tavolini e ogni ragazzo trascorre 5 minuti con ciascuna delle ragazze. Quanti "appuntamenti" individuali vengono svolti in totale?

I grafi bipartiti con due serie di dimensioni x e y sono spesso scritti come Kx,y. Hanno x×yx+y2x−y spigoli, il che significa che nell'esempio precedente vengono svolti ${m} × ${f} = ${m×f} appuntamenti.