Težinski graf

Izvor: Hrvatska internetska enciklopedija
Skoči na:orijentacija, traži

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

  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.)
  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.)

weighted graph