Versionen fra 5. feb. 2009, 19:52 redigér Loveless (diskussion \| bidrag) 23.792 edits m robot Tilføjer: ms:Teori graf ← Gå til forrige forskel		Versionen fra 6. mar. 2009, 17:45 redigér fjern redigering MGA73bot (diskussion \| bidrag) Botter 274.384 edits m Bot: Adding {{Commonscat\|Graph theory}}; kosmetiske ændringer Gå til næste forskel →
Linje 5: En ''graf'' kan i denne sammenhæng illustreres ved et diagram bestående af et antal punkter (''knuder'') forbundet med et antal ''kanter''. Hver kant illustreres som et linjestykke (eller kurvestykke) med knuder som sine to endepunkter. == Definitioner == En '''graf''' eller '''uorienteret graf''' ''G'' er et par (''V'', ''E'') bestående af * en [[mængde]] ''V'' af ''knuder'', * en mængde ''E'' ~~&sube;~~⊆ ''V''<sup>(2)</sup> af uordnede par af knuder i ''V'' kaldet ''kanter''. Læg mærke til, at denne definition ikke tillader ''loops'' (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 for en '''simpel graf''', og en graf, hvor man man tillader loop og dobbeltkanter, kaldes under tiden en '''pseudograf'''. Linje 17: En '''sti''' 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''. En graf ''G'' = (''V'', ''E'') kaldes * [[komplet graf\|komplet]], hvis ''E'' = ''V''<sup>(2)</sup>, dvs. der er kanter mellem alle knuder, * [[sammenhængende graf\|sammenhængende]], hvis der findes en sti mellem alle knuder, eller med andre ord: for alle ''v'', ''w'' ~~∈~~∈ ''V'' skal der findes en sti (''v''<sub>1</sub>, ''v''<sub>2</sub>, ..., ''v''<sub>''n''</sub>), så ''v'' = ''v''<sub>1</sub> og ''w'' = ''v''<sub>''n''</sub>, * [[todelt graf\|todelt]], hvis mængden af knuder ''V'' kan deles op i to [[disjunkt]]e mængder X og Y, (dvs. ''V'' = ''X'' ~~∪~~∪ ''Y'', ''X'' ~~∩~~∩ ''Y'' = Ø), så alle kanter går mellem de to dele af grafen, ''e'' ~~&nsub;~~⊄ ''X'' og ''e'' ~~&nsub;~~⊄ ''Y'' for alle ''e'' ~~∈~~∈ ''E''. * en [[plangraf]], hvis den kan indlejres i planen (tegnes på et stykke papir), så ingen kanter krydser hinanden, * en [[skov (matematik)\|skov]], hvis der ikke findes cykler i grafen, der går igennem flere end 2 knuder, Linje 32: En '''orienteret 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'' ~~&sube;~~⊆ ''V'' ² af ordnede par af knuder også kaldet kanter. I en orienteret graf tegnes kanterne med pile, så man kan se, hvor kanterne begynder og ender. Linje 46: [[Kant (grafteori)\|Kant]], [[vej (grafteori)\|vej]], [[punkt (grafteori)\|punkt]], [[todelt graf]], [[Hamiltonkreds]] {{Commonscat\|Graph theory}} [[Kategori:Grafteori\|]]▼ {{Link FA\|nl}} ▲[[Kategori:Grafteori\|]] [[an:Tioría de grafos]]

Grafteori: Forskelle mellem versioner