Teorija grafova
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
- ↑ a b c d FER Arhivirana inačica izvorne stranice od 14. veljače 2019. (Wayback Machine) Mladen Marinović: Teorija grafova (pristupljeno 23. prosinca 2019.)
- ↑ a b c math.e, hvatski matematički elektronički časopis Maja Fošner i Tomaž Kramberger: Teorija grafova i logistika br. 14, ISSN ISSN 1334-6083 (pristupljeno 23. prosinca 2019.)
- ↑ a b Sveučilište J. J. Strossmayera u Osijeku - Odjel za matematiku Iva Gregurić: Bojenje grafova, Osijek, 2011., str. 3, pristupljeno 28. veljače 2020.
- ↑ Kőnig, Dénes. 1990. Theory of finite and infinite graphs. Birkhäuser. Boston. str. 423. ISBN 0-8176-3389-8 Preveo Richard McCoart ; komentar W.T. Tutte.