Inhalt

- Grundlagen der Mathematik

- Diskrete Mathematik

   - Kombinatorik

   - Graphentheorie

      - Typen von Graphen

          Teilgraphen und Minoren

          Vollständiger Graph

          Bipartiter Graph

         - Wälder

            - Bäume

         - Planarer Graph

       Nachbarschaft und Grad

       Wege, Pfade, Zyklen und

       Kreise

       Isomorphie von Graphen

       Operationen auf Graphen

       Zusammenhang

      - Durchlaufbarkeit von

       Graphen

      - Färbung

       Paarungen in Graphen

      - Schnitte

       Knotenüberdeckungen,

       Cliquen und stabile Mengen

   - Zahlentheorie

- Algebra

- Lineare Algebra

- Geometrie

- Analysis

- Differentialgleichungen

- Funktionalanalysis

- Differentialgeometrie

- Topologie

- Numerik

- Stochastik

- Unsortiertes

- Anbieterkennzeichnung

Wälder in der Graphentheorie

Als Wald bezeichnet man in der Graphentheorie einen ungerichteten Graphen ohne Kreis. Ist dieser zusammenhängend, so spricht man von einem (ungerichteten) Baum. Die Zusammenhangskomponenten eines Waldes stellen in diesem Sinne für sich einen Baum dar, so dass ein Wald aus einem oder mehreren Bäumen besteht.

Jeder ungerichtete Baum ist also auch ein Wald. Betrachtungen über Wälder lassen sich damit auch auf ungerichtete Bäume übertragen. Umgekehrt sind aber auch Betrachtungen über ungerichtete Bäume häufig leicht auf Wälder übertragbar.

Neben ungerichteten Bäumen betrachtet man auch gerichtete Bäume, die häufig auch als gewurzelte Bäume bezeichnet werden und sich weiter in In-Trees und Out-Trees' unterscheiden lassen. Die Struktur entspricht im wesentlichen der von ungerichteten Bäumen, jedoch gibt es einen ausgezeichneten Knoten, den man Wurzel nennt und für den die Eigenschaft gilt, dass alle Kanten von diesem wegzeigen (Out-Tree) oder zu diesem hinzeigen (In-Tree).

Algorithmen auf Wäldern

Aufgrund ihrer einfachen Struktur kann die Komplexität von auf Bäumen arbeitenden Algorithmen meist gut abgeschätzt werden. Oft arbeiten die Algorithmen mit einem Baum als Datenstruktur schneller als andere Algorithmen für dasselbe Problem. Beispielsweise ist für das Problem Sortieren das auf Bäumen arbeitende Heapsort schneller als ein eher naives Insertionsort.

Sonderrolle innerhalb der Graphentheorie

Um alle Knoten eines Graphen effizient betrachten zu können, werden aus den bereits erwähnten Gründen gerne Bäume bzw. Wälder aus dem Graphen konstruiert. Dazu eignen sich Verfahren wie Breitensuche oder Tiefensuche auf den Graphen anzuwenden. Das Ergebnis ist ein Spannbaum. Ein minimaler Spannbaum wird unter gesonderter Betrachtung der Kantengewichte konstruiert, wie es durch den Algorithmus von Kruskal oder den Algorithmus von Prim geschieht. Dies dient bspw. als Grundlage für Algorithmen zum Problem des Handlungsreisenden.

Wichtige Aussagen und Sätze

• Wälder und Bäume sind bipartit.
• Wälder und Bäume sind planar.
• Wälder und Bäume können topologisch sortiert werden.
• Ein Graph ist genau dann zusammenhängend, wenn er einen Spannbaum enthält.

Siehe auch

• Baum
• Dendrogramm

Das entscheidende Kriterium ist Schönheit; für häßliche Mathematik ist auf dieser Welt kein beständiger Platz.

Godfrey Harold Hardy

Druckansicht     

Amazon.de empfiehlt:

Graphentheorie: Eine anwendungsorientierte Einführung

Peter Tittmann

Graphentheorie

Reinhard Diestel

Diskrete Strukturen 1. Kombinatorik, Graphentheorie, Algebra

Angelika Steger

Graphen für Einsteiger: Rund um das Haus vom Nikolaus

Manfred Nitzsche

Algorithmische Graphentheorie

Volker Turau

Diskrete Mathematik: Eine Entdeckungsreise

Jiri Matousek

Bücher zum Thema Graphentheorie auf
• bol.de
• buch.de
• buecher.de
• libri.de