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.  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.

Grundlæggende begreber 

Definitionerne i grafteori varierer. Følgende er nogle af de mere gængse måder at definere grafer og relaterede matematiske strukturer .

Graf 

En graf  (sommetider kaldt urettet graf i modsætning til rettet graf, eller simpel graf i modsætning til multigraf)   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 

En 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 

Grafer 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 

Grafen  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 

En 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 

I nogle fremstillinger bruges notationen  for knudemængden og  for kantmængden.
Kanten mellem  og  kan også skrives  eller .

Graf som relation 

Man 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 

Grafer 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

Sløjfer 

Sommetider 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 

En 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.

Blandet graf 

En 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 

En vægtet graf eller et netværk   er en graf, hvor hver kant tildeles et tal, kaldt vægten. Vægte kan repræsentere omkostninger, længder eller kapaciteter.

Hypergraf 

I 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

Orienteret graf 
En 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 

En 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 

En fuldstændig graf (også kaldt komplet graf) er en graf, i hvilken hvert par knuder er forbundet med en kant.

Endelig graf 
En 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 

En 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 

En 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 

En 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 

Et 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 

En 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 

Grafteori