Grafikoni i mrežeRukovanje i druženje

Umjesto da prebrojimo sve rubove u velikim grafovima, mogli bismo pokušati pronaći jednostavnu formulu koja će nam reći rezultat za bilo kojeg broja gostiju , Svaki od ${n} ljudi na zabavi rukuje se s ${n-1} drugima. To čini ${n} × ${n-1} = ${n×(n-1)} rukovanja ukupno. Za n ljudi, broj rukovanja bi bio n×n−1n×n+1n2.

Nažalost, ovaj odgovor nije sasvim tačan. Primjetite kako prva dva unosa u gornji red su zapravo isti, samo ih je okolo. Zapravo smo brojili svaki stisak ruke dva putaoncethree times, jednom za dvoje uključenih ljudi. To znači da je točan broj rukovanja za ${n} gostiju ${n}×${n-1}2=${n*(n-1)/2}.

Grafikoni stiska ruku su posebni jer je svaki vrh povezan sa svakom drugom vrhom. Grafikoni s ovim svojstvom nazivaju se kompletni grafikoni. Kompletni graf s 4 vrha često se skraćuje kao K4, a čitav graf s 5 vrhova poznat je kao K5 i tako dalje. Upravo smo pokazali da kompletan graf sa n vrhovima, Kn, ima n×n−12 rubove.

Drugog dana, pozvani ste na brzi sastanak za ${m} dečaka i ${f} djevojke. Mnogo je malih stolova i svaki dječak provodi 5 minuta sa svakom od djevojčica. Koliko pojedinačnih „datuma“ ima ukupno?

Dvostrani graf s dva skupa veličina x i y često se piše kao Kx,y. Ima x×yx+y2x−y rubove, što znači da u gornjem primjeru postoje datumi ${m} × ${f} = ${m×f}