Knuder
Kanter
Dele

Et klik
  • Regulær
  • Komplet

Mere om grafteori

Grafteori-legeplads

En graf er en mængde punkter, kaldet knuder, forbundet af linjer, kaldet kanter. Tegn en her med få klik, så fortæller legepladsen dig, hvilken slags graf det er: hvor mange dele den har, om den er et træ, hvor få farver den behøver, om den kan tegnes i én streg, og meget mere. Klik på en egenskab for at se den på din graf, ændr en kant, og se svarene ændre sig. Klik på et tomt sted for at tilføje en knude. Klik på en knude og derefter på en anden for at forbinde dem med en kant; gør det igen for at fjerne kanten. Træk i en knude for at flytte den. Skift klikket til Sletter, og klik på en knude eller en kant for at slette den. Når en knude er valgt, fjerner Delete den, og Esc slipper den igen. Klik på en egenskab for at vise den på grafen. Eksempel indlæser en kendt graf, Tilfældig graf laver en ny, Ryd op spreder knuderne ud, og Komplement forbinder netop de par, der ikke var forbundet. Ctrl+Z fortryder et trin.

Sådan virker det

  1. Klik på et tomt sted for at tilføje en knude. Klik på en knude og derefter på en anden for at forbinde dem; gør det igen for at fjerne kanten. Træk i en knude for at flytte den.
  2. Læs egenskaberne under grafen, og klik på en af dem for at vise den: en farvning, de to sider, en Eulervej, et udspændende træ, den korteste kreds eller diameteren.
  3. Indlæs et eksempel som Petersen-grafen, lav en tilfældig graf, tag komplementet, eller skift klikket til Sletter for at slette knuder og kanter.

Hvad egenskaberne betyder

En knudes grad er antallet af kanter, der støder til den. En graf er sammenhængende, når hver knude kan nå alle de andre langs kanterne, og et træ, når den er sammenhængende og ikke har nogen kreds. Den er todelt, når dens knuder kan deles i to sider, så hver kant går på tværs, og det sker netop, når den ikke har nogen kreds af ulige længde. Det kromatiske tal er det mindste antal farver, der giver alle naboer forskellige farver. Længden af den korteste kreds kaldes grafens talje (girth), og diameteren er den største afstand mellem to knuder, talt i kanter.

At tegne i én streg

En Eulervej bruger hver kant præcis én gang. Leonhard Euler så i 1736, med Königsbergs syv broer, hvad der står i vejen: hver gang vejen passerer en knude, bruger den to af dens kanter. Så enten er alle grader lige, og vejen kan slutte, hvor den begyndte, eller også er præcis to grader ulige, og vejen må gå fra den ene af dem til den anden. Carl Hierholzer beviste senere, at dette er nok, når alle kanter hænger sammen i ét stykke. Indlæs huseksemplet, og find ud af, hvor stregen skal begynde.

Ofte stillede spørgsmål

Hvad er en graf i grafteori?

En mængde punkter, kaldet knuder, og linjer mellem nogle af parrene, kaldet kanter. Det er ikke grafen for en funktion: den beskriver kun, hvad der er forbundet med hvad. Vejkort, sociale netværk, molekyler og computernetværk er alle grafer.

Hvordan findes det kromatiske tal?

Legepladsen prøver at farve grafen med én farve, så med to, så med tre og så videre, og for hvert antal gennemsøger den alle de muligheder, der betyder noget. Den farver altid den knude som den næste, hvis naboer allerede bruger flest farver. Det første antal, der virker, er det kromatiske tal. For de grafer, du kan tegne her, tager det højst et øjeblik; på en meget svær graf stopper søgningen tidligt, og værdien vises som en øvre grænse.

Hvornår har en graf en Eulervej?

Når alle dens kanter hænger sammen i ét stykke, og højst to knuder har ulige grad. Uden knuder med ulige grad er der en Eulerkreds, der slutter, hvor den begynder; med to begynder enhver Eulervej i den ene af dem og slutter i den anden. Antallet af knuder med ulige grad er altid lige, så det er aldrig præcis én.

Hvad er komplementet til en graf?

Grafen på de samme knuder, hvis kanter er præcis de par, der ikke var forbundet før. Komplementet til komplementet er den graf, man startede med. Petersen-grafens komplement er for eksempel 6-regulært, fordi hver knude var forbundet med 3 af de 9 andre.

Hvorfor er Petersen-grafen så berømt?

Den er en lille graf med 10 knuder og 15 kanter, som er et modeksempel på mange håbefulde formodninger. Hver knude har grad 3, dens korteste kreds har længde 5, to vilkårlige knuder ligger højst 2 kanter fra hinanden, og den kan ikke tegnes uden krydsende kanter. Legepladsen starter med den.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Gå til Editor