Grafice și rețeleStrângeri de mână și întâlniri

În loc să numărați toate marginile în grafice mari, am putea încerca, de asemenea, să găsim o formulă simplă care să ne spună rezultatul pentru orice număr de invitați.

Fiecare din ${n} oamenii de la petrecere dau mâna cu ${n-1} alții. Asta face ${n} × ${n-1} = ${n×(n-1)} strângeri de mână în total. Pentru n oameni, numărul de strângeri de mână ar fi n×n−1n×n+1n2 .

Din păcate, acest răspuns nu este chiar corect. Observați cum primele două intrări din rândul de sus sunt de fapt aceleași, doar răsucite.

De fapt, am numărat fiecare strângere de mână de două ori o singura data de trei ori , o dată pentru fiecare dintre cele două persoane implicate. Acest lucru înseamnă că numărul corect de strângeri de mână pentru ${n} oaspeții este ${n}×${n-1}2=${n*(n-1)/2} .

Graficele de strângere de mână sunt speciale, deoarece fiecare vertex este conectat la fiecare alt vertex. Graficele cu această proprietate sunt numite grafice complete . Graficul complet cu 4 vârfuri este adesea prescurtat ca K4 , graficul complet cu 5 vârfuri este cunoscut ca K5 , si asa mai departe.

Tocmai am arătat că un grafic complet cu n noduri, Kn , are n×n−12 margini.

Într-o altă zi, sunteți invitat la un eveniment de întâlnire rapidă pentru ${m} băieți și ${f} fete. Există multe mese mici și fiecare băiat petrece 5 minute cu fiecare dintre fete. Câte „date” individuale există în total?

Graficul bipartit cu două seturi de dimensiuni x și y este adesea scris ca Kx,y . Are x×yx+y2x−y margini, ceea ce înseamnă că în exemplul de mai sus există ${m} × ${f} = ${m×f} datele.