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 , onda je težina grane w(e), npr. za granu to je .[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]

IzvoriUredi

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