Riječnik

Odaberite jednu od ključnih riječi s lijeve strane ...

Grafikoni i mrežeRukovanje i druženje

Vrijeme čitanja: ~15 min
Ova je stranica automatski prevedena i može sadržavati pogreške. Javite nam se ako nam želite pomoći u pregledu prijevoda!

Pozvani ste na prekrasnu rođendansku zabavu sa svojim prijateljima. Uključujući sebe i domaćina, prisutni su ${hnd} ljudi. Uveče, dok se gosti spremaju da odu, svi odmahnu rukom sa svima ostalima. Koliko ima rukovanja ukupno? Rukovanje možemo predstaviti grafikonom: svaka osoba je , a svaka stisak ruke je .

Sada je lako izbrojiti broj rubova u grafikonu. Otkrivamo da tamo sa ${hnd} ljudima postoje ${hnd*(hnd-1)/2} stisci ruku.

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 .

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

U ovom se slučaju odgovarajući graf sastoji od dva odvojena skupa. Svaka vrhova povezana je sa svim vrhovima u , ali nijedan od vrhova u skupu. Grafovi s ovim izgledom nazivaju se dvostrani grafovi.

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