Grundbegriffe der Graphentheorie 2

Maik Geier, Anna Bremensztul

Ich:
- Die Einführung und eine kleine Wiederholung
- Bipartiter Graph
- Baeume + Waelder

Maik :
-Gerichtete Graphen und Multigraphen
- Bewertete Graphen
- Gozinto-Graphen

Zusammen:
- Zusammenfassung
- Uebung

Die Einführung und eine kleine Wiederholung

• Die Graphentheorie ist ein Teilgebiet der Mathematik, das die Eigenschaften von Graphen und ihre Beziehungen zueinander untersucht.
  
• Ein Graph besteht aus einer Menge von Punkten (Knoten,Ecken) zwischen denen Linien(Kanten, Bögen) verlaufen.
• Der Grad eines Knotens ist die Summe der Kardinalitäten der Mengen von geordneten Paaren, welche in E enthalten sein müssen, die diesen Knoten als erstes oder zweites Paarelement haben.
  

• Isomorphie --> Gleichstrukturiertheit von Graphen G∼G′
• In der Graphentheorie bezeichnet Weg, Pfad, Kantenzug oder Kantenfolge eine Folge von Knoten, in welcher jeweils zwei aufeinander folgende Knoten durch eine Kante verbunden sind.

Wo können wir die verschiedene Graphen benutzen?

„In der Mathematik ist die Kunst des Fragestellens öfter gebräuchlich als die des Lösens!“

• Verkehrswege zwischen Städten – kürzeste Wege
  
• Transportwege mit Kapazitäten – maximale Flüsse
  
• Zugmöglichkeiten in Spielen – Gewinnstrategien
  
• Beispiele dafür sind auch die Netzwerke(Verkehr, Daten), Datenstrukturen oder Rechnerarchitektur.

Wir können verschiedene Darstellungen von Graphen benutzen:
1. Darstellung als Zeichnung:

2. Darstellung als Adjazenzmatrix
Jedem Knoten wird eine Zeile und eine Spalte zugeordnet und der Eintrag in der Zeile von u und der Spalte von v wird 1 gesetzt, wenn {u, v} eine Kante des Graphen ist (sonst 0):

3. Darstellung als Adjazenzliste.
Für jeden Knoten wird die Liste seiner Nachbarn angegeben (Liste von Listen).



Für die Behandlung algorithmischer Probleme sind oft Adjazenzlisten die Datenstruktur der Wahl, weil sie die wahre Größe eines Graphen (Anzahl der Kanten) widerspiegeln.