Graph-Algorithmus

Ein Graph ist eine abstrakte Notation, die verwendet wird, um die Verbindung zwischen Objektpaaren darzustellen. Ein Graph besteht aus -

• Vertices- Verbundene Objekte in einem Diagramm werden als Scheitelpunkte bezeichnet. Scheitelpunkte werden auch als bezeichnetnodes.

• Edges - Kanten sind die Verknüpfungen, die die Eckpunkte verbinden.

Es gibt zwei Arten von Diagrammen:

• Directed graph - In einem gerichteten Graphen haben Kanten eine Richtung, dh Kanten gehen von einem Scheitelpunkt zum anderen.

• Undirected graph - In einem ungerichteten Diagramm haben Kanten keine Richtung.

Diagrammfärbung

Die Diagrammfärbung ist eine Methode zum Zuweisen von Farben zu den Scheitelpunkten eines Diagramms, sodass keine zwei benachbarten Scheitelpunkte dieselbe Farbe haben. Einige Probleme beim Färben von Grafiken sind -

• Vertex coloring - Eine Möglichkeit, die Scheitelpunkte eines Diagramms so zu färben, dass keine zwei benachbarten Scheitelpunkte dieselbe Farbe haben.

• Edge Coloring - Hiermit wird jeder Kante eine Farbe zugewiesen, sodass keine zwei benachbarten Kanten dieselbe Farbe haben.

• Face coloring - Es weist jeder Fläche oder Region eines planaren Graphen eine Farbe zu, sodass keine zwei Flächen, die eine gemeinsame Grenze haben, dieselbe Farbe haben.

Chromatische Zahl

Die chromatische Zahl ist die Mindestanzahl von Farben, die zum Färben eines Diagramms erforderlich sind. Beispielsweise ist die chromatische Zahl des folgenden Diagramms 3.

Das Konzept der Grafikfärbung wird bei der Erstellung von Fahrplänen, der Zuweisung von Mobilfunkfrequenzen, Suduku, der Registerzuweisung und der Färbung von Karten angewendet.

Schritte zum Färben von Grafiken

• Setzen Sie den Anfangswert jedes Prozessors im n-dimensionalen Array auf 1.

• Um nun einem Scheitelpunkt eine bestimmte Farbe zuzuweisen, bestimmen Sie, ob diese Farbe bereits den benachbarten Scheitelpunkten zugewiesen ist oder nicht.

• Wenn ein Prozessor dieselbe Farbe in den benachbarten Scheitelpunkten erkennt, setzt er seinen Wert im Array auf 0.

• Wenn nach n ² Vergleichen ein Element des Arrays 1 ist, ist es eine gültige Färbung.

Pseudocode für die Grafikfärbung

begin

   create the processors P(i0,i1,...in-1) where 0_iv < m, 0 _ v < n
   status[i0,..in-1] = 1
	
   for j varies from 0 to n-1 do
      begin
		
         for k varies from 0 to n-1 do
         begin
            if aj,k=1 and ij=ikthen
            status[i0,..in-1] =0
         end
			
      end
      ok = ΣStatus
		
   if ok > 0, then display valid coloring exists
   else
      display invalid coloring
      
end

Minimaler Spanning Tree

Ein Spannbaum, dessen Summe aus Gewicht (oder Länge) aller seiner Kanten geringer ist als alle anderen möglichen Spannbäume des Graphen G, ist als a bekannt minimal spanning tree oder minimum cost spanningBaum. Die folgende Abbildung zeigt einen gewichteten verbundenen Graphen.

Einige mögliche Spannbäume des obigen Diagramms sind unten dargestellt -

Unter allen oben genannten Spannbäumen ist Abbildung (d) der minimale Spannbaum. Das Konzept des Spanning Tree mit minimalen Kosten wird beim Problem des Handlungsreisenden, beim Entwerfen elektronischer Schaltungen, beim Entwerfen effizienter Netzwerke und beim Entwerfen effizienter Routing-Algorithmen angewendet.

Um den minimalen Kostenbereich zu implementieren, werden die folgenden zwei Methoden verwendet:

• Prims Algorithmus
• Kruskals Algorithmus

Prims Algorithmus

Prims Algorithmus ist ein gieriger Algorithmus, der uns hilft, den minimalen Spannbaum für einen gewichteten ungerichteten Graphen zu finden. Es wählt zuerst einen Scheitelpunkt aus und findet eine Kante mit dem niedrigsten Gewicht, das auf diesen Scheitelpunkt fällt.

Schritte des Prim-Algorithmus

• Wählen Sie einen beliebigen Scheitelpunkt aus, z. B. v ₁ in Diagramm G.

• Wählen Sie eine Kante aus, sagen Sie e ₁ von G, so dass e ₁ = v ₁ v ₂ und v ₁ ≠ v ₂ und e ₁ ein minimales Gewicht unter den Kanten haben, die auf v ₁ in Grafik G fallen.

• Wählen Sie nun nach Schritt 2 die minimale gewichtete Kante aus, die auf v ₂ einfällt .

• Fahren Sie fort, bis n - 1 Kanten ausgewählt wurden. Hiern ist die Anzahl der Eckpunkte.

Der minimale Spannbaum ist -

Kruskals Algorithmus

Der Kruskal-Algorithmus ist ein gieriger Algorithmus, der uns hilft, den minimalen Spannbaum für einen verbundenen gewichteten Graphen zu finden und bei jedem Schritt steigende Kostenbögen hinzuzufügen. Es handelt sich um einen Minimum-Spanning-Tree-Algorithmus, der eine Kante mit dem geringstmöglichen Gewicht findet, die zwei beliebige Bäume im Wald verbindet.

Schritte des Kruskal-Algorithmus

• Wählen Sie eine Kante mit minimalem Gewicht. sagen wir e ₁ von Graph G und e ₁ ist keine Schleife.

• Wählen Sie die nächste minimale gewichtete Kante aus, die mit e _{1 verbunden ist} .

• Fahren Sie fort, bis n - 1 Kanten ausgewählt wurden. Hiern ist die Anzahl der Eckpunkte.

Der minimale Spannbaum des obigen Diagramms ist -

Algorithmus für kürzeste Wege

Der Algorithmus für den kürzesten Pfad ist eine Methode zum Ermitteln des Pfades mit den geringsten Kosten vom Quellknoten (S) zum Zielknoten (D). Hier werden wir den Moore-Algorithmus diskutieren, der auch als Breadth First Search-Algorithmus bekannt ist.

Moores Algorithmus

• Beschriften Sie den Quellscheitelpunkt S und beschriften Sie ihn i und setzen i=0.

• Suchen Sie alle unbeschrifteten Scheitelpunkte neben dem beschrifteten Scheitelpunkt i. Wenn keine Scheitelpunkte mit dem Scheitelpunkt S verbunden sind, ist der Scheitelpunkt D nicht mit S verbunden. Wenn Scheitelpunkte mit S verbunden sind, beschriften Sie siei+1.

• Wenn D markiert ist, fahren Sie mit Schritt 4 fort, andernfalls fahren Sie mit Schritt 2 fort, um i = i + 1 zu erhöhen.

• Halten Sie an, nachdem die Länge des kürzesten Pfades gefunden wurde.