Diagrammfärbung
Das Färben von Diagrammen kann als ein Prozess beschrieben werden, bei dem den Eckpunkten eines Diagramms Farben zugewiesen werden. Dabei sollte nicht die gleiche Farbe zum Füllen der beiden benachbarten Eckpunkte verwendet werden. Wir können die Graphfärbung auch als Scheitelpunktfärbung bezeichnen. Bei der Graphfärbung müssen wir darauf achten, dass ein Graph keine Kante enthalten darf, deren Endscheitelpunkte mit derselben Farbe gefärbt sind. Diese Art von Diagramm wird als richtig gefärbtes Diagramm bezeichnet.
Beispiel für die Einfärbung von Diagrammen
Python-Restoperator
In diesem Diagramm zeigen wir das ordnungsgemäß gefärbte Diagramm, das wie folgt beschrieben wird:
Die obige Grafik enthält einige Punkte, die wie folgt beschrieben werden:
- Die gleiche Farbe kann nicht zum Färben der beiden benachbarten Scheitelpunkte verwendet werden.
- Daher können wir es als richtig gefärbten Graphen bezeichnen.
Anwendungen der Graphfärbung
Es gibt verschiedene Anwendungen der Diagrammfärbung. Einige ihrer wichtigen Anwendungen werden wie folgt beschrieben:
- Abtretung
- Kartenfärbung
- Planen der Aufgaben
- Sudoku
- Bereiten Sie einen Zeitplan vor
- Konfliktlösung
Chromatische Zahl
Die chromatische Zahl kann als die Mindestanzahl an Farben beschrieben werden, die erforderlich ist, um einen Graphen richtig einzufärben. Mit anderen Worten kann die chromatische Zahl als die minimale Anzahl von Farben beschrieben werden, die erforderlich sind, um einen beliebigen Graphen so zu färben, dass keinem zwei benachbarten Scheitelpunkte eines Graphen die gleiche Farbe zugewiesen wird.
Beispiel einer chromatischen Zahl:
Um die chromatische Zahl zu verstehen, betrachten wir einen Graphen, der wie folgt beschrieben wird:
Die obige Grafik enthält einige Punkte, die wie folgt beschrieben werden:
- Zum Färben der beiden benachbarten Scheitelpunkte wird nicht dieselbe Farbe verwendet.
- Die Mindestanzahl an Farben dieses Diagramms beträgt 3, was erforderlich ist, um die Eckpunkte richtig einzufärben.
- Daher ist in diesem Diagramm die chromatische Zahl = 3
- Wenn wir dieses Diagramm richtig einfärben möchten, benötigen wir in diesem Fall mindestens 3 Farben.
Arten der chromatischen Anzahl von Diagrammen:
Es gibt verschiedene Arten von chromatischen Anzahlgraphen, die wie folgt beschrieben werden:
Zyklusdiagramm:
Ein Graph wird als Zyklusgraph bezeichnet, wenn er „n“ Kanten und „n“ Eckpunkte (n >= 3) enthält, die einen Zyklus der Länge „n“ bilden. Es kann nur 2 oder 3 Gradzahlen für alle Scheitelpunkte im Zyklusdiagramm geben.
Chromatische Zahl:
- Die chromatische Zahl in einem Zyklusgraphen ist 2, wenn die Anzahl der Eckpunkte in diesem Graphen gerade ist.
- Die chromatische Zahl in einem Zyklusgraphen ist 3, wenn die Anzahl der Eckpunkte in diesem Graphen ungerade ist.
Beispiele für Zyklusdiagramme:
Es gibt verschiedene Beispiele für Zyklusdiagramme. Einige davon werden wie folgt beschrieben:
Beispiel 1: In der folgenden Grafik müssen wir die chromatische Zahl bestimmen.
Lösung: Im obigen Zyklusdiagramm gibt es drei verschiedene Farben für drei Scheitelpunkte, und keiner der benachbarten Scheitelpunkte hat die gleiche Farbe. In diesem Diagramm ist die Anzahl der Eckpunkte ungerade. Also
Chromatische Zahl = 3
Beispiel 2: In der folgenden Grafik müssen wir die chromatische Zahl bestimmen.
Lösung: Im obigen Zyklusdiagramm gibt es zwei Farben für vier Scheitelpunkte, und keiner der benachbarten Scheitelpunkte ist mit derselben Farbe gefärbt. In diesem Diagramm ist die Anzahl der Eckpunkte gerade. Also
Chromatische Zahl = 2
Beispiel 3: In der folgenden Grafik müssen wir die chromatische Zahl bestimmen.
Lösung: In der obigen Grafik gibt es vier verschiedene Farben für fünf Scheitelpunkte, und zwei benachbarte Scheitelpunkte sind mit derselben Farbe (blau) gefärbt. Dieser Graph ist also kein Zyklusgraph und enthält keine chromatische Zahl.
Beispiel 4: In der folgenden Grafik müssen wir die chromatische Zahl bestimmen.
Lösung: In der obigen Grafik gibt es zwei verschiedene Farben für sechs Scheitelpunkte, und keiner der benachbarten Scheitelpunkte ist mit derselben Farbe gefärbt. In diesem Diagramm ist die Anzahl der Eckpunkte gerade. Also
Chromatische Zahl = 2
Planerdiagramm
Ein Diagramm wird als Plandiagramm bezeichnet, wenn es in einer Ebene gezeichnet wird. Die Kanten des Planerdiagramms dürfen sich nicht kreuzen.
Chromatische Zahl:
- In einem Planerdiagramm muss die chromatische Zahl kleiner oder gleich 4 sein.
- Das Planerdiagramm kann auch durch alle oben genannten Zyklusdiagramme außer Beispiel 3 angezeigt werden.
Beispiele für Planer-Grafiken:
Es gibt verschiedene Beispiele für Planergraphen. Einige davon werden wie folgt beschrieben:
Beispiel 1: In der folgenden Grafik müssen wir die chromatische Zahl bestimmen.
Lösung: Im obigen Diagramm gibt es drei verschiedene Farben für drei Scheitelpunkte, und keine der Kanten dieses Diagramms schneidet einander. Also
Apurva Padgaonkar
Chromatische Zahl = 3
Hier ist die chromatische Zahl kleiner als 4, daher ist dieser Graph ein ebener Graph.
Beispiel 2: In der folgenden Grafik müssen wir die chromatische Zahl bestimmen.
Lösung: Im obigen Diagramm gibt es zwei verschiedene Farben für vier Eckpunkte, und keine der Kanten dieses Diagramms schneidet einander. Also
Chromatische Zahl = 2
Hier ist die chromatische Zahl kleiner als 4, daher ist dieser Graph ein ebener Graph.
Beispiel 3: In der folgenden Grafik müssen wir die chromatische Zahl bestimmen.
Lösung: Im obigen Diagramm gibt es fünf verschiedene Farben für fünf Eckpunkte, und keine der Kanten dieses Diagramms schneidet einander. Also
Chromatische Zahl = 5
Hier ist die chromatische Zahl größer als 4, daher ist dieser Graph kein ebener Graph.
Beispiel 4: In der folgenden Grafik müssen wir die chromatische Zahl bestimmen.
Lösung: Im obigen Diagramm gibt es zwei verschiedene Farben für sechs Eckpunkte, und keine der Kanten dieses Diagramms schneidet einander. Also
Chromatische Zahl = 2
Hier ist die chromatische Zahl kleiner als 4, daher ist dieser Graph ein ebener Graph.
Komplettes Diagramm
Ein Graph wird als vollständiger Graph bezeichnet, wenn nur eine Kante verwendet wird, um alle zwei unterschiedlichen Eckpunkte zu verbinden. Jeder Knoten in einem vollständigen Graphen ist mit jedem anderen Knoten verbunden. In diesem Diagramm wird jeder Scheitelpunkt mit einer anderen Farbe eingefärbt. Das bedeutet, dass im vollständigen Diagramm zwei Eckpunkte nicht dieselbe Farbe enthalten.
Chromatische Zahl
In einem vollständigen Diagramm entspricht die chromatische Zahl der Anzahl der Eckpunkte in diesem Diagramm.
Beispiele für vollständige Diagramme:
Es gibt verschiedene Beispiele für vollständige Diagramme. Einige davon werden wie folgt beschrieben:
Beispiel 1: In der folgenden Grafik müssen wir die chromatische Zahl bestimmen.
Lösung: Es gibt 4 verschiedene Farben für 4 verschiedene Scheitelpunkte und keine der Farben in der obigen Grafik ist gleich. Laut Definition ist eine chromatische Zahl die Anzahl der Eckpunkte. Also,
Chromatische Zahl = 4
entspricht Java
Beispiel 2: In der folgenden Grafik müssen wir die chromatische Zahl bestimmen.
Lösung: Es gibt 5 verschiedene Farben für 5 verschiedene Scheitelpunkte und keine der Farben in der obigen Grafik ist gleich. Laut Definition ist eine chromatische Zahl die Anzahl der Eckpunkte. Also,
Chromatische Zahl = 5
Beispiel 3: In der folgenden Grafik müssen wir die chromatische Zahl bestimmen.
Lösung: Es gibt drei verschiedene Farben für vier verschiedene Scheitelpunkte, und in der obigen Grafik wird eine Farbe in zwei Scheitelpunkten wiederholt. Dieser Graph ist also kein vollständiger Graph und enthält keine chromatische Zahl.
Zweiteiliger Graph
Ein Graph wird als bipartiter Graph bezeichnet, wenn er zwei Sätze von Scheitelpunkten, A und B, enthält. Der Scheitelpunkt von A kann nur mit den Scheitelpunkten von B verbunden werden. Das bedeutet, dass die Kanten die Scheitelpunkte nicht mit einer Menge verbinden können.
Chromatische Zahl
In jedem bipartiten Graphen ist die chromatische Zahl immer gleich 2.
Beispiele für zweiteilige Graphen:
Es gibt verschiedene Beispiele für bipartite Graphen. Einige davon werden wie folgt beschrieben:
Beispiel 1: In der folgenden Grafik müssen wir die chromatische Zahl bestimmen.
Lösung: Im obigen Diagramm gibt es zwei verschiedene Sätze von Scheitelpunkten. Die chromatische Zahl aller bipartiten Graphen ist also immer 2. Also
Chromatische Zahl = 2
Baum:
Ein verbundener Graph wird als Baum bezeichnet, wenn dieser Graph keine Kreise enthält. In einem Baum ist die chromatische Zahl gleich 2, unabhängig davon, wie viele Eckpunkte sich im Baum befinden. Jeder bipartite Graph ist auch ein Baum.
Chromatische Zahl
In jedem Baum ist die chromatische Zahl gleich 2.
Konstruktoren in Java
Beispiele für Bäume:
Es gibt verschiedene Beispiele für einen Baum. Einige davon werden wie folgt beschrieben:
Beispiel 1: Im folgenden Baum müssen wir die chromatische Zahl bestimmen.
Lösung: Es gibt zwei verschiedene Farben für vier Eckpunkte. Ein Baum mit einer beliebigen Anzahl von Eckpunkten muss im obigen Baum die chromatische Zahl 2 enthalten. Also,
Chromatische Zahl = 2
Beispiel 2: Im folgenden Baum müssen wir die chromatische Zahl bestimmen.
Lösung: Es gibt zwei verschiedene Farben für fünf Eckpunkte. Ein Baum mit einer beliebigen Anzahl von Eckpunkten muss im obigen Baum die chromatische Zahl 2 enthalten. Also,
Chromatische Zahl = 2
Reales Beispiel einer chromatischen Zahl
Angenommen, Marry ist Managerin bei der Firma Xyz. Das Unternehmen stellt einige neue Mitarbeiter ein und sie muss einen Schulungsplan für diese neuen Mitarbeiter erstellen. Sie muss die drei Treffen planen und versucht, die wenigen Zeitfenster so gut wie möglich für Besprechungen zu nutzen. Wenn ein Mitarbeiter an zwei verschiedenen Besprechungen teilnehmen muss, muss der Manager unterschiedliche Zeitpläne für diese Besprechungen verwenden. Angenommen, wir möchten eine visuelle Darstellung dieses Treffens erhalten.
Für die visuelle Darstellung verwendet Marry den Punkt, um das Treffen anzuzeigen. Wenn es einen Mitarbeiter gibt, der zwei Besprechungen hat und an beiden Besprechungen teilnehmen möchte, werden beide Besprechungen mithilfe einer Kante verbunden. Die verschiedenen Zeitfenster werden mit Hilfe von Farben dargestellt. Daher füllt der Manager die Punkte mit diesen Farben so, dass nicht zwei Punkte dieselbe Farbe enthalten, die eine gemeinsame Kante haben. (Das bedeutet, dass ein Mitarbeiter, der an den beiden Besprechungen teilnehmen muss, nicht das gleiche Zeitfenster haben darf.) Die visuelle Darstellung hierzu wird wie folgt beschrieben:
