grafteori

Grafteori. En graf med noder (svarte) og kanter (røde).

Av /Store norske leksikon ※.

Grafteori er en gren av topologien som ble grunnlagt av Leonhard Euler i 1736 med en avhandling som tok utgangspunkt i det königsbergske broproblem. Både dette og firfargeproblemet har blitt løst ved hjelp av grafteori, og teorien har også gitt mange verdifulle og interessante resultater når det gjelder spørsmål i forbindelse med elektriske nettverk, optimeringsproblemer og forskjellige datastrukturer.

En graf er i denne sammenhengen en samling noder (punkter) og kanter (linjer) som forbinder noen, eller alle, av nodene. En graf er regulær av graden n hvis det finnes n kanter ved hver node.

Noen sentrale personer innen utviklingen av grafteorien (i tillegg til Euler) er Gustav Kirchhoff, William R. Hamilton og Kasimir Kuratowski (1896–1980). I nyere tid har man kommet frem til mange interessante resultater innen grafteor ved hjelp av datamaskiner.

Les mer i Store norske leksikon

Kommentarer

Kommentaren din publiseres her. Fagansvarlig eller redaktør svarer når de kan.

Du må være logget inn for å kommentere.

eller registrer deg