Diskrete Mathematik - Mehr zu Graphen

Diagrammfärbung

Die Graphfärbung ist das Verfahren zum Zuweisen von Farben zu jedem Scheitelpunkt eines Graphen G, so dass keine benachbarten Scheitelpunkte dieselbe Farbe erhalten. Ziel ist es, die Anzahl der Farben beim Färben eines Diagramms zu minimieren. Die kleinste Anzahl von Farben, die zum Färben eines Graphen G erforderlich ist, wird als chromatische Zahl dieses Graphen bezeichnet. Das Problem der Farbfärbung ist ein NP-Komplettproblem.

Methode zum Färben eines Diagramms

Die Schritte zum Färben eines Graphen G mit n Eckpunkten sind wie folgt:

Step 1 - Ordnen Sie die Eckpunkte des Diagramms in einer bestimmten Reihenfolge an.

Step 2 - Wählen Sie den ersten Scheitelpunkt und färben Sie ihn mit der ersten Farbe.

Step 3- Wählen Sie den nächsten Scheitelpunkt aus und färben Sie ihn mit der Farbe mit der niedrigsten Nummer, die auf den angrenzenden Scheitelpunkten nicht gefärbt wurde. Wenn alle benachbarten Scheitelpunkte mit dieser Farbe gefärbt sind, weisen Sie ihr eine neue Farbe zu. Wiederholen Sie diesen Schritt, bis alle Eckpunkte farbig sind.

Example

In der obigen Abbildung ist der erste Scheitelpunkt $ a $ rot gefärbt. Da die benachbarten Scheitelpunkte des Scheitelpunkts a wieder benachbart sind, werden der Scheitelpunkt $ b $ und der Scheitelpunkt $ d $ mit unterschiedlicher Farbe, grün bzw. blau, gefärbt. Dann wird der Scheitelpunkt $ c $ rot gefärbt, da kein benachbarter Scheitelpunkt von $ c $ rot gefärbt ist. Daher könnten wir den Graphen mit 3 Farben färben. Daher ist die chromatische Zahl des Graphen 3.

Anwendungen der Graphfärbung

Einige Anwendungen der Diagrammfärbung umfassen -

Zuordnung registrieren
Kartenfärbung
Bipartite Graph Checking
Mobilfunkfrequenzzuweisung
Zeitplan usw. erstellen.

Graph Traversal

Das Durchlaufen von Graphen ist das Problem, alle Scheitelpunkte eines Graphen in einer systematischen Reihenfolge zu besuchen. Es gibt hauptsächlich zwei Möglichkeiten, einen Graphen zu durchlaufen.

Breite erste Suche
Tiefe Erste Suche

Breite erste Suche

Die Breitensuche (BFS) beginnt am Startpunkt $ X $ des Graphen $ G $. Dann besuchen wir alle Eckpunkte, die die Nachbarn von $ X $ sind. Nach dem Besuch markieren wir die Eckpunkte als "besucht" und platzieren sie in Ebene 1. Dann gehen wir von den Eckpunkten der Ebene 1 aus und wenden dieselbe Methode auf jeden Eckpunkt der Ebene 1 an und so weiter. Die BFS-Durchquerung wird beendet, wenn jeder Scheitelpunkt des Diagramms besucht wurde.

BFS Algorithm

Das Konzept besteht darin, alle Nachbarscheitelpunkte zu besuchen, bevor andere Nachbarscheitelpunkte von Nachbarscheitelpunkten besucht werden.

Initialisieren Sie den Status aller Knoten als "Bereit".
Stellen Sie den Quellscheitelpunkt in eine Warteschlange und ändern Sie seinen Status in "Warten".
Wiederholen Sie die folgenden zwei Schritte, bis die Warteschlange leer ist -
- Entfernen Sie den ersten Scheitelpunkt aus der Warteschlange und markieren Sie ihn als "Besucht".
- Fügen Sie am Ende der Warteschlange alle Nachbarn des entfernten Scheitelpunkts hinzu, deren Status "Bereit" ist. Markieren Sie ihren Status als "Warten".

Problem

Nehmen wir ein Diagramm (Quellscheitelpunkt ist 'a') und wenden den BFS-Algorithmus an, um die Durchlaufreihenfolge herauszufinden.

Solution - -

Initialisieren Sie den Status aller Scheitelpunkte auf "Bereit".
Stellen Sie eine Warteschlange ein und ändern Sie ihren Status in "Warten".
Entfernen Sie eine aus der Warteschlange und markieren Sie sie als "Besucht".
Fügen Sie einen ‚Nachbarn in Zustand‚Bereit‘ b, d und e der Warteschlange zu beenden und markieren Sie sie als‚Waiting‘.
Entfernen Sie b aus der Warteschlange, markieren Sie es als "Besucht", setzen Sie den Nachbarn "Bereit" c am Ende der Warteschlange und markieren Sie c als "Warten".
Entfernen Sie d aus der Warteschlange und markieren Sie es als "Besucht". Es hat keinen Nachbarn im Status "Bereit".
Entfernen Sie e aus der Warteschlange und markieren Sie es als "Besucht". Es hat keinen Nachbarn im Status "Bereit".
Entfernen Sie c aus der Warteschlange und markieren Sie es als "Besucht". Es hat keinen Nachbarn im Status "Bereit".
Die Warteschlange ist leer, also hör auf.

Die Durchquerungsreihenfolge lautet also -

$ a \ rightarrow b \ rightarrow d \ rightarrow e \ rightarrow c $

Die alternativen Durchlaufreihenfolgen sind -

