Ordlista

Välj ett av nyckelorden till vänster ...

Grafer och nätverkHandskakningar och dejting

Lästid: ~15 min

Du har blivit inbjuden till en underbar födelsedagsfest med dina vänner. Inklusive dig själv och värden finns det ${hnd} människor närvarande.

På kvällen, när gästerna är redo att lämna, skakar alla hand med alla andra. Hur många handskakningar är det totalt?

Vi kan representera handskakningarna med hjälp av en graf: varje person är , och varje handskakning är .

Nu är det enkelt att räkna antalet kanter i diagrammet. Vi finner det där med ${hnd} människor, det finns ${hnd*(hnd-1)/2} handslag.

I stället för att räkna alla kanter i stora diagram kan vi också försöka hitta en enkel formel som berättar resultatet för valfritt antal gäster.

Var och en av ${n} folk på festen skakar hand med ${n-1} andra. Det gör ${n} × ${n-1} = ${n×(n-1)} totalt handskakningar. För n människor skulle antalet handskakningar vara .

Tyvärr är detta svar inte helt rätt. Lägg märke till hur de två första posterna på den översta raden är faktiskt samma, bara vänt runt.

Vi har faktiskt räknat varje handskakning , en gång för var och en av de två inblandade. Detta betyder att rätt antal handskakningar för ${n} gäster är ${n}×${n-1}2=${n*(n-1)/2} .

Handskakningsgraferna är speciella eftersom varje toppunkt är ansluten till varje annan toppunkt. Grafer med den här egenskapen kallas kompletta grafer . Den kompletta grafen med 4 vertikaler förkortas ofta som K4 är den kompletta grafen med 5 vertikaler känd som K5 , och så vidare.

Vi har precis visat att en komplett graf med n vertex, Kn , har n×n12 kanter.

På en annan dag är du inbjuden till ett speed dating-evenemang för ${m} pojkar och ${f} flickor. Det finns många små bord och varje pojke tillbringar 5 minuter med var och en av flickorna. Hur många enskilda "datum" är det totalt?

I detta fall består motsvarande graf av två separata uppsättningar av hörn. Varje topp är ansluten till vertikaler uppsättning, men ingen av topparna i uppsättning. Grafer som har denna layout kallas bipartitgrafer .

Den tvåpartsgrafen med två uppsättningar av storlek x och y skrivs ofta som Kx,y . Det har kanter, vilket betyder att i exemplet ovan finns det ${m} × ${f} = ${m×f} datum.

Archie