Riječnik

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

Grafikoni i mrežeUvod

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

Svakodnevno smo okruženi bezbroj veza i mreža: prometnice i željezničke pruge, telefonske linije, internet, elektronički sklopovi, pa čak i molekularne veze. Postoje čak društvene mreže između prijatelja i obitelji. Možete li smisliti još neke primjere?

Cestovne i željezničke mreže

Računalni čipovi

Lanci za opskrbu

Prijateljstva

Neuronske veze

Internet

U matematici se svi ovi primjeri mogu predstaviti kao grafikoni (da se ne brkaju sa grafom funkcije). Graf se sastoji od određenih točaka nazvanih , od kojih su neke povezane .

Teorija grafova je proučavanje grafova i njihovih svojstava. To je jedno od najuzbudljivijih i najvidljivijih područja matematike i ima bezbroj važnih primjena.

Izgled jednostavnih grafova možemo nacrtati pomoću krugova i linija. Položaj vrhova i duljina rubova nebitni su - brine nas samo kako su oni povezani međusobno. Rubovi se čak mogu prelaziti i ne moraju biti ravni.

U nekim grafovima rubovi idu samo u jednom smjeru. To se zove usmjereni grafikon.

Neki se grafovi sastoje od više skupina vrhova koji međusobno nisu povezani rubovima. Ti su grafovi nepovezani.

Ostali grafovi mogu sadržavati više rubova između istih parova vrhova ili vrhova koji su povezani sami (petlje).

Iz postojećeg grafikona možemo stvoriti nove grafikone uklanjajući neke vrhove i rubove. Rezultat se zove podgraf. Ovdje možete vidjeti još nekoliko primjera grafova, s obojenim rubovima i vrhovima koji ukazuju na mogući podgraf:

Kažemo da je naredba grafikona broj vrhova koje ima. stupanj vrha je broj rubova koji se nalaze u toj vrhovi.

Naredba:

Naredba:

Stupanj:

Stupanj:

Grafovi koji se sastoje od jedne petlje vrhova nazivaju se ciklusom. Svi ciklusi imaju .

Opremljeni ovim novim definicijama, istražimo neka fascinantna svojstva i primjene grafikona.

Archie