Grafteori
From Wikipedia, the free encyclopedia
Grafteori er en gren i matematikk og informatikk der man studerer egenskapene til grafer. Grafer er matematiske strukturer som brukes til å lage modeller for parvise relasjoner mellom objekter. I informatikken regnes graf som en abstrakt datastruktur, en teoretisk struktur som kan implementeres på ulike måter. Studier av algoritmer som behandler grafer er en viktig disiplin med mange praktiske anvendelser, i dag er dette i stor grad knyttet mot moderne datateknikk, men slike algoritmer var også utviklet før den digitale tidsalderen.[1] Grafer og behandling av grafer er viktige verktøy i mange hverdagslige problemstillinger som f.eks. ruteplanlegging, datanettverk og design av mikrobrikker.
Eksempelgrafer | ||
---|---|---|
Planar | Ikke planar | |
Opprinnelsen til grafteori anses for å være en artikkel publisert av Leonhard Euler i 1736, som tok for seg problemet Broene i Königsberg.