Graf (diskret matematik)
I matematikken, og mere specifikt i diskret matematik og grafteori, er en graf en struktur, der består af en mængde objekter og et relationsbegreb mellem par af objekter. Objekterne kaldes knuder (eller hjørner eller punkter), og relationen mellem par af knuder kaldes en kant. [1] Grafen afbildes ofte i diagrammatisk form som en mængde af prikker eller cirkler for knuderne, som er forbundet med linjer eller kurver for kanterne. Grafer kaldes i nogle discipliner for netværk. Denne slags grafer har intet at gøre med grafen for en funktion.
Kanterne kan være rettede eller urettede, svarende til relationens symmetriegenskaber. Når knuderne for eksempel repræsenterer festdeltagere, og en kant forbinder de mennesker, der har givet hånd til hinanden, er grafen ikke rettet, idet A har givet hånd til B, hvis B og kun hvis B har givet hånd til A. Når kantrelationen derimod skal modellere, at A skylder penge til B, så er grafen rettet, idet »at skylde penge« ikke nødvendigvis er gengældt. Den førstnævnte type graf kaldes en urettet graf, mens den sidstnævnte kaldes en rettet graf .
Grafer er det grundlæggende struktur studeret i grafteori. Ordet »graf« blev først brugt i denne forstand af James Joseph Sylvester i 1878. [2] [3]
Grundlæggende begreber
redigérDefinitionerne i grafteori varierer. Følgende er nogle af de mere gængse måder at definere grafer og relaterede matematiske strukturer .
Graf
redigérEn graf (sommetider kaldt urettet graf i modsætning til rettet graf, eller simpel graf i modsætning til multigraf) [4] [5] består af en mængde , hvis elementer kaldes knuder, og en mængde , hvis elementer kaldes kanter. I mange fremstillinger opfattes som det ordnede par . Kanterne i en urettet graf kan betragtes som delmængder af størrelse 2 af knudemængden, så man kan opfatte som en delmængde af . Kanten mellem og kan da skrives .
Knuderne og i kanten kaldes kantens endeknuder eller endepunkter . Kanten siges at forbinde og og være incidente på eller hosliggende til og . En knude behøver ikke at tilhøre nogen kant, og kaldes da isoleret.
Den tomme graf er grafen med en tom knudemængde (og dermed et tom kantmængde). En grafs orden er størrelsen af knudemængden , grafens størrelse er antallet af kanter . I nogle sammenhænge, ikke mindst når man angiver beregningskompleksiteten af algoritmer, er størrelsen dog (ellers ville en ikke-tom graf kunne have en størrelse 0). Graden eller valensen af et knude er antallet incidente kanter; for grafer med sløjfer tælles hver sløjfe to gange.
Grafens kanter definerer en symmetrisk relation på knuderne, kaldt naborelationen. Knuderne og kaldes naboer, når er en kant.
Rettet graf
redigérEn rettet graf eller digraf er en graf, hvor kanterne har retning.
I en begrænset, men meget udbredt forstand defineres en rettet graf ved at definere kantmængden som en mængde af ordnede par af forskellige knuder, . Kanterne kaldes rettede kanter, og sommetider pile eller buer. For at undgå tvetydighed kan denne type objekt kaldes en rettet, simpel graf.
Parret opfattes som gående fra knude x til knude y, som kaldes for henholdsvis startknude og målknude . Kanten kaldes den modsatrettede eller omvendte kant af . Derudover bruges samme terminologi som for urettede grafer, sommetider skelnes mellem indgående og udgående kanter til en knude, og mellem udgrad og indgrad. En knude uden indgående kanter kaldes sommetider kilde, en knude uden udgående kanter dræn.
I nogle fremstillinger, ikke mindst i datalogien, repræsenteres en urettet kant som et par af modsatrettede kanter og . På den måde bliver urettede grafer bare en særlig form for rettede grafer, hvor alle kanter er dobbeltrettede. Her skal man være forsigtig med hvordan antallet af kanter er defineret.
Graftegning
redigérGrafer kan tegnes i planen på mange måder. Typisk er knuderne vist som cirkler eller kasser, opmærket med knudenavne. Kanterne er vist som rette linjer eller kurver, og for rettede kanter er retning typisk indikeret med en pil. I grafer, der repræsenterer et hierarki, er knuderne ofte arrangeret oppefra og ned.
Nogle grafer kan tegnes i planen uden krydsende kanter, sådan en graf kaldes planær. Alle grafer med højst 4 knuder er planære, men der findes ikke-planære grafer; fx den fuldstændige graf på 5 knuder, .
Det er vigtigt at fastholde, at grafen ikke er identisk med sin tegning – meget forskellige visuelle fremstillinger kan repræsentere samme graf. Abstrakt betragtet er grafen entydig bestemt af, hvilke knuder er forbundne med hinanden af hvilke kanter. Konkret kan dog arrangementet knuder og forløbet af linjer i en tegning have stor indflydelse på grafens forståelighed, anvendelighed, produktionsomkostning og æstetik.
Delgraf
redigérGrafen siges at være en delgraf af grafen , hvis dens knuder og kanter også findes , dvs. og . Ofte siges at indeholde , især når er en sti, en kreds, eller en anden specifik graf.
Et mere begrænset begreb er induceret delgraf: En delmængde af knuder siges at inducere grafen , som består af knudemængden og netop de kanter fra , som forbinder knuder i . Formelt er . Grafen er en induceret delgraf af , hvis der findes således at . Alle inducerede delgrafer er delgrafer, men ikke alle delgrafer er inducerede.
Et mere generelt delgrafsbegreb er minor: Sammmentrækningen af en kant sker ved at fjerne kanten fra grafen og forene endeknuderne og . Grafen er en minor af , hvis den fremkommer ved at sammentrække kanter i de delgraf af . Studiet af minorer en en vigtig del af grafteorien, for eksempel siger Wagner sætning at en graf er plan hvis og kun hvis den hverken indeholder den fuldstændige graf eller den fuldstændige todelte graf som minor.
Kantfølge, tur, sti
redigérEn følge , hvor er knuder, er kanter, og der for alle gælder, at kanten forbinder og , kaldes en kantfølge eller en vandring. I en rettet graf skal kanten desuden have den rigtige retning, dvs. Hvis grafen er simpel, er kantfølgen entydig bestemt af følgen af knuder og man kan nøjes med at angive den som
En kantfølge uden gentagne kanter kaldes en tur; en tur bestående af samtlige kanter i grafen kaldes eulertur og er det tidligste studerede fænomen i grafteorien. En kantfølge uden gentagne knuder (og derfor også uden gentagne kanter) kaldes en sti eller vej. Man kan bruge begrebet -sti for at angive stiens startknude og målknude . En kantfølge med kaldes lukket. En kantfølge uden gentagne knuder bortset fra kaldes en kreds eller cykel.
Terminologien for kantfølger varierer kraftigt mellem fremstillinger og sommetider bruges sti eller vej også når knudegentagelse er tilladt. Man kan bruge adjektivet simpel (som i simpel sti) for at gøre det klart, at man udelukker knudegentagelse. Ligeledes er der ingen enighed i litteraturen om længden af en kantfølge, som dog oftest defineres som antallet af kanter (i stedet for antallet af knuder.)
Notation
redigérI nogle fremstillinger bruges notationen for knudemængden og for kantmængden. Kanten mellem og kan også skrives eller .
Graf som relation
redigérMan kan betragte simple grafer som en særlig type af binær relation på en endelig mængde , således at kanten betyder . Simple, urettede grafer uden sløjfer svarer da til relationer, som er symmetriske (dvs. at relationen opfylder at medfører for alle ) og irrefleksive (dvs. at for alle ).
Andre slags simple grafer svarer til andre slags relationer: Simple, rettede grafer uden sløjfer svarer til binære, irrefleksive relationer, som ikke nødvendigvis er symmetriske. Refleksive relationer (dvs. at for alle ) svarer til grafer, som har en sløjfe ved hver knude. Antisymmetriske relationer (dvs. at medfører for alle ) svarer til orienterede grafer.
Anvendelser
redigérGrafer kan bruges til at modellere mange forskellige fænomener, hvor objekter (modelleret af knuderne) står i parvise relationer til hinanden.
For at modellere et socialt netværk i sociologien lader man knuder svare til individer og kanter til individers parvise forhold, for eksempel venskab eller andre interaktioner. I det internetbaserede sociale netværk Facebook er venskabsbegrebet symmetrisk og modelleres derfor med en urettet kant. I netværket Twitter følger brugere andre brugere uden gensidighed, og relationen modelleres derfor af rettede kanter. Lignende modeller bruges i epidemiologien til at spore smittespredning. Her er man ofte interesseret i at undersøge, hvor velforbundne enkelte knuder er, eller hvor mange andre knuder kan nås hurtigt fra specifikke knuder.
For at modellere et transportnetværk bruges knuder til repræsentere vejkryds, lufthavne, holdepladser eller togstationer, og kanterne modellerer veje, flyforbindelser, busruter eller jernbanespor. Ensrettede forbindelser svarer til rettede kanter. Kommunikationsnetværk i informationsteknologi består af enheder som rutere, værter og klienter, modelleret som knuder, og forskellige parvise trådede eller trådløse forbindelser, modelleret som kanter. I disse modeller er man ofte interesseret i stier og afstande i grafen, samt at opdage knuder som bruges af mange veje og derfor er kritiske.
I skemalægning og projektplanlægning kan en rettet kant angive, at en aktion eller værdi afhænger af en anden. For eksempel kan en delopgave i et større projekt kræve, at en anden delopgave er afsluttet, cellen i et regneark kan afhænge af værdierne i andre celler (som derfor skal udregnes først). I disse sammenhæng er man ofte interesseret i at finde fornuftige rækkefølger for delopgaverne og opdage (og helst undgå) cykliske afhængigheder.
Generaliseringer
redigérSløjfer
redigérSommetider tillades grafer at indeholde sløjfer (også kaldt løkker), som er kanter, der forbinder en knude til sig selv. For at tillade sløjfer skal de enkle definitioner forovern ændres til at tillade kanter på henholdsvis . Den slags grafer kaldes grafer med sløjfer eller blot grafer, når det fremgår af sammenhængen, at sløjfer er tilladte.
Multigraf
redigérEn multigraf er en generalisering, der tillader, at flere kanter forbinder det samme par af knuder. Mængden skal da defineres til at være en multimængde af 2-delmængder henholdsvis 2-tupler. I nogle fremstillinger kaldes multigrafer for grafer. [6] [7]
Blandet graf
redigérEn blandet graf er en graf, som kan indeholde både rettete og urettete kanter. Den kan defineres som en tripel , hvor er mængden (eller multimængden) af urettede kanter og er mængden (eller multimængden) af rettede kanter. Rettede og urettede grafer er specialtilfælde af blandede grafer.
Vægtet graf
redigérEn vægtet graf eller et netværk [8] [9] er en graf, hvor hver kant tildeles et tal, kaldt vægten. Vægte kan repræsentere omkostninger, længder eller kapaciteter.
Hypergraf
redigérI en hypergraf består kantmængden af vilkårlige ikke-tomme delmængder af knuder, i stedet for bare delmængder af to elementer. En hypergraf kaldes -uniform, hvis alle dens kanter har kardinalitet . En (urettet) graf er altså en 2-uniform hypergraf. Kanterne i en hypergraf kaldes ofte hyperkanter.
Typer af grafer
redigérOrienteret graf
redigérEn orienteret graf er en rettet graf, som for hver kant ikke indeholder dens modsatrettede kant . Man kan opfatte en on orienteret graf som resultatet af at orientere hver kant i en urettet graf.
En orientering af en urettet fuldstændig graf, dvs. en rettet graf, som for hvert par af knuder og indeholder enten eller (men ikke begge), kaldes en turnering. Man kan opfatte en turnering som resultatet af en alle-mod-alle turnering i en sport eller et spil, hvor kanten er rettet mod vinderen af det enkelte møde.
I nogle fremstillinger bruges »orienteret graf« imidlertid som synonym for »rettet graf«.
Regulær graf
redigérEn regulær graf er en graf, hvor hver knude har det samme antal naboer, dvs. hver knude har samme grad. En regulær graf med knuder af grad k kaldes k-regulær.
Fuldstændig graf
redigérEn fuldstændig graf (også kaldt komplet graf) er en graf, i hvilken hvert par knuder er forbundet med en kant.
Endelig graf
redigérEn endelig graf er en graf, hvor knude- og kantmængderne er endelige mængder . Ellers kaldes den en uendelig graf .
I grafteorien er det ofte underforstået, at de diskuterede grafer er endelige, medmindre andet er sagt.
Todelt graf
redigérEn todelt graf er en simpel graf, hvis knudemængde kan opdeles i to mængder W og X, så ingen to knuder i W deler en fælles kant og ingen knuder i X deler en fælles kant. Alternativt er det en graf med kromatisk tal 2.
I en fuldstændig, todelt graf er knudemængden foreningen af to disjunkte mængder, W og X, så hvert knude i W er nabo til hver knude i X, og der ikke er kanter inden for hverken W eller X.
Sti
redigérEn sti eller en lineær graf af orden er en graf hvis knudemængde kan skrives som således at alle kanter er på formen for . Stier kan også karakteriseres som sammenhængende grafer, hvis knuder alle har grad 2, på nær to knuder med grad 1. Når en sti-graf forekommer som en delgraf i en anden graf, kaldes den en sti i grafen. I en rettet sti skal alle kanter pege i samme retning, dvs. være på formen .
Kreds
redigérEn kreds eller kredsgraf eller cykel af orden er en graf hvis knudemængde kan skrives som således at alle kanter er på formen for , samt kanten . Kredse kan også karakteriseres som sammenhængende 2-regulære grafer. Når en kreds forekommer som en delgraf i en anden graf, kaldes den en kreds (eller cykel) i grafen. En graf uden kredse kaldes kredsfri eller acyklisk. I en rettet kreds skal alle kanter pege i samme retning, dvs. være på formen samt .
Træ og skov
redigérEt træ is en urettet graf i hvilken hvert par af knuder er forbundet af netop én sti. En ækvivalent definition er en sammenhængende, kredsfri urettet graf.
En skov er en urettet graf i hvilken hvert par af knuder er forbundet af højst én sti. En ækvivalent definition er en disjunkt forening af træer.
Knuder af grad 1 kaldes sommetider for blade. Et rodfæstet træ er et træ med en bestemt knude, kaldt roden.
Knuder, som hverken er blade eller roden kaldes sommetider for interne knuder.
Et udtræ (henholdsvis indtræ) fremkommer ved at orientere kanterne i et rodfæstet træ bort fra roden (henholdsvis hen imod roden). Denne slags rettede graf modellerer mange hierarkiske strukturer og kaldes ofte blot »træ«. Udtræer tillader også en rekursiv definition, ifølge hvilken et træ enten er tomt eller består af en knude , samt træerne med rødder og kanterne .
Rodfæstede træer giver anledning til et hierarkisk struktur, ofte afbildet med roden foroven, således at træet ser ud til at »vokse nedad«. Knudernes indbydres forhold beskrives ofte i termer af familjerelationer. Hver kant i et udtræ peger fra en forælder til et barn, knuder med samme forælder kaldes søskende. En knudes efterfølgerne er de knuder, der kan nås på en rettet sti i udtræet, tilsvarende bruges forgænger.
Acyklisk rettet graf
redigérEn endelig, rettet graf uden (rettede) kredse kaldes acyklisk rettet graf (eller kredsfri rettet graf). Acykliske rettede grafer er præcis de grafer, der tillader en såkaldt topologisk orden af knuderne, dvs. at knuderne kan ordnes som , således at alle kanter er rettet fra en tidligere til en senere knude i ordenen, dvs. at der for hver kant gælder . Acykliske rettede grafer spiller en central rolle i datalogi, softwareudvikling og planlægning, blandt andet fordi de modeller afhængighedsforhold mellem processer i veldefinerede opgaver.
Noter
redigér- ^ Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. udgave). New York: Dover Pub. s. 19. ISBN 978-0-486-67870-2. Hentet 8. august 2012.
A graph is an object consisting of two sets called its vertex set and its edge set.
- ^ See:
- ^ Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. s. 35. ISBN 978-1-58488-090-5.
- ^ Bender & Williamson 2010, s. 148.
- ^ Se fx Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.
- ^ Bender & Williamson 2010, s. 149.
- ^ Graham et al., p. 5.
- ^ Strang, Gilbert (2005), Linear Algebra and Its Applications (4th udgave), Brooks Cole, ISBN 978-0-03-010567-8 (Webside ikke længere tilgængelig)
- ^ Lewis, John (2013), Java Software Structures (4th udgave), Pearson, ISBN 978-0133250121