More actions
Bot: Automatski unos stranica |
m Bot: Automatska zamjena teksta (-{{cite book +{{Citiranje knjige) |
||
| Redak 7: | Redak 7: | ||
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]] [[matematika u 1736.|1736.]] godine postavio i riješio taj problem. Objavio je [[matematika u 1741.|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. <ref name="E-math"/> | 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]] [[matematika u 1736.|1736.]] godine postavio i riješio taj problem. Objavio je [[matematika u 1741.|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. <ref name="E-math"/> | ||
Riječ ''graf'' ušla je u široku uporabu tek [[matematika u 1936.|1936.]] kad je [[Dénes Kőnig]] objavio monografiju<ref name=Gregurić/> ''Theorie der endlichen und unendlichen Graphen''.<ref name="Richard McCoart">{{ | Riječ ''graf'' ušla je u široku uporabu tek [[matematika u 1936.|1936.]] kad je [[Dénes Kőnig]] objavio monografiju<ref name=Gregurić/> ''Theorie der endlichen und unendlichen Graphen''.<ref name="Richard McCoart">{{Citiranje knjige|first=Dénes|last=Kőnig|title=Theory of finite and infinite graphs|year=1990|publisher=Birkhäuser|location=Boston|isbn=0-8176-3389-8|page=[https://archive.org/details/theoryoffinitein0000koni/page/423 423]|url=https://archive.org/details/theoryoffinitein0000koni/page/423}} Preveo Richard McCoart ; komentar W.T. Tutte.</ref> 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 [[komunikacijska znanost|komunikacijske]], [[Biheviorizam|biheviorističke]] [[biheviorističke znanosti|znanosti]] i tehnologija.<ref name=Gregurić>[http://www.mathos.unios.hr/~mdjumic/uploads/diplomski/GRE10.pdf Sveučilište J. J. Strossmayera u Osijeku - Odjel za matematiku] Iva Gregurić: Bojenje grafova, Osijek, 2011., str. 3, pristupljeno 28. veljače 2020.</ref> | ||
== Primjena == | == Primjena == | ||
Posljednja izmjena od 2. siječanj 2022. u 22:00
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
Predmet proučavanja
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]
Povijest
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]
Primjena
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
Izvori
- ↑ 1,0 1,1 1,2 1,3 FER Mladen Marinović: Teorija grafova (pristupljeno 23. prosinca 2019.)
- ↑ 2,0 2,1 2,2 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.)
- ↑ 3,0 3,1 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. Boston: Birkhäuser. str. 423. ISBN 0-8176-3389-8. https://archive.org/details/theoryoffinitein0000koni/page/423 Preveo Richard McCoart ; komentar W.T. Tutte.