Glossario

Seleziona una delle parole chiave a sinistra ...

Grafi e retiStrette di mano e appuntamenti

Momento della lettura: ~15 min

Sei stato invitato ad una meravigliosa festa di compleanno con i tuoi amici. Oltre a te e al festeggiato, ci sono ${hnd} persone presenti. La sera, mentre gli ospiti si preparano a partire, tutti si stringono la mano con tutti gli altri. Quante strette di mano vengono fatte in totale? Possiamo rappresentare le strette di mano usando un grafo: ogni persona è e ogni stretta di mano è .

Ora è facile contare il numero di spigoli nel grafico. Troviamo che lì con ${hnd} persone, ci sono ${hnd*(hnd-1)/2} strette di mano.

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 .

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 , 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×n12 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?

In questo caso, il grafo corrispondente è costituito da due serie separate di vertici. Ogni vertice è collegato a tutti i vertici , ma nessuno dei vertici . I grafi che hanno questo layout sono chiamati grafi bipartiti.

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