Knoten
Kanten
Komponenten

Klick
  • Regulär
  • Vollständig

Mehr über Graphentheorie

Graphentheorie-Spielplatz

Ein Graph ist eine Menge von Punkten, den Knoten, die durch Linien, die Kanten, verbunden sind. Zeichnen Sie hier mit wenigen Klicks einen, und der Spielplatz verrät Ihnen, was für ein Graph es ist: aus wie vielen Komponenten er besteht, ob er ein Baum ist, mit wie wenigen Farben er auskommt, ob er sich in einem Zug zeichnen lässt und mehr. Klicken Sie auf eine Eigenschaft, um sie in Ihrem Graphen zu sehen, ändern Sie eine Kante und beobachten Sie, wie sich die Antworten ändern. Klicken Sie auf eine freie Stelle, um einen Knoten hinzuzufügen. Klicken Sie auf einen Knoten und dann auf einen anderen, um beide mit einer Kante zu verbinden; wiederholen Sie das, um die Kante wieder zu entfernen. Ziehen Sie einen Knoten, um ihn zu verschieben. Stellen Sie den Klick auf Radieren um, dann löscht ein Klick den getroffenen Knoten oder die getroffene Kante. Ist ein Knoten ausgewählt, entfernt ihn Entf, und Esc hebt die Auswahl auf. Klicken Sie auf eine Eigenschaft, um sie im Graphen anzuzeigen. Beispiel lädt einen bekannten Graphen, Zufallsgraph erzeugt einen, Aufräumen verteilt die Knoten übersichtlich, und Komplement verbindet genau die Paare, die bisher nicht verbunden waren. Ctrl+Z macht einen Schritt rückgängig.

Wie es funktioniert

  1. Klicken Sie auf eine freie Stelle, um einen Knoten hinzuzufügen. Klicken Sie auf einen Knoten und dann auf einen anderen, um beide zu verbinden; wiederholen Sie das, um die Kante zu entfernen. Ziehen Sie einen Knoten, um ihn zu verschieben.
  2. Lesen Sie die Eigenschaften unter dem Graphen ab und klicken Sie auf eine, um sie anzuzeigen: eine Färbung, die zwei Seiten, einen Eulerweg, einen Spannbaum, den kürzesten Kreis oder den Durchmesser.
  3. Laden Sie ein Beispiel wie den Petersen-Graphen, erzeugen Sie einen Zufallsgraphen, bilden Sie das Komplement, oder stellen Sie den Klick auf Radieren um, um Knoten und Kanten zu löschen.

Was die Eigenschaften bedeuten

Der Grad eines Knotens ist die Anzahl der Kanten an ihm. Ein Graph ist zusammenhängend, wenn jeder Knoten jeden anderen entlang der Kanten erreichen kann, und ein Baum, wenn er zusammenhängend ist und keinen Kreis enthält. Er ist bipartit, wenn sich seine Knoten so auf zwei Seiten aufteilen lassen, dass jede Kante hinüberführt, und das ist genau dann der Fall, wenn er keinen Kreis ungerader Länge hat. Die chromatische Zahl ist die kleinste Anzahl von Farben, mit der benachbarte Knoten verschiedene Farben bekommen. Die Länge des kürzesten Kreises heißt Taillenweite, und der Durchmesser ist der größte Abstand zwischen zwei Knoten, gezählt in Kanten.

In einem Zug zeichnen

Ein Eulerweg benutzt jede Kante genau einmal. Leonhard Euler erkannte 1736 an den sieben Brücken von Königsberg, was dem im Weg steht: Jedes Mal, wenn ein Weg durch einen Knoten führt, verbraucht er zwei seiner Kanten. Also ist entweder jeder Grad gerade, und der Weg kann enden, wo er begonnen hat, oder genau zwei Grade sind ungerade, und der Weg muss von einem dieser Knoten zum anderen führen. Carl Hierholzer bewies später, dass diese Bedingung zusammen mit zusammenhängenden Kanten auch ausreicht. Laden Sie das Haus vom Nikolaus und finden Sie heraus, wo der Zug beginnen muss.

Häufig gestellte Fragen

Was ist ein Graph in der Graphentheorie?

Eine Menge von Punkten, Knoten oder Ecken genannt, und Linien zwischen einigen Paaren davon, den Kanten. Gemeint ist nicht der Graph einer Funktion: Ein solcher Graph beschreibt nur, was womit verbunden ist. Straßenkarten, soziale Netzwerke, Moleküle und Computernetze sind alles Graphen.

Wie wird die chromatische Zahl bestimmt?

Der Spielplatz versucht, den Graphen mit einer Farbe zu färben, dann mit zwei, dann mit drei und so weiter, und durchsucht für jede Anzahl alle Möglichkeiten, auf die es ankommt; dabei färbt er als Nächstes immer den Knoten, dessen Nachbarn schon die meisten Farben verwenden. Die erste Anzahl, die funktioniert, ist die chromatische Zahl. Bei den Graphen, die man hier zeichnen kann, dauert das höchstens einen Moment; bei einem sehr schwierigen Graphen bricht die Suche vorzeitig ab, und der Wert wird als obere Schranke angezeigt.

Wann hat ein Graph einen Eulerweg?

Wenn alle seine Kanten zusammenhängen und höchstens zwei Knoten ungeraden Grad haben. Ohne ungerade Knoten gibt es einen Eulerkreis, der endet, wo er beginnt; bei zwei ungeraden Knoten beginnt jeder Eulerweg bei einem von ihnen und endet beim anderen. Die Anzahl der ungeraden Knoten ist immer gerade, also nie genau eins.

Was ist das Komplement eines Graphen?

Der Graph auf denselben Knoten, dessen Kanten genau die Paare sind, die vorher nicht verbunden waren. Das Komplement des Komplements ist wieder der Ausgangsgraph. Das Komplement des Petersen-Graphen zum Beispiel ist 6-regulär, weil jeder Knoten mit 3 der 9 anderen verbunden war.

Warum ist der Petersen-Graph so berühmt?

Er ist ein kleiner Graph mit 10 Knoten und 15 Kanten, der viele hoffnungsvolle Vermutungen widerlegt. Jeder Knoten hat Grad 3, sein kürzester Kreis hat die Länge 5, je zwei Knoten sind höchstens 2 Kanten voneinander entfernt, und er lässt sich nicht ohne Kantenkreuzungen zeichnen. Der Spielplatz startet mit ihm.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Zum Editor