$ a \ rightarrow b \ rightarrow e \ rightarrow d \ rightarrow c $

Oder $ a \ rightarrow d \ rightarrow b \ rightarrow e \ rightarrow c $

Oder $ a \ rightarrow e \ rightarrow b \ rightarrow d \ rightarrow c $

Oder $ a \ rightarrow b \ rightarrow e \ rightarrow d \ rightarrow c $

Oder $ a \ rightarrow d \ rightarrow e \ rightarrow b \ rightarrow c $

Application of BFS

Den kürzesten Weg finden
Minimaler Spanning Tree für ungewichtete Diagramme
GPS-Navigationssystem
Erkennen von Zyklen in einem ungerichteten Diagramm
Finden aller Knoten innerhalb einer verbundenen Komponente

Complexity Analysis

Sei $ G (V, E) $ ein Graph mit $ | V | $ Anzahl der Eckpunkte und $ | E | $ Anzahl der Kanten. Wenn der Breitensuchalgorithmus jeden Scheitelpunkt im Diagramm besucht und jede Kante überprüft, ist seine zeitliche Komplexität -

$$ O (| V | + | E |). O (| E |) $$

Sie kann zwischen $ O (1) $ und $ O (| V2 |) $ variieren

Tiefe Erste Suche

Der DFS-Algorithmus (Depth First Search) beginnt mit einem Scheitelpunkt $ v $, wechselt dann zu seinem benachbarten Scheitelpunkt (z. B. x), der zuvor noch nicht besucht wurde, markiert als "besucht" und fährt mit dem benachbarten Scheitelpunkt $ x $ und fort demnächst.

Wenn an einem Scheitelpunkt festgestellt wird, dass alle benachbarten Scheitelpunkte besucht werden, wird zurückverfolgt, bis der erste Scheitelpunkt mit einem benachbarten Scheitelpunkt gefunden wird, der zuvor noch nicht durchlaufen wurde. Dann durchquert es diesen Scheitelpunkt, fährt mit seinen benachbarten Scheitelpunkten fort, bis es alle besuchten Scheitelpunkte durchquert und erneut zurückverfolgen muss. Auf diese Weise werden alle vom anfänglichen Scheitelpunkt $ v $ erreichbaren Scheitelpunkte durchlaufen.

DFS Algorithm

Das Konzept besteht darin, alle Nachbarscheitelpunkte eines Nachbarscheitelpunkts zu besuchen, bevor die anderen Nachbarscheitelpunkte besucht werden.

Initialisieren Sie den Status aller Knoten als "Bereit".
Legen Sie den Quellscheitelpunkt in einen Stapel und ändern Sie seinen Status in "Warten".
Wiederholen Sie die folgenden zwei Schritte, bis der Stapel leer ist -
- Nehmen Sie den oberen Scheitelpunkt vom Stapel und markieren Sie ihn als "Besucht".
- Schieben Sie alle Nachbarn des entfernten Scheitelpunkts, deren Status "Bereit" ist, auf die Oberseite des Stapels. Markieren Sie ihren Status als "Warten".

Problem

Nehmen wir ein Diagramm (Quellscheitelpunkt ist 'a') und wenden den DFS-Algorithmus an, um die Durchlaufreihenfolge herauszufinden.

Solution

Initialisieren Sie den Status aller Scheitelpunkte auf "Bereit".
Schieben Sie einen In-Stack und ändern Sie seinen Status in "Warten".
Pop a und markieren Sie es als "Visited".
Drücken Sie eine ‚Nachbarn in Zustand‚Bereit‘ e, d und b nach oben Stapel und markieren Sie sie als‚Waiting‘.
Pop b vom Stapel, markieren Sie es als "Visited", schieben Sie seinen "Ready" -Nachbar c auf den Stapel.
Pop c vom Stapel und markieren Sie es als "Visited". Es hat keinen "Bereit" -Nachbarn.
Pop d vom Stapel und markieren Sie es als "Visited". Es hat keinen "Bereit" -Nachbarn.
Pop e vom Stapel und markieren Sie es als "Visited". Es hat keinen "Bereit" -Nachbarn.
Der Stapel ist leer. Also hör auf.

Die Durchquerungsreihenfolge lautet also -

$ a \ rightarrow b \ rightarrow c \ rightarrow d \ rightarrow e $

Die alternativen Durchlaufreihenfolgen sind -

$ a \ rightarrow e \ rightarrow b \ rightarrow c \ rightarrow d $

Oder $ a \ rightarrow b \ rightarrow e \ rightarrow c \ rightarrow d $

Oder $ a \ rightarrow d \ rightarrow e \ rightarrow b \ rightarrow c $

Oder $ a \ rightarrow d \ rightarrow c \ rightarrow e \ rightarrow b $

Oder $ a \ rightarrow d \ rightarrow c \ rightarrow b \ rightarrow e $

Complexity Analysis

Sei $ G (V, E) $ ein Graph mit $ | V | $ Anzahl der Eckpunkte und $ | E | $ Anzahl der Kanten. Wenn der DFS-Algorithmus jeden Scheitelpunkt im Diagramm besucht und jede Kante überprüft, beträgt die zeitliche Komplexität -

$$ \ circleddash (| V | + | E |) $$

Applications

Zyklus in einem Diagramm erkennen
Topologische Sortierung finden
Um zu testen, ob ein Graph zweiteilig ist
Verbundene Komponenten finden
Finden der Brücken eines Graphen
Bi-Konnektivität in Diagrammen finden
Lösung des Knight's Tour-Problems
Rätsel lösen mit nur einer Lösung