Versionen fra 6. okt. 2019, 10:17 redigér Glenn (diskussion \| bidrag) Administratorer 128.682 edits m +Kategori:Matematiske discipliner ← Gå til forrige forskel		Versionen fra 26. jun. 2020, 16:32 redigér fjern redigering Thore Husfeldt (diskussion \| bidrag) 71 edits →‎Definitioner: orienteret -> rettet. (Ikke alle rettede grafer er orienterede.) Gå til næste forskel →
Linje 9: == Definitioner == En '''graf''' eller '''~~uorienteret~~urettet graf''' ''G'' er et par (''V'', ''E'') bestående af * en [[mængde]] ''V'' af ''knuder'', * en mængde ''E'' ⊆ ''V''<sup>(2)</sup> af uordnede par af knuder i ''V'' kaldet ''kanter''. Læg mærke til, at denne definition ikke tillader ''~~loops~~løkker'' (kanter fra en knude til sig selv) eller ''dobbeltkanter'' (2 eller flere kanter mellem de samme to knuder). En sådan graf kaldes ~~under tiden~~sommetider for en '''simpel graf''',. ~~og en~~En graf, ~~hvor~~med ~~man man tillader loop~~løkker og dobbeltkanter, kaldes ~~under tiden~~sommetider en '''pseudograf'''. Grafen på billedet består af Linje 19: En '''sti''' (eller '''vej''') i en graf er en følge (''v''<sub>1</sub>, ''v''<sub>2</sub>, ..., ''v''<sub>''n''</sub>) af knuder i ''V'', så {''v''<sub>''i''</sub>, ''v''<sub>''i''+1</sub>} ∈ ''E'' for alle 1 ≤ ''i'' < n. En '''cykel''' eller '''kreds''' er en sti (''v''<sub>1</sub>, ''v''<sub>2</sub>, ..., ''v''<sub>''n''</sub>), så ''v''<sub>''i''</sub> ≠ ''v''<sub>''j''</sub> for ''i'' ≠ ''j'' og {''v''<sub>''n''</sub>, ''v''<sub>1</sub>} ∈ ''E''. Antallet af kanter fra en knude, kaldes dens '''valens''' eller '''grad'''. En graf ''G'' = (''V'', ''E'') kaldes * [[komplet graf\|komplet]], hvis ''E'' = ''V''<sup>(2)</sup>, dvs. der er kanter mellem alle knuder, Line 36 ⟶ 34: En '''~~orienteret~~rettet graf''' (evt. '''digraf''' efter det engelske ''digraph'' – ''directed graph'') ''G'' er at par (''V'', ''E'') bestående af * en mængde ''V'' af knuder, * en mængde ''E'' ⊆ ''V'' ² af ordnede par af knuder også kaldet kanter. I en ~~orienteret~~rettet graf tegnes kanterne ofte med pile, så man kan se, hvor kanterne begynder og ender. En rettet graf kaldes '''orienteret''', hvis der mellem hvert knudepar højst findes én kant; med andre ord fremkommer en orienteret graf fra en simpel, urettet graf ved at vælge en retning for hver kant. En orienteret graf er en '''turnering''', hvis den indeholder en (rettet) kant mellem hvert par af knuder. == Historie ==

Grafteori: Forskelle mellem versioner