-
Reguljär
-
Komplett
Grafteorins lekplats
En graf är en mängd punkter, kallade hörn, förbundna med linjer, kallade kanter. Rita en här med några klick, så berättar lekplatsen vilken sorts graf det är: hur många delar den har, om den är ett träd, hur få färger den behöver, om den kan ritas i ett streck och mycket mer. Klicka på en egenskap för att se den i din graf, ändra en kant och se svaren ändras. Klicka på en tom plats för att lägga till ett hörn. Klicka på ett hörn och sedan på ett annat för att förbinda dem med en kant; gör det igen för att ta bort kanten. Dra i ett hörn för att flytta det. Byt klicket till Suddar och klicka på ett hörn eller en kant för att ta bort det. När ett hörn är markerat tar Delete bort det och Esc släpper det. Klicka på en egenskap för att visa den i grafen. Exempel läser in en känd graf, Slumpgraf skapar en ny, Städa upp sprider ut hörnen och Komplement förbinder precis de par som inte var förbundna. Ctrl+Z ångrar ett steg.
Hur det fungerar
- Klicka på en tom plats för att lägga till ett hörn. Klicka på ett hörn och sedan på ett annat för att förbinda dem; gör det igen för att ta bort kanten. Dra i ett hörn för att flytta det.
- Läs egenskaperna under grafen och klicka på en av dem för att visa den: en färgning, de två sidorna, en Eulerväg, ett uppspännande träd, den kortaste cykeln eller diametern.
- Läs in ett exempel som Petersengrafen, skapa en slumpgraf, ta komplementet eller byt klicket till Suddar för att ta bort hörn och kanter.
Vad egenskaperna betyder
Ett hörns grad är antalet kanter som möts i det. En graf är sammanhängande när varje hörn kan nå alla andra längs kanterna, och ett träd när den är sammanhängande och saknar cykler. Den är bipartit när hörnen kan delas upp i två sidor så att varje kant går tvärs över, vilket händer precis när den saknar cykler av udda längd. Det kromatiska talet är det minsta antal färger som ger grannar olika färger. Längden av den kortaste cykeln kallas grafens midja (eng. girth), och diametern är det största avståndet mellan två hörn, räknat i kanter.
Att rita i ett streck
En Eulerväg använder varje kant exakt en gång. Leonhard Euler såg 1736, med Königsbergs sju broar, vad som står i vägen: varje gång vägen passerar ett hörn använder den två av dess kanter. Så antingen är alla grader jämna, och vägen kan sluta där den började, eller så är exakt två grader udda, och vägen måste gå från det ena av dem till det andra. Carl Hierholzer visade senare att detta, när alla kanter hänger ihop i ett stycke, också räcker. Läs in husexemplet och ta reda på var strecket måste börja.
Ofta ställda frågor
Vad är en graf inom grafteori?
En mängd punkter, kallade hörn eller noder, och linjer mellan några av paren, kallade kanter. Det är inte grafen till en funktion: den beskriver bara vad som är förbundet med vad. Vägkartor, sociala nätverk, molekyler och datornätverk är alla grafer.
Hur räknas det kromatiska talet ut?
Lekplatsen försöker färga grafen med en färg, sedan två, sedan tre och så vidare, och för varje antal söker den igenom alla sätt som spelar roll. Den färgar alltid härnäst det hörn vars grannar redan använder flest färger. Det första antalet som fungerar är det kromatiska talet. För graferna du kan rita här tar det som mest ett ögonblick; i en mycket svår graf avbryts sökningen tidigt och värdet visas som en övre gräns.
När har en graf en Eulerväg?
När alla dess kanter hänger ihop i ett stycke och högst två hörn har udda grad. Utan hörn med udda grad finns det en Eulerkrets som slutar där den börjar; med två börjar varje Eulerväg i det ena av dem och slutar i det andra. Antalet hörn med udda grad är alltid jämnt, så det är aldrig exakt ett.
Vad är komplementet till en graf?
Grafen på samma hörn vars kanter är precis de par som inte var förbundna tidigare. Komplementet till komplementet är den graf man började med. Petersengrafens komplement är till exempel 6-reguljärt, eftersom varje hörn var förbundet med 3 av de 9 andra.
Varför är Petersengrafen så känd?
Det är en liten graf med 10 hörn och 15 kanter som är ett motexempel till många hoppfulla gissningar. Varje hörn har grad 3, dess kortaste cykel har längden 5, två godtyckliga hörn ligger högst 2 kanter ifrån varandra, och den kan inte ritas utan att kanter korsar varandra. Lekplatsen börjar med den.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Gå till Editor