Grafer och nätverkHandskakningar och dejting

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 n×n−1n×n+1n2 .

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 två gånger en gång tre gånger , 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×n−12 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?

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