Grafteori

Den komplette grafen K5 er ein graf med fem nodar som alle er knytte opp til kvarandre med kantar.

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.

Other Languages
norsk: Grafteori
svenska: Grafteori
dansk: Grafteori
አማርኛ: ሥነ ግራፍ
беларуская: Тэорыя графаў
čeština: Teorie grafů
Ελληνικά: Θεωρία γράφων
English: Graph theory
Esperanto: Grafeteorio
euskara: Grafo teoria
한국어: 그래프 이론
Bahasa Indonesia: Teori graf
íslenska: Netafræði
latviešu: Grafu teorija
lietuvių: Grafų teorija
Bahasa Melayu: Teori graf
монгол: Графын онол
Nederlands: Grafentheorie
日本語: グラフ理論
português: Teoria dos grafos
sicilianu: Tiuria dî grafi
Simple English: Graph theory
slovenčina: Teória grafov
slovenščina: Teorija grafov
српски / srpski: Теорија графова
srpskohrvatski / српскохрватски: Teorija grafova
Türkçe: Çizge teorisi
українська: Теорія графів
Tiếng Việt: Lý thuyết đồ thị
粵語: 圖論
中文: 图论