grafteori

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

Grafteori av /Store norske leksikon ※. Gjengitt med tillatelse

Grafteori, gren av topologien, 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 visse 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 G. Kirchhoff, W. R. Hamilton og Kasimir Kuratowski (1896–1980). I de senere år har det også vært stor aktivitet på området, og mange interessante resultater er fremkommet ved hjelp av datamaskiner.

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