Zum Inhalt springen
OneKitly
Registrieren · Anmelden

Graphfärbungs-Rechner

Färbe einen Graphen so, dass zwei benachbarte Knoten nie dieselbe Farbe haben. Gib eine Kantenliste ein, und die DSATUR- (oder Greedy-)Heuristik weist jedem Knoten eine Farbe zu, zeigt die Farbklassen und nennt eine obere Schranke der chromatischen Zahl χ. K4 braucht 4 Farben, ein gerader Kreis 2, ein ungerader Kreis 3 — sofort sichtbar.

Ähnliche Tools

Alle Tools: Diskrete Mathematik & Graphen →
Planarer-Graph-PrüferTeste, ob ein Graph wahrscheinlich planar ist. Gib eine Kantenliste ein: Das Tool wendet Eulers notwendige Ungleichungen an (E ≤ 3V−6 und E ≤ 2V−4 bei Dreiecksfreiheit) und sucht nach K5- und K3,3-Teilgraphen aus dem Satz von Kuratowski. Es ist eine ehrliche Heuristik, kein vollständiger Planaritätsalgorithmus: „nicht planar" ist sicher, „wahrscheinlich planar" ist kein Beweis. Auf 16 Knoten begrenzt.Bitweise-Operationen-RechnerUND, ODER, XOR, NICHT und Verschiebungen in Binär, Dezimal oder Hex, mit 8, 16, 32 oder 64 Bit, samt Bit-für-Bit-Diagramm und Ergebnis in allen drei Basen. Mit BigInt gerechnet, damit die 64-Bit-Ergebnisse dort stimmen, wo JavaScripts eigene 32-Bit-Operatoren stillschweigend abschneiden würden.Delaunay-Triangulations-GeneratorFüge eine Menge von 2D-Punkten ein und es trianguliert sie auf Delaunay-Art — die Triangulation, die dünne Splitterdreiecke vermeidet, bei der kein Punkt im Umkreis eines anderen Dreiecks liegt. Es führt den Bowyer-Watson-Algorithmus im Browser aus und zeichnet das Netz, mit Punkt-, Dreiecks- und Kantenzahl.Dijkstra-Kürzeste-Wege-RechnerGib einen gewichteten Graphen als Kanten ein („A, B, 4" pro Zeile) sowie einen Startknoten: Der Dijkstra-Algorithmus liefert die minimale Distanz und den genauen Weg vom Start zu jedem erreichbaren Knoten. Funktioniert für gerichtete oder ungerichtete Graphen, akzeptiert viele Kantenformate und markiert nicht erreichbare Knoten — ideal für Routing, Netzwerke und Wegfindung.Gruppentheorie-OrdnungsrechnerAnalysiere die klassischen endlichen Gruppen — zyklisch Zₙ, direkte Produkte Zₘ×Zₙ, Dieder Dₙ und symmetrisch Sₙ. Es gibt die Gruppenordnung, ob sie abelsch ist, ihre Struktur, die Erzeugerzahl bei zyklischen Gruppen und die Ordnung jedes eingegebenen Elements, auch einer Permutation in Zyklenschreibweise für Sₙ.Hamiltonscher-Weg-und-Kreis-PrüferPrüfe, ob ein Graph einen Hamiltonschen Weg (besucht jeden Knoten einmal) oder einen Hamiltonschen Kreis (kehrt zusätzlich zum Start zurück) besitzt. Gib eine Kantenliste ein, wähle gerichtet oder ungerichtet, und eine erschöpfende Backtracking-Suche liefert einen konkreten Weg und Kreis oder beweist, dass keiner existiert. Auf 12 Knoten begrenzt.Karnaugh-Diagramm-Löser (K-Map)Minimiere eine boolesche Funktion mit dem Quine–McCluskey-Algorithmus: Gib Minterme, Maxterme oder eine Wahrheitstabelle ein und erhalte die minimale SOP- oder POS-Form, Primimplikanten und die Literalanzahl.Topologische-Sortierung-RechnerOrdne die Knoten eines gerichteten Graphen so, dass jede Kante nach vorn zeigt. Gib gerichtete Kanten ein („A -> B"): Das Tool führt den Kahn-Algorithmus mit lexikografischer Reihung und eine DFS-Nachordnung aus und liefert beide gültigen Ordnungen. Enthält der Graph einen Zyklus, ist er kein DAG — das Tool erkennt ihn und zeigt den betreffenden Zyklus.

Graphfärbungs-Rechner kannst du kostenlos und beliebig oft direkt auf dieser Seite nutzen. Sein Platz ist unter Diskrete Mathematik & Graphen; Planarer-Graph-Prüfer und Bitweise-Operationen-Rechner beantworten die nächstliegenden Fragen.

