Težinski graf

Težinski graf, pojam iz teorije grafova. To je onaj graf u kojem je realan broj pridružen svakoj grani. Ako grane označimo s ${\displaystyle e_{1},e_{2},\dots }$, onda je težina grane w(e), npr. za granu ${\displaystyle e_{1}}$ to je ${\displaystyle w(e_{1})}$.^[1]

Realan broj može se pridružiti svakom bridu čime je graf proširen težinskom funkcijom. Kod težinskog grafa, ako je graf mreža cesta, težinska funkcija je npr. duljina svakog puta.^[2]

U težinskom grafu minimalno razapinjuće stablo je stablo težine (tj. zbroja težina njegovih bridova) manje ili jednake težini svakog drugog razapinjućeg stabla u težinskom grafu.^[2]

Izvori

1. Sveučilište u Zagrebu, Geodetski fakultet, Zavod za kartografiju i fotogrametriju  Arhivirana inačica izvorne stranice od 19. kolovoza 2019. (Wayback Machine) Nada Vučetić: OSNOVE GEOINFORMATIKE: Neki pojmovi i definicije iz teorije grafova, Osnove teorije skupova (pristupljeno 8. siječnja 2020.)
2. math.e, hrvatski matematički elektronički časopis Maja Fošner i Tomaž Kramberger: Teorija grafova i logistika br. 14, ISSN ISSN 1334-6083 (pristupljeno 8. siječnja 2020.)