05C85 Graph algorithms [See also 68R10, 68W05]
Refine
Language
- English (3)
Keywords
- Directed graph (1)
- Graphen (1)
- MaxFlow-MinCut (1)
- Measure Theory (1)
- Minimal equivalent subgraph (1)
- Network Flows over Time (1)
- Transitive closure (1)
- Transitive reduction (1)
- Wegeprobleme (1)
- Zählen (1)
Transitive reductions and minimal equivalent subgraphs have proven to be a powerful concept to simplify networks and to measure their redundancy. Here we consider a generalization of the minimal equivalent subgraph problem where a set of arcs is already given. For two digraphs D = (V,A), D′ = (V,A′) with A′ ⊆ A, we ask for the minimal set of edges of D that have to be added to D′ such that the transitive closure of D equals the transitive closure of D′.
We present a method to compute such an extension and show that if D is transitively closed, this problem can be solved in polynomial time.
Network flows over time form a fascinating area of research. They model the temporal
dynamics of network flow problems occurring in a wide variety of
applications. Research in this area has been pursued in two different and mainly independent
directions with respect to time modeling: discrete and continuous time models.
In this paper we deploy measure theory in order to introduce a general model of network flows over time combining both discrete and continuous aspects into a single model. Here, the flow on each arc is modeled as a Borel measure on the real line (time axis) which assigns to each
suitable subset a real value, interpreted as the amount of
flow entering the arc over the subset. We focus on the maximum flow problem formulated in a network where capacities on arcs are also given as Borel measures and storage might be allowed at the nodes of the network. We generalize the concept of cuts to the case of these Borel Flows and extend the famous MaxFlow-MinCut Theorem.
Den kürzesten Weg in einem Graphen zu finden ist ein klassisches Problem der Graphentheorie. Über einen Vortrag zu diesem Thema beim Tag der Mathematik 2007 von R. Borndörfer kam ich in Kontakt mit dem Konrad-Zuse-Zentrum (ZIB), das sich u.a. mit Wegeoptimierung beschäftigt. Ein Forschungsschwerpunkt dort ist im Rahmen eines Projekts zur Chipverifikation das Zählen von Lösungen, das, wie wir sehen werden, eng mit dem Zählen von Wegen zusammenhängt.
Anhand von zwei Fragen aus der Graphentheorie soll diese Facharbeit unterschiedliche Lösungsmethoden untersuchen. Wie bestimmt man den kürzesten Weg zwischen zwei Knoten in einem Graphen und wie findet man alle möglichen Wege?
Nach einer Einführung in die Graphentheorie und einer Konkretisierung der Probleme wird zunächst für beide eine Lösung mit auf Graphen basierenden Algorithmen vorgestellt. Während der Algorithmus von Dijkstra sehr bekannt ist, habe ich für das Zählen von Wegen einen eigenen Algorithmus auf der Basis der Tiefensuche entwickelt.
Im zweiten Teil der Arbeit wird das Konzept der ganzzahligen Programmierung vorgestellt und die Lösungsmöglichkeiten für Wegeprobleme, die sich darüber ergeben.