So funktioniert's

  1. Öffne das Tool — ohne Anmeldung oder Installation.
  2. Gib deine Daten ein oder passe die verfügbaren Optionen an.
  3. Erhalte dein Ergebnis sofort und kopiere oder lade es herunter.

Häufige Fragen

Wofür ist Graphfärbungs-Rechner da?

Färbe einen Graphen so, dass zwei benachbarte Knoten nie dieselbe Farbe haben. Gib eine Kantenliste ein, und die DSATUR- (oder Greedy-)Heuristik weist jedem Knoten eine Farbe zu, zeigt die Farbklassen und nennt eine obere Schranke der chromatischen Zahl χ. K4 braucht 4 Farben, ein gerader Kreis 2, ein ungerader Kreis 3 — sofort sichtbar.

Wie sieht ein konkreter Fall aus?

K₄ → 4 · C₅ → 3 · K₃,₃ → 2 — das Werkzeug zeigt jeden Zwischenschritt, nicht nur das Endergebnis.

Wann brauche ich das konkret?

Alles, was sich als Knoten und Kanten modellieren lässt: kürzester Weg, Netzkapazität, ein Ablaufplan mit Abhängigkeiten oder eine auf ihre Logik reduzierte Schaltung.

Was ist der häufigste Fehler?

Annehmen, ein kürzester Weg bleibe kürzester, wenn ein Gewicht das Vorzeichen wechselt. Negative Kanten brechen das Greedy-Argument, auf dem Dijkstra ruht — der Algorithmus liefert dann selbstsicher ein falsches Ergebnis statt eines Fehlers.

Worin unterscheidet sich Graphfärbungs-Rechner von Planarer-Graph-Prüfer?

Sie liegen nah beieinander, beantworten aber verschiedene Fragen. Planarer-Graph-Prüfer: teste, ob ein Graph wahrscheinlich planar ist. Gib eine Kantenliste ein: Das Tool wendet Eulers notwendige Ungleichungen an (E ≤ 3V−6 und E ≤ 2V−4 bei Dreiecksfreiheit) und sucht nach K5- und K3,3-Teilgraphen aus dem Satz von Kuratowski. Es ist eine ehrliche Heuristik, kein vollständiger Planaritätsalgorithmus: „nicht planar" ist sicher, „wahrscheinlich planar" ist kein Beweis. Auf 16 Knoten begrenzt. Nimm das, was zu deinem Ausgangspunkt passt — beide sind kostenlos.

Woher stammen die Daten?

Die Algorithmen sind die aus dem Lehrbuch, ihre Ergebnisse exakt für den eingegebenen Graphen. Was variiert, sind die Kosten: für mehrere dieser Probleme ist keine effiziente Lösung bekannt, große Eingaben werden heuristisch beantwortet — das Werkzeug sagt es.

Zum Weiterlesen

Alle Ratgeber →
ErklärungMinus siebzehn modulo fünf hat zwei verschiedene Antworten17 mod 5 ist überall 2. −17 mod 5 ist −2 in JavaScript, C und Java und 3 in Python, Ruby und einer Tabellenkalkulation. Beides ist richtig, und der Unterschied ist ein echter Fehler.ErklärungDas Schubfachprinzip beweist, dass etwas existiert, ohne es zu findenZehn Gegenstände in drei Fächern erzwingen vier in einem davon. 367 Menschen erzwingen einen gemeinsamen Geburtstag. Keine der Aussagen sagt, welches Fach oder welches Paar.ErklärungEin Kegel ist genau ein Drittel seines ZylindersRadius 5, Höhe 10: Der Kegel fasst 261,8, der ihn umgebende Zylinder 785,4. Das Verhältnis ist genau ein Drittel und gilt für jede beliebige Grundform.ErklärungEine Formel, die auch ein Rechteck und auch ein Dreieck istParallele Seiten von 8 und 5 bei einer Höhe von 4 ergeben eine Fläche von 26 — die mittlere Breite mal der Höhe. Mach beide Seiten gleich, und es ist ein Rechteck; schrumpfe eine auf null, und es ist ein Dreieck.ErklärungDoppelt so breit fasst das Vierfache; doppelt so hoch nur das DoppelteEin Zylinder mit Radius 5 und Höhe 10 fasst 785,4 Volumeneinheiten. Verdopple den Radius, und er fasst 3.141,6; verdopple stattdessen die Höhe, und er fasst 1.570,8.ErklärungVierzig hin und sechzig zurück ergeben im Mittel achtundvierzigDas harmonische Mittel von 40 und 60 ist 48, nicht 50, weil die langsamere Strecke länger dauert und daher stärker zählt. Für 1, 2 und 4 beträgt es 1,714 gegen ein arithmetisches Mittel von 2,33.