Glossari

Seleccioneu una de les paraules clau de l’esquerra ...

Gràfics i xarxesEnganxaments de mans i cites

Temps de lectura: ~15 min
Aquesta pàgina ha estat traduïda automàticament i pot contenir errors. Poseu-vos en contacte si voleu ajudar-nos a revisar les traduccions.

Ha estat convidat a una meravellosa festa d’aniversari amb els teus amics. Inclosos tu mateix i l’amfitrió, n’hi ha ${hnd} gent present.

Al vespre, quan els convidats es disposen a sortir, tothom dóna la mà amb els altres. Quants cops de mà hi ha en total?

Podem representar els cops de mà mitjançant un gràfic: cada persona és , i cada cop de mà és .

Ara és fàcil comptar el nombre d'arcs del gràfic. Ho trobem amb això ${hnd} gent, n’hi ha ${hnd*(hnd-1)/2} encaixades de mans.

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 .

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

En aquest cas, el gràfic corresponent consta de dos conjunts de vèrtexs separats. Cada vèrtex està connectat a tots els vèrtexs conjunt, però cap dels vèrtexs conjunt . Els gràfics que disposen d'aquest disseny s'anomenen gràfics de bipartit .

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