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.

En graf med seks knuder og syv kanter.

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 med tre knuder og tre kanter.

En graf $G$ (sommetider kaldt urettet graf i modsætning til rettet graf, eller simpel graf i modsætning til multigraf) består af en mængde $V$, hvis elementer kaldes knuder, og en mængde $E$, hvis elementer kaldes kanter. I mange fremstillinger opfattes $G$ som det ordnede par $G=(V,E)$. Kanterne i en urettet graf kan betragtes som delmængder af størrelse 2 af knudemængden, så man kan opfatte $E$ som en delmængde af $\{\,\{x,y\}\colon x,y\in V\}$. Kanten mellem $x$ og $y$ kan da skrives $\{x,y\}$.

Knuderne $x$ og $y$ i kanten $\{x,y\}$ kaldes kantens endeknuder eller endepunkter . Kanten siges at forbinde $x$ og $y$ og være incidente på eller hosliggende til $x$ og $y$. 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 $|V|$, grafens størrelse er antallet af kanter $|E|$. I nogle sammenhænge, ikke mindst når man angiver beregningskompleksiteten af algoritmer, er størrelsen dog $|V|+|E|$ (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 $x$ og $y$ kaldes naboer, når $\{x,y\}$ er en kant.

Rettet graf

En rettet graf med tre knuder og fire rettede kanter (dobbeltpilen repræsenterer en kant i hver retning).

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, $E\subseteq \{(x,y)\colon x,y\in V,x\neq y\}$. Kanterne kaldes rettede kanter, og sommetider pile eller buer. For at undgå tvetydighed kan denne type objekt kaldes en rettet, simpel graf.

Parret $(x,y)$ opfattes som gående fra knude x til knude y, som kaldes for henholdsvis startknude og målknude . Kanten $(y,x)$ kaldes den modsatrettede eller omvendte kant af $(x,y)$. 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 $\{x,y\}$ som et par af modsatrettede kanter $(x,y)$ og $(y,x)$. 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

Tre forskellige tegninger af samme urettede graf på 5 knuder. Grafens knuder er $\{1,2,3,4,5\}$, dens kanter er $\{1,2\}$, $\{2,3\}$, $\{1,3\}$, $\{2,4\}$ og $\{4,5\}$.

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, $K_{5}$.

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

$H_{1}$ er en delgraf af $G$, som fremkommer ved at fjerne knuderne $u$ og $v$ og kanten $wx$. $H_{2}$ er den inducerede delgraf $G[\{v,w,x\}]$. $H_{3}$ er en minor af $G$, som fremkommer ved at trække $u$ og $v$ sammen til den nye knude $y$ og fjerne kanten $wx$.

Grafen $G'=(V',E')$ siges at være en delgraf af grafen $G=(V,E)$, hvis dens knuder og kanter også findes $G$, dvs. $V'\subseteq V$ og $E'\subseteq E$. Ofte siges $G$ at indeholde $G'$, især når $G'$ er en sti, en kreds, eller en anden specifik graf.

Et mere begrænset begreb er induceret delgraf: En delmængde $U\subseteq V$ af knuder siges at inducere grafen $G[U]$, som består af knudemængden $U$ og netop de kanter fra $E$, som forbinder knuder i $U$. Formelt er $G[U]=(U,\{\,uv\in E\mid u,v\in U\})$. Grafen $G'$ er en induceret delgraf af $G$, hvis der findes $U\subseteq V$ således at $G'=G[U]$. Alle inducerede delgrafer er delgrafer, men ikke alle delgrafer er inducerede.

Et mere generelt delgrafsbegreb er minor: Sammmentrækningen af en kant $\{x,y\}$ sker ved at fjerne kanten fra grafen og forene endeknuderne $x$ og $y$. Grafen $H$ er en minor af $G$, hvis den fremkommer ved at sammentrække kanter i de delgraf af $G$. 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 $K_{5}$ eller den fuldstændige todelte graf $K_{3,3}$ som minor.

Kantfølge, tur, sti

En følge $v_{0},e_{1},v_{1},e_{2},\dots ,v_{k-1},e_{k},v_{k}$, hvor $v_{i}$ er knuder, $e_{i}$ er kanter, og der for alle $i$ gælder, at kanten $e_{i}$ forbinder $v_{i-1}$ og $v_{i}$, kaldes en kantfølge eller en vandring. I en rettet graf skal kanten desuden have den rigtige retning, dvs. $e_{i}=(v_{i-1},v_{i})$ Hvis grafen er simpel, er kantfølgen entydig bestemt af følgen af knuder og man kan nøjes med at angive den som $v_{0},v_{1},\dots ,v_{k}$

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 $s,t$-sti for at angive stiens startknude $s=v_{0}$ og målknude $t=v_{k}$. En kantfølge med $v_{0}=v_{n}$ kaldes lukket. En kantfølge uden gentagne knuder bortset fra $v_{0}=v_{n}$ 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 $V(G)$ for knudemængden og $E(G)$ for kantmængden. Kanten mellem $x$ og $y$ kan også skrives $xy$ eller $x{}-{}y$.

Graf som relation

Man kan betragte simple grafer som en særlig type af binær relation $\sim$ på en endelig mængde $V$, således at kanten $xy$ betyder $x\sim y$. Simple, urettede grafer uden sløjfer svarer da til relationer, som er symmetriske (dvs. at relationen $\sim$ opfylder at $x\sim y$ medfører $y\sim x$ for alle $x,y\in V$) og irrefleksive (dvs. at $x\not \sim x$ for alle $x\in V$).

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 $x\sim x$ for alle $x\in V$) svarer til grafer, som har en sløjfe ved hver knude. Antisymmetriske relationer (dvs. at $x\sim y$ medfører $y\not \sim x$ for alle $x,y\in V$) 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å $\{x,x\}$ henholdsvis $(x,y)$. 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 $E$ 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 multigraf med 6 knuder og de rettede kanter $b,f,g,h,i$ og de urettede kanter $a,c,d,e,j,k$. Kanten $e$ er en sløjfe, og der er to (urettede) kanter mellem 2 og 3.

