Grundbegriffe der Graphentheorie 2

Maik Geier, Anna Bremensztul

Die Einführung und eine kleine Wiederholung

Die Klassenkameraden haben im vorigen Woche eine Vollständige Graphen vorgestellt und Grundbegriffe der Graphentheorie erklärt.

Dagegen möchten wir heute andere Typen von Graphen vorstellen.
1. Bipartite Graphen.
2. Gerichtete Graphen und Multigraphen
3. Bewertete Graphen
4. Bäume und Wälder
5. Gozinto-Graphen

Aber am Amfang möchten wir sichere Begriffe erklären oder wiederholen.

Was bedeutet die Begriffe Graphentheorie und Graph?

• 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.

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): 1 : 2; 2 : 1, 4, 5; 3 : 4, 5; 4 : 2, 3, 5; 5 : 2, 3, 4; oder mit anderer Syntax (2),(1, 4, 5),(4, 5),(2, 3, 5),(2, 3, 4)

4. Darstellung als Inzidenzmatrix. Darstellung als Inzidenzmatrix. Jedem Knoten wird eine Zeile und jeder Kante eine Spalte zugeordnet und der Eintrag in der Zeile von u und der Spalte von e wird 1 gesetzt, wenn u eine Ecke der Kante e ist (sonst 0):

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.

Bipartite Graphen

Definitionen

Bipartiter Graph
Ein Graph G = (V,E) (V Menge der Knoten, E Menge der Kanten) heißt bipartit, wenn man seine Knoten so in zwei Teilmengen S und T aufteilen kann, das gilt:

• S und T besitzen keine gemeinsames Element (disjunkt) und ergeben zusammen alle Knoten
• Kanten verlaufen immer nur von einer Teilmenge zur Anderen.

  Zwischen den Knoten, innerhalb beider Teilmengen, verlaufen keine Kanten

Vollständig Bipartit
Der Graph G heißt vollständig bipartit, wenn jeder Knoten aus S mit jedem Knoten aus T verbunden ist. Einen solchen Graphen bezeichnet man auch als K{m,n}, wobei m und n jeweils die Anzahl der Knoten von S und T sind. Die Kantenanzahl des vollständigen bipartiten Graphen lässt sich mit folgender Formel berechnen:

Ein vollständig bipartiter Graph, bei dem m=1 oder n=1 ist, heißt Sterngraph.