Grafteori

Grafteori er den greina av matematikk der ein studerer eigenskapane til grafar.
Ein graf består av ei mengd hjørne eller nodar, og ei mengd kantar, der kvar kant bind saman to hjørne. På figuren er eit døme på ein graf med fem nodar og ti kantar.

Formelt er det vanleg å definera ein graf  som eit par , der  er ei ikkje-tom mengd med nodar, og  er ei mengd med undermengder av  der kvar undermengd har to element.
Strengt tatt er grafen desse mengdene av hjørne og kantar – ikkje teikninga av dei.

Grafteori vart grunnlagd av Leonhard Euler då han publiserte ein artikkel om problemet «Bruene i Königsberg» i 1736.

 Grafteoretiske omgrep 

To hjørne er naboar viss dei er forbunde med ein kant. Ein kant er insident til hjørna som han bind saman. 

Ein graf er enkel viss det aldri er meir enn éin kant mellom to naboar, og ingen hjørne er nabo med seg sjølv. Ein slik kant blir kalla ei løkke. Ein graf som inneheld løkker, eller som inneheld naboar som er forbunde med meir enn éin kant, blir kalla ein multigraf.

En veg i ein graf er ei mengd kantar i rekkefølgje, slik at to kantar etter kvarandre alltid har eit hjørne felles. Ein sti er ein veg der kvart hjørne opptrer høgst éin gong. Ein sykel er ein veg der det første og det siste hjørnet er det same, mens alle andre hjørne opptrer høgst éin gong.

Ein planar graf er ein graf som kan teiknast i eit plan eller på ei kuleflate slik at ingen kantar kryssar kvarandre. 
Ein graf er samanhengande viss kvart par av ulike hjørne er knytte saman med ein sti.

To grafar er isomorfe viss det finst ei avbilding frå hjørna i den eine grafen til hjørna i den andre grafen, slik at to hjørne er naboar i den første grafen viss og berre viss dei korresponderande hjørna er naboar i den andre grafen.

Bakgrunnsstoff


Kategori:Diskret matematikk