Gràfics i xarxesEnganxaments de mans i cites

En lloc de comptar totes les vores en gràfics grans, també podríem intentar trobar una fórmula senzilla que ens indiqui el resultat per a qualsevol nombre de convidats.

Cadascun dels ${n} la gent de la festa dóna la mà ${n-1} d’altres. Que fà ${n} × ${n-1} = ${n×(n-1)} encaixades de mans en total. Per a n persones, el nombre de cops de mà seria n×n−1n×n+1n2 .

Malauradament aquesta resposta no és del tot correcta. Observeu com les dues primeres entrades a la fila superior en realitat són els mateixos, simplement han voltat.

De fet, hem comptat cada cop de mà dues vegades un cop tres vegades , una vegada per cadascuna de les dues persones implicades. Això significa que el nombre correcte de cops de mà ${n} convidats ho és ${n}×${n-1}2=${n*(n-1)/2} .

Els gràfics de mà són especials perquè cada vèrtex està connectat a tots els altres vèrtexs. Els gràfics amb aquesta propietat s’anomenen gràfics complets . El gràfic complet amb 4 vèrtexs sovint s’abreuja com K4 , es coneix com a gràfic complet amb 5 vèrtexs K5 , etcètera.

Acabem de demostrar que amb un gràfic complet n vèrtexs, Kn , té n×n−12 vores.

En un dia diferent, se us convida a un esdeveniment de cites ràpides ${m} nois i ${f} noies. Hi ha moltes taules petites i cada noi passa 5 minuts amb cadascuna de les noies. Quantes “dates” individuals hi ha en total?

El gràfic bipartit amb dos conjunts de mida x i y s’escriu sovint com Kx,y . Té x×yx+y2x−y vores, cosa que significa que en l’exemple anterior n’hi ha ${m} × ${f} = ${m×f} dates.