En blandet graf er en graf, som kan indeholde både rettete og urettete kanter. Den kan defineres som en tripel $G(V,E,A)$, hvor $E$ er mængden (eller multimængden) af urettede kanter og $A$ 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 med ti knuder og tolv kanter.

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 $E$ af vilkårlige ikke-tomme delmængder af knuder, i stedet for bare delmængder af to elementer. En hypergraf kaldes $k$-uniform, hvis alle dens kanter har kardinalitet $k$. 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 $(x,y)$ ikke indeholder dens modsatrettede kant $(y,x)$. 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 $x$ og $y$ indeholder enten $(x,y)$ eller $(y,x)$ (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

Petersengrafen, en 3-regulær graf på 10 knuder.

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

Den fuldstændige graf på 5 knuder, $K_{5}$.

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

Den fuldstændige todelte graf $K_{5,3}$.

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

Stigrafen på 6 knuder, 6-stien $P_{6}$.

En sti eller en lineær graf af orden $n\geq 2$ er en graf hvis knudemængde kan skrives som $\{v_{1},\ldots ,v_{n}\}$ således at alle kanter er på formen $\{v_{i},v_{i+1}\}$ for $i\in \{1,\ldots ,n-1\}$. 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 $(v_{i},v_{i+1})$.

Kreds

Kredsgrafen på 6 knuder, 6-kredsen $C_{6}$.

En kreds eller kredsgraf eller cykel af orden $n\geq 3$ er en graf hvis knudemængde kan skrives som $\{v_{1},\ldots ,v_{n}\}$ således at alle kanter er på formen $\{v_{i},v_{i+1}\}$ for $i\in \{1,\ldots ,n-1\}$, samt kanten $\{v_{n},v_{1}\}$. 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 $(v_{i},v_{i+1})$ samt $(v_{n},v_{1})$.

Træ og skov

Et træ med 5 blade (hvide) og 4 interne knuder (sorte).

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 rodfæstet træ med roden i toppen, orienteret som udtræ.

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 $u$, samt træerne $T_{1},\ldots ,T_{r}$ med rødder $v_{1},\ldots ,v_{r}$ og kanterne $(u,v_{1}),\ldots ,(u,v_{r})$.

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

Hovedartikel: Acyklisk rettet graf.

En acyklisk rettet graf. En mulig topologisk orden er A, B, G, C, D, E, F.

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 $\{v_{1},\ldots ,v_{n}\}$, således at alle kanter er rettet fra en tidligere til en senere knude i ordenen, dvs. at der for hver kant $(v_{i},v_{j})$ gælder $i<j$. 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.