Graphentheorie

Operations Research 1

Das Kapitel Graphentheorie in unserem Online-Kurs Operations Research 1 besteht aus folgenden Inhalten:

1. Einführung: Graphentheorie

   Graphentheorie > Einführung: Graphentheorie

   

   ... Kapitel beschäftigt sich mit der Graphentheorie. Ein Graph besteht aus $n$ verschiedenen Knoten, welche ganz oder teilweise miteinander verbunden sind. Die Graphentheorie findet Anwendung z.B. bei der Planung von Verkehrsnetzen, Kommunikationsnetzen oder auch Versorgungsnetzen.Grundbegriffe der GraphentheorieEin Graph $G$ besteht aus einer nichtleeren Knotenmenge $V$ und einer Pfeil- oder Kantenmenge $E$. Jedem Element aus $E$ ist genau ein Knotenpaar $[i,j]$ aus $V$ zugeordnet.Es ...

2. Kürzeste Wege

   Graphentheorie > Kürzeste Wege

   

   In diesem Abschnitt sollen kürzesten Wege in Graphen bestimmt werden. Der Algorithmus von Dijkstra und der Fifo-Algorithmus bestimmen die kürzester Entfernung von einem vorgegebenen Startknoten zu allen anderen Knoten des Graphen.  In den folgenden Abschnitten werden die beiden Verfahren ausführlich behandelt. Dabei beschränken sich die folgenden Ausführungen auf Diagraphen.Diagraphen enthalten keine Schlingen und keine parallelen Kanten bzw. Pfeile.

3. Fifo-Algorithmus

   Graphentheorie > Kürzeste Wege > Fifo-Algorithmus

   

   In diesem Abschnitt wird der FIFO-Algorithmus zur Bestimmung von kürzesten Wegen in Graphen ausführlich behandelt.Gegeben sei ein Diagraph mit $n$ Knoten und einem Startknoten. Es werden alle kürzesten Wege zwischen dem Startknoten und allen anderen Knoten gesucht.FIFO-AlgorithmusGegeben sei ein Diagraph mit $n$ Knoten und einem Startknoten $a$. Alle Pfeile seien mit $k(i,j)$ bewertet. Gesucht wird der kürzeste Weg zwischen dem Startknoten und allen anderen Knoten des Diagraphen.Sei ...