STRUKE:

teorija grafova

teorija grafova, grana matematike koja se bavi istraživanjem problema opisanih s pomoću mrežnih grafova. Nazivlje u teoriji grafova razlikuje se od uobičajenoga matematičkog nazivlja: graf je matematički objekt koji se sastoji od skupa vrhova (točaka) i skupa bridova (dužina koje povezuju vrhove); petlja je brid koji završava u istom vrhu; šetnja je niz povezanih vrhova i bridova; put je šetnja u kojoj se bridovi i vrhovi ne ponavljaju; Eulerov put je put koji obuhvaća sve bridove; udaljenost vrhova najkraći je put (najmanji broj bridova) između vrhova; težina brida je broj pridružen svakomu bridu; tablica incidencije je tablica u kojoj redovi i stupci predstavljaju vrhove grafa, a polja u tablici na križanju pojedinih redaka i stupaca predstavljaju težinu brida koji spaja te vrhove, itd.

Smatra se da je prvi problem teorije grafova, sedam mostova Königsberga, postavio i riješio Leonhard Euler (1736). Prvi udžbenik iz teorije grafova, Teorija konačnih i beskonačnih grafova (Theorie der endlichen und unendlichen Graphen, 1936), napisao je madžarski matematičar Dénes König. Neki problemi teorije grafova, kao što je npr. traženje najkraćeg puta između zadanih točaka, poznati su pod nazivima problem kineskog poštara, problem trgovačkog putnika, problem muzejskog vodiča, a njihova se rješenja primjenjuju u stvarnom svijetu za organiziranje prijevoza robe od skladišta do trgovina, raspored linija javnog prijevoza, planiranje i vođenje projekata i dr. Metode teorije grafova, npr. nalaženja najmanje razapinjućeg stabla ili pretraživanja stabla, primjenjuju se za strukturiranje baza podataka i za rješavanje mnoštva problema u računalstvu.

teorija grafova. Hrvatska enciklopedija, mrežno izdanje. Leksikografski zavod Miroslav Krleža, 2018. Pristupljeno 28.2.2020. <http://www.enciklopedija.hr/Natuknica.aspx?ID=70127>.