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 [math]\displaystyle{ e_1, e_2, \dots }[/math], onda je težina grane w(e), npr. za granu [math]\displaystyle{ e_1 }[/math] to je [math]\displaystyle{ w(e_1) }[/math].^[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

↑ Sveučilište u Zagrebu, Geodetski fakultet, Zavod za kartografiju i fotogrametriju Nada Vučetić: OSNOVE GEOINFORMATIKE: Neki pojmovi i definicije iz teorije grafova, Osnove teorije skupova (pristupljeno 8. siječnja 2020.)
↑ ^2,0 ^2,1 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.)

weighted graph

[1] Sveučilište u Zagrebu, Geodetski fakultet, Zavod za kartografiju i fotogrametriju Nada Vučetić: OSNOVE GEOINFORMATIKE: Neki pojmovi i definicije iz teorije grafova, Osnove teorije skupova (pristupljeno 8. siječnja 2020.)

[E-math-2] 2,0 ^2,1 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.)

[1]

[2]