Glosar

Selectați unul dintre cuvintele cheie din stânga ...

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

Timp de citit: ~15 min

Ai fost invitat la o minunată petrecere de naștere alături de prieteni. Inclusiv tu și gazda, există ${hnd} oameni prezenți.

Seara, pe măsură ce oaspeții se pregătesc să plece, toată lumea dă mâna cu toți ceilalți. Câte strângeri de mână sunt în total?

Putem reprezenta strângerile de mână folosind un grafic: fiecare persoană este și fiecare strângere de mână este .

Acum este ușor să numeri numărul de muchii din grafic. O găsim acolo cu ${hnd} oameni, există ${hnd*(hnd-1)/2} strângeri de mână.

Î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 .

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

În acest caz, graficul corespunzător este format din două seturi de vârfuri separate. Fiecare vertex este conectat la toate vârfurile din setul , dar niciunul dintre vârfurile setul . Graficele care dispun de acest aspect se numesc grafice bipartite .

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

Archie