@misc{Ridder2008, author = {Ridder, Johanna}, title = {Wegeprobleme der Graphentheorie}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10782}, number = {08-26}, year = {2008}, abstract = {Den k{\"u}rzesten Weg in einem Graphen zu finden ist ein klassisches Problem der Graphentheorie. {\"U}ber einen Vortrag zu diesem Thema beim Tag der Mathematik 2007 von R. Bornd{\"o}rfer kam ich in Kontakt mit dem Konrad-Zuse-Zentrum (ZIB), das sich u.a. mit Wegeoptimierung besch{\"a}ftigt. Ein Forschungsschwerpunkt dort ist im Rahmen eines Projekts zur Chipverifikation das Z{\"a}hlen von L{\"o}sungen, das, wie wir sehen werden, eng mit dem Z{\"a}hlen von Wegen zusammenh{\"a}ngt. Anhand von zwei Fragen aus der Graphentheorie soll diese Facharbeit unterschiedliche L{\"o}sungsmethoden untersuchen. Wie bestimmt man den k{\"u}rzesten Weg zwischen zwei Knoten in einem Graphen und wie findet man alle m{\"o}glichen Wege? Nach einer Einf{\"u}hrung in die Graphentheorie und einer Konkretisierung der Probleme wird zun{\"a}chst f{\"u}r beide eine L{\"o}sung mit auf Graphen basierenden Algorithmen vorgestellt. W{\"a}hrend der Algorithmus von Dijkstra sehr bekannt ist, habe ich f{\"u}r das Z{\"a}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{\"o}sungsm{\"o}glichkeiten f{\"u}r Wegeprobleme, die sich dar{\"u}ber ergeben. Schließlich wurden die vorgestellten Algorithmen am Beispiel des S- und U-Bahnnetzes von Berlin implementiert und mit Programmen, die die gleichen Fragen {\"u}ber ganzzahlige Programmierung l{\"o}sen, verglichen.}, language = {de} }