Wann ist ein Graph Zweifärbbar?
Dabei sagt man, dass ein ungerichteter Graph zweifärbbar ist, wenn man seine Knoten mit zwei Farben so färben kann, dass adjazente Knoten unterschiedlich gefärbt sind. Entsprechend spricht man von k-färbbar, wenn es eine Färbung der Knoten mit k Farben gibt, so dass adjazente Knoten unterschiedlich gefärbt sind.
Wann ist ein Graph 3 Färbbar?
Knotenfärbungen planarer Graphen Eines der klassischen Probleme der Graphentheorie ist die Frage, wie viele Farben man minimal braucht, um eine Landkarte so zu färben, dass je zwei aneinandergrenzende Länder nicht dieselbe Farbe haben. Enthält der Graph kein Dreieck, so ist er sogar 3-Knoten-färbbar.
Wann ist ein Graph Planar?
Ein planarer oder plättbarer Graph ist in der Graphentheorie ein Graph, der auf einer Ebene, mit Punkten für die Knoten und Linien für die Kanten, dargestellt werden kann, sodass sich keine Kanten schneiden.
Wie viele isomorphe Graphen gibt es?
Zwei Graphen sind genau dann isomorph, wenn ihre kanonischen Labelings übereinstimmen.
Was ist die Anzahl der Färbungen in einem Graph?
Anzahl der Färbungen. Wenn ein Graph färbbar ist, gibt es eine kleinste Zahl k {displaystyle k} , sodass der Graph k {displaystyle k} -knotenfärbbar ist. Diese Zahl wird die chromatische Zahl oder Knotenfärbungszahl des Graphen genannt und meist mit χ {displaystyle chi } ( G ) {displaystyle (G)} bezeichnet.
Was ist eine Verallgemeinerung der Knotenfärbung?
Eine Verallgemeinerung der Knotenfärbung ist der Begriff der Listenfärbung. Hierbei wird jedem Knoten eine „Liste“ von verfügbaren Farben zugeteilt und der Graph soll nun eine gültige Färbung aus diesen Listen erhalten. Des Weiteren gibt es die Totalfärbung, bei der sowohl Knoten als auch Kanten gefärbt werden sollen.
Was ist eine zulässige Knotenfärbung eines Graphens?
Eine zulässige Knotenfärbung eines Graphen ist eine Partition seiner Knotenmenge in unabhängige Mengen. Eine Teilmenge der Knotenmenge eines Graphen heißt unabhängig, falls sie keine zwei benachbarten Knoten enthält. gefärbt ist. Das heißt, für jedes Farbenpaar existieren benachbarte Knoten, die mit diesen Farben gefärbt sind.
Welche Farbklassen sind optimal für eine Färbung?
Farben. Bei einer optimalen Färbung muss zwischen jedem Paar von Farbklassen mindestens eine der -knotenfärbbar, die Partitionsklassen entsprechen hier genau den Farben. Insbesondere sind alle bipartiten Graphen 2-färbbar. Jeder 2-färbbare Graph ist jedoch auch bipartit.