Vorlesungen

Inhalte

    1. Grundbegriffe der Graphentheorie
    Graphen, Untergraphen, Digraphen
    Wege, Kreise, Zusammenhang
    Eulersche Kreise und Wege
    Hamiltonsche Kreise und Wege
    Einige Anwendungsbeispiele
    Elektrische Schaltungen
    Chemische Isomere CnH2n

    2. Graphentheoretische Algorithmen
    Algorithmen
    Darstellung von Graphen
    Bewertete Graphen und Digraphen, Netzwerke
    Datenstrukture
    Komplexität von Algorithmen
    Kreisfreie Digraphen, topologische Sortierung

    3. Kürzeste Wege in Digraphen
    Kürzeste Wege von einem fixierten Knoten (Algorithmus von Dijkstra)
    Kürzeste Wege zwischen zwei Teilmengen von Knoten
    Kürzeste Wege zwischen allen Paaren von Knoten (Algorithmus von Floyd-Warshall)
    Optimale Plazierung und Trassierung

    4. Minimale Bäume in Graphen
    Minimale Gerüste
    Der Algorithmus von Prim
    Der Algorithmus von Kruskal
    Optimale Steiner-Bäume

    5. Enumeration von Graphen
    Markierte Graphen und Digraphen
    Nicht markierte Graphen

Literatur

  • Berge, C.: Théorie des graphes et ses applications. Dunod, Paris, 1958.
  • Bodendiek, R. und Lang, R.: Lehrbuch der Graphentheorie. Spektrum Akademischer Verlag,
    Band 1, 1995, ISBN: 3-86025-667-X,
    Band 2, 1996, ISBN: 3-86025-668-8.
  • Christofides, N.: Graph Theory. An Algorithmic Approach. Academic Press, NY, 1975.
  • Diestel, R.: Graphentheorie. Springer-Verlag, Heidelberg ISBN: 3-540-67656-2.
  • Garey, M. and Johnson, D.: Computers and Intractability (A guide to the theory of NP-completeness). W.H. Freeman and Company, NY, 1979.
  • Harary, F.: Graph Theory. Addison-Wesley, Reading, Mass. 1969.
  • Jungnickel, D.: Graphen, Netzwerke und Algorithmen. B.I.-Wissenschaftsverlag, Wien-Zütich, 1994. ISBN: 3-411-14263-4.
  • König, D.: Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe. Akad. Verlag, Leipig, 1936.
  • Minieka, E.: Optimization Algorithms for Networks and Graphs. Marcel Dekker, NY, 1978.
  • Nägler, G. und Stopp, F. : Graphen und Anwendungen. Teubner-Verlag, 1996. ISBN: 3-8154-2084-9.
  • Ore, O.: Theory of Graphs. Providence, Rhode Island, 1962.
  • Swamy M. and Thulasiraman, K: Graphs, Networks and Algorithms. Wiley-Inter-Science, NY, 1981.
  • Turau, V.: Algorithmische Graphentheorie. Addison Wesley, Bonn, 1996. ISBN: 3-89319-938-1.
  • Volkmann, L.: Fundamente der Graphentheorie. 1996. XIX, 446 S. Springer-Verlag, Berlin- Heidelberg, ISBN: 3-211-82774-9.