Graf (diskret matematik)

object der består af knuder og links

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.

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. [2] [3]

Grundlæggende begreber

redigér

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

 
En graf med tre knuder og tre kanter.

En 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ér
 
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,  . 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ér
 
Tre forskellige tegninger af samme urettede graf på 5 knuder. Grafens knuder er  , dens kanter er  ,  ,  ,   og  .

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

redigér
 
  er en delgraf af  , som fremkommer ved at fjerne knuderne   og   og kanten  .   er den inducerede delgraf  .   er en minor af  , som fremkommer ved at trække   og   sammen til den nye knude   og fjerne kanten  .

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

redigér

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

redigér

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

Graf som relation

redigér

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

redigér

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

redigér

Sløjfer

redigér

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

redigér

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. [6] [7]

Blandet graf

redigér
 
En blandet multigraf med 6 knuder og de rettede kanter   og de urettede kanter  . Kanten   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  , 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ér
 
En vægtet graf med ti knuder og tolv kanter.

En 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ér

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

redigér

Orienteret graf

redigér

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

redigér
 
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

redigér
 
Den fuldstændige graf på 5 knuder,  .

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

Endelig graf

redigér

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

redigér
 
Den fuldstændige todelte 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.

 
Stigrafen på 6 knuder, 6-stien  .

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  .

 
Kredsgrafen på 6 knuder, 6-kredsen  .

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

redigér
 
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  , 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ér
  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  , 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.

  1. ^ 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.
  2. ^ See:
  3. ^ Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. s. 35. ISBN 978-1-58488-090-5.
  4. ^ Bender & Williamson 2010, s. 148.
  5. ^ Se fx Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.
  6. ^ Bender & Williamson 2010, s. 149.
  7. ^ Graham et al., p. 5.
  8. ^ Strang, Gilbert (2005), Linear Algebra and Its Applications (4th udgave), Brooks Cole, ISBN 978-0-03-010567-8 (Webside ikke længere tilgængelig)
  9. ^ Lewis, John (2013), Java Software Structures (4th udgave), Pearson, ISBN 978-0133250121