Den grafteori er den disciplin matematik og computer , at undersøgelser af de grafer , som er abstrakte modeller af tegninger af net, der forbinder objekter. Disse modeller består af dataene om hjørner (også kaldet knudepunkter eller punkter med henvisning til polyhedra ) og kanter (også kaldet links eller linjer ) mellem disse hjørner; disse kanter er undertiden ikke-symmetriske (graferne siges derefter at være orienterede ) og kaldes pile eller buer .
De algoritmer, der er udviklet til at løse problemer vedrørende objekterne i denne teori, har adskillige anvendelser inden for alle områder relateret til begrebet netværk ( socialt netværk , computernetværk , telekommunikation osv.) Og i mange andre områder (f.eks. Genetisk ) som begrebet graf , omtrent svarende til den af binære relation (ikke at forveksle med graf for en funktion ), er generel. Store og vanskelige sætninger, såsom firefarvet sætning , den perfekte grafsætning eller Robertson-Seymour sætningen , har hjulpet med at etablere dette emne med matematikere, og de spørgsmål, det lader åbne, såsom formodningen om Hadwiger , gør det en levende gren af diskret matematik .
Der er flere variationer i definitionen af grafer i grafteorien. De mest almindelige definitioner er som følger.
I en begrænset, men meget udbredt betydning af udtrykket, er en graf et par G = ( V , E ) omfattende
For at undgå tvivl kan denne type objekt kaldes nøjagtigt en simpel ikke-rettet graf .
I kanten { x , y } kaldes hjørnerne x og y enderne eller ekstreme hjørner af kanten. Vi siger, at kanten forbinder x og y og er hændende på x og på y . Et toppunkt kan eksistere i en graf uden en hændende kant. De flere kanter er to eller flere kanter, der forbinder de samme to hjørner; de kan ikke eksistere i en simpel ikke-rettet graf.
I en mere generel betydning af udtrykket, der tillader flere kanter, er en graf en triplet G = ( V , E , ϕ ) omfattende
For at undgå tvivl kan denne type genstand kaldes nøjagtigt en ikke-rettet multigraf .
En sløjfe er en kant, der forbinder et toppunkt med sig selv. Grafer som defineret i de to foregående definitioner kan ikke have sløjfer, fordi en sløjfe, der forbinder et toppunkt x, er kanten (for en simpel ikke-orienteret graf) eller er hændende på (for en ikke-orienteret multigraf) { x , x } = { x } hvilket er ikke i {{ x , y } | ( x , y ) ∈ V 2 ∧ x ≠ y} . Så for at tillade sløjfer skal definitionerne udvides. For enkle ustyrede grafer, E ⊆ {{ x , y } | ( x , y ) ∈ V 2 ∧ x ≠ y} skal blive E ⊆ {{ x , y } | ( x , y ) ∈ V 2 } . For ustyrede multigrafier, ϕ : E → {{ x , y } | ( x , y ) ∈ V 2 ∧ x ≠ y} skal blive ϕ : E → {{ x , y } | ( x , y ) ∈ V 2 } . For at undgå tvivl kan disse typer objekter kaldes nøjagtigt en ikke-rettet enkel graf med hhv. Sløjfer og en ikke-rettet multigraf med hhv.
V og E antages generelt at være endelige, og mange resultater ophører med at være sande (eller har forskellige udsagn) for uendelige grafer, fordi nogle bevisargumenter ikke oversættes til det uendelige tilfælde. Desuden antages V ofte at være ikke-frit, men E kan være det tomme sæt. Den rækkefølge af en graf | V | er antallet af hjørner. Den størrelse af en graf er | E |, antallet af kanter. Den grad eller valens for en knude er antallet af kanter hændelsen til at Isse, hvor en løkke tæller det dobbelte.
I en simpel ikke-rettet graf af rækkefølge n er den maksimale grad af et toppunkt n - 1, og den maksimale størrelse af grafen er n ( n - 1) / 2 .
Kanterne E af en ikke-orienteret graf G inducerer en symmetrisk binær forhold på ~ V kaldes adjacency forhold af G . Specifikt for hver kant { x , y } siges dens ekstreme hjørner x og y at være ved siden af hinanden, hvilket betegnes x ~ y .
En rettet graf er en graf, hvor kanterne har en retning.
I en begrænset, men meget udbredt betydning af udtrykket, er en rettet graf et par G = ( V , A ) (undertiden G = ( V , E ) ) omfattende
For at undgå tvivl kan denne type genstand kaldes nøjagtigt en rettet enkel graf .
I pilens ( x , y ) orienteret fra x til y , x kaldes halen af pilen og y den hovedet af pilen. Pilen ( y , x ) kaldes den inverse pil på ( x , y ) .
I en mere generel betydning af udtrykket, der tillader flere pile, er en rettet graf en triplet G = ( V , A , ϕ ) (undertiden G = ( V , E , ϕ ) ) inklusive
For at undgå tvivl kan denne type objekt kaldes nøjagtigt et orienteret multigrafi .
Rettede grafer som defineret i de foregående to definitioner kan ikke have sløjfer, fordi en sløjfe, der forbinder et toppunkt x, er pilen (for en simpel rettet graf) eller er indfaldende på (for en rettet multigraf) ( x , x ), som ikke er i { ( x , y ) | ( x , y ) ∈ V 2 ∧ x ≠ y} . Så for at tillade sløjfer skal definitionerne udvides. For enkle orienterede grafer, A ⊆ {( x , y ) | ( x , y ) ∈ V 2 ∧ x ≠ y} skal blive A ⊆ V 2 . For orienterede multigrafier, ϕ : A → {( x , y ) | ( x , y ) ∈ V 2 ∧ x ≠ y} skal blive ϕ : A → V 2 . For at undgå tvivl, kan disse typer af objekter kaldes netop en simpel orienteret graf med løkker og en rettet Multigraph med sløjfer (eller et pilekogger ) hhv.
En simpel rettet graf med sløjfer er en homogen relation (en binær relation mellem et sæt og sig selv). En simpel orienteret graf med løkker G = ( V , A ) kaldes symmetrisk hvis for hver pil A , det tilsvarende inverse arrow også i A .
Der er tre hovedfamilier med grafer og fem kategorier i alt:
En artikel af den schweiziske matematiker Leonhard Euler , præsenteret for Akademiet i Sankt Petersborg i 1735 og derefter offentliggjort i 1741, behandlede problemet med de syv Königsberg-broer , som vist skematisk nedenfor. Problemet var at finde en strandpromenade fra et givet punkt, der vender tilbage til det punkt, der passerer en og kun en gang gennem hver af de syv broer i byen Königsberg. En sti, der passerede gennem en højderyg nøjagtigt en gang, blev kaldt Eulerian stien eller Eulerian kredsløb, hvis den ender, hvor den startede. I forlængelse heraf kaldes en graf , der tillader et Eulerian-kredsløb, en Eulerian-graf , som derfor udgør det første egenskabssag for en graf. Euler havde formuleret, at en graf kun er eulerisk, hvis hvert toppunkt har et lige antal kanter. Skikken er at henvise til det som Eulers sætning , skønt beviset først blev leveret 130 år senere af den tyske matematiker Carl Hierholzer . Et lignende problem er at gå gennem hvert toppunkt nøjagtigt en gang og blev først løst med det specielle tilfælde af, at en ridder skulle besøge hver firkant på et skakbræt af den arabiske skakteoretiker Al-Adli i sit arbejde Kitab ash -shatranj offentliggjort omkring 840 og tabt siden. Ridderen turné blev undersøgt nærmere i det XVIII th århundrede af den franske matematiker Alexandre-Théophile Vandermonde , Pierre Remond de Montmort og Abraham de Moivre ; Den britiske matematiker Thomas Kirkman studerede det mere generelle problem med ruten, hvor man kun kan passere et toppunkt en gang, men en sådan rute tog til sidst navnet Hamiltonian sti efter den irske matematiker William Rowan Hamilton , og selvom dette sidstnævnte kun studerede en bestemt sag. Vi giver derfor Euler oprindelsen til grafteori, fordi han var den første til at foreslå en matematisk behandling af spørgsmålet efterfulgt af Vandermonde.
I midten af det XIX th århundrede, den britiske matematiker Arthur Cayley var interesseret i de træer , som er en særlig form for graf med ingen cyklus, dvs. hvor det er umuligt at vende tilbage til et udgangspunkt uden at gøre den omvendte vej. Især studerede han antallet af træer med n hjørner og viste, at der er nogle . Dette udgjorde "en af de smukkeste formler inden for enumerativ kombinatorik ", et felt bestående af at tælle antallet af elementer i et endeligt sæt, og åbnede også vejen for optælling af grafer med bestemte egenskaber. Dette forskningsfelt blev virkelig initieret af den ungarske matematiker George Pólya , der offentliggjorde i 1937 tællesætningen, der bærer hans navn , og den hollandske matematiker Nicolaas Govert de Bruijn . Cayleys arbejde havde, ligesom Polyas, anvendelser til kemi, og den engelske matematiker James Joseph Sylvester , medforfatter af Cayley, introducerede i 1878 udtrykket "graf" baseret på kemi:
”Det er måske ikke helt uden interesse for naturlæsere at være opmærksom på en analogi, der for nylig imponerede meget mellem grene af menneskelig viden, tilsyneladende lige så forskellig som kemi og moderne algebra. […] Hver invariant og covariant bliver derfor udtrykkelig med en graf, der er nøjagtig identisk med et Kékuléan-diagram eller kemikograf. "
Et af de mest kendte problemer i grafteorien kommer fra graffarvning , hvor målet er at bestemme, hvor mange forskellige farver der er nok til at farve en graf fuldstændigt, så intet toppunkt har samme farve som dets naboer. I 1852 skitserede den sydafrikanske matematiker Francis Guthrie problemet med fire farver i en diskussion med sin bror, der spurgte sin lærer Auguste De Morgan, om et kort kunne farves med fire farver, så nabolandene havde forskellige farver. De Morgan sendte først et brev til den irske matematiker William Rowan Hamilton , som ikke var interesseret, og derefter offentliggjorde den engelske matematiker Alfred Kempe fejlagtige beviser i American Journal of Mathematics , som netop var grundlagt af Sylvester. Undersøgelsen af dette problem førte til mange udviklinger inden for grafteori af Peter Guthrie Tait , Percy John Heawood , Frank Ramsey og Hugo Hadwiger .
Problemerne med faktorisering af grafer opstod således i slutningen af XIX E århundrede ved at være interesseret i de spændende underbilleder, det vil sige i graferne, der indeholder alle hjørnerne, men kun en del af kanterne. En spændende undergraf kaldes en k- faktor, hvis hver af dens hjørner har k kanter, og de første sætninger blev givet af Julius Petersen ; for eksempel viste han, at en graf kan opdeles i 2-faktorer, hvis og kun hvis alle hjørnerne har et lige antal kanter (men det tog 50 år for Bäbler at håndtere det ulige tilfælde). Ramseys arbejde med farvning, og især resultaterne af den ungarske matematiker Pal Turan , tillod udviklingen af teorien om ekstreme grafer med fokus på grafer, der nåede det maksimale af en bestemt mængde (for eksempel antallet af kanter) med givne begrænsninger, såsom fraværet af visse underbilleder.
I anden halvdel af det XX th århundrede, de franske matematiker Claude Berge bidrager til udviklingen af grafteori af hans bidrag om perfekte grafer og indførelsen af perioden for hypergraph (efter de bemærkninger, Jean-Marie Pla de har brugt i en seminar) med en monografi om emnet. Hans indledende bog om grafteori tilbød også et originalt alternativ, der mere består af en personlig gåtur end en fuld beskrivelse. Det vil også markere fransk forskning på dette område ved fælles oprettelse med Marcel-Paul Schützenberger af et ugentligt seminar på Henri Poincaré-instituttet, møder mandage i Maison des Sciences de l'Homme og ledelsen af det kombinerende team fra Paris.
Tyskerne Franz Ernst Neumann og Jacobi , henholdsvis fysiker og matematiker, grundlagde en række seminarer i 1834. Den tyske fysiker Gustav Kirchhoff var en af de studerende, der deltog i seminaret mellem 1843 og 1846, og han udvidede Georg Ohms arbejde til at etablere Kirchhoffs love i 1845, der udtrykte bevarelse af energi og ladning i et elektrisk kredsløb . Især dens lov om knudepunkter siger, at summen af intensiteten af strømme, der kommer ind i en knude, er lig med den, der forlader den. Et elektrisk kredsløb kan ses som en graf, hvor hjørnerne er kredsløbets noder, og kanterne svarer til de fysiske forbindelser mellem disse noder. For at modellere de strømme, der strømmer gennem kredsløbet, anses det for, at hver kant kan krydses af en strømning . Dette giver mange analogier, for eksempel til strømmen af en væske såsom vand gennem et netværk af kanaler eller cirkulationen i et vejnet. Som bestemt af loven om knuder bevares strømmen ved et toppunkt eller identisk ved indgangen som ved udgangen; for eksempel forsvinder ikke vandet, der kommer ind i en kanal, og kanalen producerer ingen, så der er lige så meget vand, som det kommer ind. Derudover har en kant en kapacitetsgrænse, ligesom en kanal kan bære en bestemt maksimal mængde vand. Hvis vi tilføjer, at strømmen starter ved et bestemt toppunkt ( kilden ), og at det ender ved et andet ( vasken ), opnår vi de grundlæggende principper for studiet af strømme i en graf.
Hvis vi overvejer, at kilden er et oliefelt, og at brønden er raffinaderiet, hvor den drænes, så ønsker vi at justere ventilerne for at få den bedst mulige strøm fra kilden til brønden. Med andre ord forsøger vi at have så effektiv anvendelse som muligt af kapaciteten på hver af kanterne, hvilket er det maksimale flowproblem . Antag, at vi "klipper" grafen i to dele, således at kilden er i den ene og vasken i den anden. Hver strøm skal passere mellem de to dele og er derfor begrænset af den maksimale kapacitet, som den ene del kan sende til den anden. At finde udskæringen med den mindste kapacitet indikerer derfor det sted, hvor netværket er mest begrænset, hvilket svarer til at etablere den maksimale strøm, der kan krydse det. Denne sætning kaldes flow-max / cut-min og blev etableret i 1956.
Undersøgelsen af netværksstrømme er generaliseret på flere måder. Søgningen efter et maksimum, her i tilfælde af flow, er et optimeringsproblem , som er grenen af matematik, der består i at optimere ( dvs. finde et minimum eller maksimum) en funktion under visse begrænsninger. Et netværksflow er underlagt tre begrænsninger: kapacitetsgrænsen på hver kant, oprettelsen af et ikke-nul-flow mellem kilden og vasken ( dvs. kilden skaber et flow) og ligestillingen mellem input / output-flowet for enhver vertex andet end kilden og drænene ( dvs. de hverken forbruger eller genererer en del af strømmen). Disse begrænsninger er lineære , og problemet med et netværksflow er en del af lineær optimering . Det er også muligt at tilføje andre variabler til problemet for at tage højde for flere situationer: vi kan således have flere kilder og dræn (in) , en minimumskapacitet (in) på hver kant, en pris ved brug af en kant eller en forstærkning af strømmen (ved), der passerer gennem en kant.
Indtil midten af det XX th århundrede, bygge en graf algoritme var ikke tilfældigt: så længe de parametre, der leveres til algoritmen ikke ændrede, så grafen det bygget var det samme. En bestemt dosis tilfældighed blev derefter indført, og algoritmerne blev således sandsynlige . Matematikeren af russisk oprindelse Anatol Rapoport havde denne idé først i 1957, men den blev foreslået uafhængigt to år senere på en mere formel måde af de ungarske matematikere Paul Erdős og Alfréd Rényi . De spekulerede på, hvordan en "typisk" graf med n hjørner og m kanter ser ud . De ønskede at vide, hvilke egenskaber der kunne findes med n hjørner, og m kanter oprettet tilfældigt. Da en fast mængde m ikke er praktisk at besvare dette spørgsmål, blev det besluttet, at hver kant ville eksistere med en sandsynlighed p . Dette var begyndelsen af teorien om tilfældige grafer , hvor vi finder en række knudepunkter n stor nok, og vi er interesseret i sandsynligheden p tilstrækkelig til grafen at have en vis egenskab.
Erdős og Rényi opdagede, at grafen ikke udviklede sig lineært, men i stedet var der en kritisk sandsynlighed p, hvorefter den ændrede sig radikalt. Denne adfærd er velkendt i fysikken: om der er et glas vand, som er bragt i en fryser , er det ikke gradvist ændrer sig til is temmelig brat, når temperaturen falder til under 0 ° C . Vandet havde to faser (væske og is) og passerer fra den ene til den anden ved et fænomen kaldet fase overgang, overgangen er hurtig omkring et kritisk punkt , som i dette tilfælde er temperaturen af 0 ° C . For mange observerede egenskaber fungerer tilfældige grafer på samme måde: der er en kritisk sandsynlighed, under hvilken de er i en subkritisk fase, og over hvilken de passerer i en superkritisk fase. I tilfældet med en tilfældig graf er sandsynligheden for, at vi observerer den egenskab, der er af interesse for os, lav i den underkritiske fase, men bliver meget høj ( dvs. kvasi-sikkerhed) i den overkritiske fase; plottet for sandsynligheden for at have ejendommen som en funktion af p har derfor et meget specifikt udseende, forenklet i diagrammet til højre.
Ud over det fælles ordforråd for faser findes teorien om tilfældige grafer i statistisk fysik i form af perkolationsteorien . Sidstnævnte havde oprindeligt til formål at undersøge strømmen af en væske gennem et porøst materiale . For eksempel, hvis vi nedsænker en pimpsten i en spand fyldt med vand, er vi interesserede i, hvordan vandet vil strømme gennem stenen. For at modellere dette problem fokuserer vi på de vigtige parametre: stenens alder eller farve betyder ikke noget, mens åbningerne eller 'kanaler', hvor vandet kan cirkulere, er vigtige. Den enkleste abstraktion er at se en sten som et gitter, hvor hver kanal findes med en sandsynlighed p . Vi finder således modellen for den tilfældige graf, men med en rumlig begrænsning : en kant kan kun eksistere mellem to hjørner, hvis de er naboer i gitteret. Denne begrænsning kan dog fjernes for at etablere en ækvivalens mellem teorien om grafer og perkolation. For det første kan en graf med n hjørner repræsenteres af et gitter med n dimensioner; da vi er interesseret i det tilfælde, hvor n er stor nok, det vil sige , etablerer dette en ækvivalens med perkolering i uendelig dimension. Derudover er der en kritisk dimension, således at resultatet ikke længere afhænger af dimensionen, så snart den er nået ; denne kritiske dimension menes at være 6, men den kunne kun bevises for 19.
Der er blevet foreslået mange modeller siden begyndelsen af 2000'erne for at finde fænomener observeret i grafer som den, der repræsenterer forbindelserne mellem Hollywood-aktører (opnået af IMDb ) eller dele af Internettet . I 1999 forklarede Albert-László Barabási og Réka Albert , at et af disse fænomener "er en konsekvens af to mekanismer: netværket vokser kontinuerligt med tilføjelsen af nye toppe, og de nye toppe knytter sig med visse præferencer til andre, der allerede har det godt på plads ". En vis forvirring afgjort omkring deres model: hvis det faktisk gør det muligt at opnå det ønskede fænomen, er det ikke den eneste model, der når frem til dette resultat, og vi kan derfor ikke konkludere med at se fænomenet, at det resulterer i en præferentiel tilknytningsproces. Fænomenerne med den lille verden og stordriftsfrihed , som mange modeller er blevet foreslået for, kan opnås simpelthen ved hjælp af tilfældige grafer: teknikken fra Michael Molloy og Bruce Reed gør det muligt at opnå effekten af skalafri, mens Li , Leonard og Loguinov fører til den lille verden.
Formelt er en graf mærket : hvert toppunkt eller kant hører til et sæt og bærer derfor en etiket . Typisk er grafer mærket med hele tal, men en etiket kan faktisk tilhøre ethvert sæt: sæt farver, sæt ord, sæt reelle tal. Eksemplerne overfor viser grafer mærket med heltal og bogstaver. Mærkning af en graf kan designes til at give nyttig information til problemer såsom ruting : startende fra et toppunkt , vi ønsker at nå frem til et toppunkt , dvs. vi vil rute information fra til . Afhængigt af hvordan hjørnerne er mærket, kan de etiketter, der bærer og let, let finde en vej. For eksempel, i Kautz-grafen (in) hvor den maksimale afstand mellem to hjørner er , forestil dig at vi er ved et mærket toppunkt, og som vi vil gå til : skift bare etiketten ved at indtaste destinationen, hvilket giver vej
Denne sti lyder som følger: hvis du er øverst på den mærkede, skal du gå til naboen med etiketten osv.
Vi står dog over for et problem: hvis vi ser over illustrationen af listen over træer med 2, 3 og 4 hjørner, har mange af dem nøjagtigt den samme struktur, men en anden mærkning (givet her af farver). For kun at studere strukturen har vi brug for et værktøj, der gør det muligt at ignorere mærkning, det vil sige at give en strukturel ækvivalens. Til dette introducerer vi begrebet morfisme. En grafmorfisme eller grafhomomorfisme er en applikation mellem to grafer, der respekterer grafernes struktur. Med andre ord, billedet af grafen i skal respektere adjacency relationer til stede i . Mere præcist, hvis og er to grafer, er en applikation en morfisme af grafer, hvis hvor omdanner hjørnerne af G til dem af H, og kanterne af G til dem af H under overholdelse af følgende begrænsning: hvis der er en kant mellem to hjørner af så skal der være en kant mellem de to tilsvarende hjørner af . Vi siger om homomorfisme, at det er en injektion (henholdsvis overkastelse ), hvis dens to funktioner og er injektionsdygtige (henholdsvis overvejende); hvis de begge er injektions- og surjective, dvs. bijective , så er en graf isomorfisme . Hvis to grafer er isomorfe, har de samme struktur: Uanset hvordan de tegnes eller mærkes, er det muligt at flytte hjørnerne eller ændre etiketterne, så den ene er en carbonkopi af den anden, som illustreret nedenfor. Vi derefter betegne som umærket graf for ækvivalens klasse af en graf for isomorphism forhold. To isomorfe grafer vil derefter blive betragtet som lige, hvis vi betragter dem som umærkede grafer.
Graf G | Graf H | Isomorfisme mellem G og H. |
---|---|---|
![]() |
![]() |
|
Ordgrafen kan, afhængigt af konteksten, betegne en mærket eller umærket graf. Når vi taler om webgrafen, er etiketter URL'er og har en betydning. Ordet bruges til at betegne en mærket graf. I modsætning hertil betragtes Petersen-grafen altid op til isomorfisme, derfor umærket, kun dens strukturelle egenskaber er af interesse.
Den hyperkubus mærket på alfabetet
Graf mærket med heltal
Graf mærket med bogstaver
Enhver graf kan repræsenteres af en matrix . Forholdet mellem kanter og hjørner, kaldet incidensrelationer, er alle repræsenteret af grafens incidensmatrix . Relationer mellem tilgrænsninger (hvis to hjørner er forbundet med en kant, de er tilstødende) er repræsenteret af dens nærhed matrix . Det er defineret af
Kurve | Repræsentation ved en nærhedsmatrix | Repræsentation ved en laplacisk matrix (ikke normaliseret) |
---|---|---|
![]() |
En masse information i en graf kan repræsenteres af en matrix. For eksempel er matrixen af grader en diagonal matrix, hvor elementerne svarer til antallet af forbindelser i toppunktet , det vil sige til dets grad . Ved hjælp af denne matrix og den foregående kan vi også definere den laplaciske matrix ; vi får sin normaliserede form af , hvor betegner identitetsmatrixen , eller vi kan også få den direkte af hvert af dens elementer:
Disse repræsentationer afhænger af, hvordan hjørnerne i grafen er mærket. Lad os forestille os, at vi holder den samme struktur som i eksemplet ovenfor, og at vi vender etiketterne 1 og 6 : Vi vender derefter kolonne 1 og 6 i adjacency matrixen. Der er dog mængder, der ikke afhænger af, hvordan vi mærker hjørnerne, såsom minimum / maksimum / gennemsnit grad af grafen. Disse mængder er invarianter i grafen: de ændres ikke i henhold til nummereringen. Mens en nærhed eller laplacisk matrix varierer, er dens spektrum , det vil sige sæt af egenværdier , en invariant. Undersøgelsen af forholdet mellem spektre og egenskaberne for en graf er genstand for spektralgrafteori ; blandt de interessante forhold giver spektret information om det kromatiske antal , antallet af tilsluttede komponenter og cyklusser i grafen.
Da grafer kan repræsentere mange situationer, er der mange algoritmer ( dvs. programmer), der bruger dem. Den kompleksitet af en algoritme i det væsentlige består i at vide, om et givet problem, hvor meget tid er nødvendig for at løse det, og hvad er maskinrummet, at det vil bruge. Nogle grafrepræsentationer giver bedre ydeevne, dvs. problemet løses hurtigere eller tager mindre plads. I nogle tilfælde kan et NP-komplet problem (sværeste klasse) på en gengivelse af en graf løses i polynomisk tid (enkel klasse) med en anden repræsentation; ideen er ikke, at det er nok at se på grafen forskelligt for at løse problemet hurtigere, men at man "betaler" for at transformere det, og at man derefter "sparer" for at løse problemet. En sådan transformation er trænedbrydning foreslået af matematikere Robertson og Seymour i deres serie Graph Minors . Intuitivt repræsenterer en trænedbrydning den oprindelige graf ved et træ, hvor hvert toppunkt svarer til en delmængde af hjørnerne af G med nogle begrænsninger. For en given graf er dets trænedbrydning formelt, hvor er et træ og en funktion, der forbinder med hvert toppunkt et sæt hjørner . Tre begrænsninger skal være opfyldt:
Den træ bredde af en nedbrydning af en graf er , det vil sige størrelsen af den største sæt repræsenteret ved et toppunkt minus 1; vi kan se det som den maksimale abstraktion: for en top af træet, op til hvor mange hjørner af grafen repræsenterer vi? At bygge trænedbrydningen af en hvilken som helst graf med den mindste træbredde er et NP-hårdt problem. Dette kan dog gøres hurtigt for nogle grafer eller tilnærmes andre for f.eks. Plane grafer ( dvs. kan tegnes uden at krydse to kanter).
Robertson og Seymour udviklede også begrebet forgrening . For at forstå det skal du introducere mere ordforråd i et træ. I graferne tegnes et træ "på hovedet": vi starter fra roden øverst, og vi stiger ned, indtil vi når bladene i bunden; ethvert toppunkt, der ikke er et blad, kaldes en 'indre knude'. Nedbrydningen i grene resulterer i et træ, hvor hver intern knude har nøjagtigt tre naboer (som i eksemplet overfor), og hvor hvert blad repræsenterer en kant af den oprindelige graf. Den mindste dybde for nedbrydningen af en graf bemærkes , og vi har forholdet . Hvad angår trænedbrydning, er det NP-svært at konstruere en grennedbrydning med minimal for enhver graf; i dette tilfælde er denne konstruktion mulig for en plan graf .
Disse repræsentationer bruges på NP-komplette problemer ved hjælp af dynamiske programmeringsteknikker , som generelt tager eksponentiel tid i eller . Et sådant problem er for eksempel det dominerende sæt : vi vil vide, om der højst er en delmængde af størrelseshjørner, således at et toppunkt, der ikke er i y, er forbundet med en kant. Hvis grafen er plan, gør denne teknik det muligt at løse problemet i tide .
Den måde, hvorpå grafen er repræsenteret som et matematisk objekt, blev diskuteret i det foregående afsnit. I det algoritmiske aspekt af grafteori søger vi at designe en effektiv proces til at håndtere et problem, der involverer en graf. Hovedkriterierne for effektiviteten af en proces er den tid, det tager at få svaret, og den plads, som processen bruger i sit arbejde. Den måde, hvorpå vi repræsenterer grafen, påvirker ydeevnen i tid og rum: for eksempel, hvis vi vil vide eksistensen af en kant mellem to hjørner, vil nærhedsmatricen gøre det muligt at få et resultat med det samme, det vi kalder i . På den anden side er en grundlæggende operation som at finde nabo til et toppunkt på en nærhedsmatrix: i værste fald vil det være nødvendigt at scanne hele kolonnen for at finde ud af, at der ikke er nogen nabo. En anden datastruktur er nærhedslisten , der består af en matrix, hvis indgang giver listen over naboerne til toppunktet : På en sådan struktur finder man en nabo, mens eksistensen af en kant er inde . Således afhænger tidsmæssigt valg af struktur af de grundlæggende operationer, som man ønsker at optimere.
Repræsentation ved hjælp af listen over grafen overfor: | ||
0 | ved siden af | 0,1,2,3 |
1 | ved siden af | 0 |
2 | ved siden af | 0.3.4 |
3 | ved siden af | 0,2 |
4 | ved siden af | 2 |
Ligeledes afhænger pladsen, som en struktur bruger, af den anvendte graftype: en voldelig genvej består i at sige, at en liste over tilknytninger bruger mindre plads end en matrix, fordi sidstnævnte vil være sparsom , men det tager for eksempel mere plads til at gemme en tilfældig graf med listerne end med en matrix; i det generelle tilfælde bruger en matrix plads og derfor bruger lister, hvis grafen er tæt, så kan den være stor nok til, at en matrix bruger mindre plads, og hvis grafen er sparsom, vil listerne forbruge mindre plads. Enkle ændringer af en datastruktur kan gøre det muligt at have en mærkbar forstærkning: for eksempel i en delvist suppleret repræsentation af en liste angiver en speciel bit, om listen er den af de tilstedeværende eller manglende naboer ; denne teknik gør det muligt at have lineære algoritmer som supplement til en graf.
Mens disse strukturer er lokale, er der også distribuerede datastrukturer . Princippet i disse strukturer er at designe en mærkningsordning , således at for to knudepunkter og , kan man besvare et spørgsmål som "hvad er afstanden mellem og " kun ved hjælp af etiketter på disse knudepunkter; sådan brug af etiketter blev set i afsnittet “ Mærkning og morfismer ” med Kautz-grafen, hvor vi kun kan udlede stien mellem to hjørner takket være deres etiket, og længden af denne sti giver os afstanden. Mærkning er effektiv, hvis det kun giver mulighed for at besvare et givet spørgsmål ved hjælp af to tags, samtidig med at det maksimale antal bits for et tag minimeres. Udover afstanden kan et typisk spørgsmål være at teste nærhed, det vil sige at vide, om to hjørner er tætte; bemærk, at dette også koger ned til det specielle tilfælde af en afstand 1. Det første eksempel på effektiv mærkning til test af tilstødning blev foreslået i tilfælde af træer, og hver etiket består af to bitdele: den første del identificerer toppunktet, og et tal op til kræver bits, der skal kodes , mens den anden del identificerer forældren til det øverste punkt; For at teste nærhed bruger vi det faktum, at to hjørner er naboer i et træ, hvis og kun hvis den ene er forælder til den anden.
Effektiviteten af en mærkningsordning er knyttet til størrelsen på separatorerne i grafen.
Definition - en separator er en delmængde af hjørner, der "opdeler" hjørnerne i grafen i to komponenter og sådan, at og der ikke er nogen kanter mellem hjørnerne af og .
Hvis en graf har størrelsesseparatorer , kan vi for eksempel designe bitetiketter til afstanden; dette gør det muligt direkte at udlede mærkningen for grafer, hvis størrelse af separatorerne er kendt, såsom en plan graf, hvor separatoren er af størrelse . Endelig skal vi ikke kun overveje størrelsen på mærkningen, men også den nødvendige tid, givet to etiketter, til at udføre afkodningen, der besvarer spørgsmålet ( dvs. hvad er afstanden? Er de naboer?).
Mange grafproblemer er NP-komplette, dvs. svære at løse. Denne hårdhed er imidlertid ujævn: nogle dele af problemet kan være særligt barske og udgør således dets kerne, mens andre er ret nemme at håndtere. Så før du kører en algoritme på et problem, der kan være hårdt, er det bedst at bruge lidt tid på at reducere dette problem, så du kun behøver at overveje din kerne.