Teorija grafova, grana diskretne matematike koja se bavi grafovima, vrstom matematičkih objekata,[1]:1 jer njima možemo modelirati složene probleme veoma jednostavno.[1]:3[1]:1
U matematici i računarstvu pod ovom se teorijom smatra se proučavanje matematičkih struktura (grafova) korištenih radi predstavljanja odnosa koje uključuju dva elementa određene kolekcije. Graf je u gruboj definiciji skup objekata: vrhova, točaka ili čvorova. Povezuju ih veze bridovi odnosno crte (linije). Uz dani skup objekata čvorova i drugi skup objekata bridova, definicija grafa je odnos između tih skupova: svaki brid spaja par čvorova. Grafove se prikazuju crtanjem točaka za svaki vrh i povlačenjem luka između dvaju vrhova, ako ih povezuje brid. Kod usmjerenog grafa, smjer se navodi crtanjem strijelice. Svakom se bridu može pridružiti realan broj, čime je graf proširen težinskom funkcijom i to je težinski graf. Npr. kada graf predstavlja mrežu cesta, težinska funkcija je npr. duljina svakog puta.[2]
Začetak teorije grafova u svezi je s jednim problemom iz stvarnog života. Radi se o problemu sedam königsberških mostova. U naravi po današnjim je mjerilima to logistički problem. Švicarski matematičar Leonhard Euler 1736. godine postavio i riješio taj problem. Objavio je 1741. godine članak Solutio problematis ad geometriam situs pertinentis u časopisu Commentarii academiae scientiarum Petropolitanae, u kojem je formulirao i riješio ovaj problem i ovaj se rad smatra prvim radom u teoriji grafova.[2]
Riječ graf ušla je u široku uporabu tek 1936. kad je Dénes Kőnig objavio monografiju[3] Theorie der endlichen und unendlichen Graphen.[4] Ta se godina uzima kao trenutak osnutka teorije grafova kao samostalne matematičke discipline. 1950-ih teorija dobiva na zamahu i procvat kad su se razvile komunikacijske, biheviorističke znanosti i tehnologija.[3]
Teorija grafova ima široke primjene u različitim disciplinama te njome razmatramo strukture kojima možemo modelirati mnogo problema iz svakodnevnice.[2] Mnogo se primjenjuje na području računalnih mreža, npr. na područjima algoritma usmjeravanja, traženja puteva kroz mrežu te opisivanju topologije mreže.[1]:1
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
