Grundbegriffe der Graphentheorie 2
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
Maik Geier,
Anna Bremensztul
== <b><font color="black">Einführung und Wiederholung </font color></b>==
<ul>
<li><font color="green"><b>Die Graphentheorie </b></font color> ist ein Teilgebiet der Mathematik, welche die Eigenschaften von Graphen und ihre Beziehungen zueinander untersucht.<br>
<li><font color="green"> <b>Ein Graph </b></font color> besteht aus einer Menge von Punkten (Knoten,Ecken) zwischen denen Linien(Kanten, Bögen) verlaufen.
<li><font color="green"> <b> Der Grad eines Knotens </b></font color> ist die Summe der Kanten, welche an dem jeweiligen Knoten anliegen.
</ul>
[[Bild:S3anbrem_1.png]]
<br>
<br>
<ul>
<li> <font color="green"> <b> Isomorphie </b></font color> --> Gleichstrukturiertheit von Graphen G∼G′ <br>
</ul>
[[Bild:S3anbrem_1234567890-.png]]
[[Bild:S3anbrem_Graph1.PNG|350px]]
[[Bild:S3anbrem_Graph2.PNG|300px]]
<br>
[[Bild:S3anbrem_Graph3.PNG|490px]]
[[Bild:S3anbrem_Graph4a.PNG|360px]]
<br>
{| class="wikitable"
|-
! !! G1 !! G2 !! G3 !! G4!!
|-
|G1 || <popup>-</popup>|| <popup>ja</popup> || <popup>ja</popup> ||<popup>nein</popup>
|-
|G2 || <popup>ja</popup>|| <popup>-</popup> || <popup>ja</popup>|| <popup> nein </popup>||
|-
|G3 || <popup>ja</popup>|| <popup>ja</popup> || <popup>-</popup> ||<popup>nein</popup>
|-
|G4 || <popup>nein</popup>|| <popup>nein</popup> || <popup>nein</popup> ||<popup>-</popup>||
|}
<ul>
<li> In der Graphentheorie bezeichnet <font color="green"> <b> Weg, Pfad, Kantenzug oder Kantenfolge </b></font color> eine Folge von Knoten, in welcher jeweils zwei aufeinander folgende Knoten durch eine Kante verbunden sind.
</ul>
<b><font color="green">Wo können wir die verschiedenen Graphen nutzen?</font></b>
<i> „In der Mathematik ist die
Kunst des Fragenstellens öfter gebräuchlich als die
des Lösens!“ </i> <br>
<ul>
<li> Verkehrswege zwischen Städten – kürzeste Wege<br>
<li> Transportwege mit Kapazitäten – maximale Flüsse<br>
<li> Zugmöglichkeiten in Spielen – Gewinnstrategien<br>
<li> Beispiele dafür sind auch die Netzwerke(Verkehr, Daten), Datenstrukturen oder Rechnerarchitektur.
</ul>
[[Bild:S3anbrem_Anw.JPG|500px]]
<br>
<b> Wir können verschiedene <font color="green">Darstellungen </font> von Graphen benutzen: </b><br>
1. Darstellung als <b><font color="green">Zeichnung</font></b>:<br>
[[Bild:S3anbrem_Darstellung1.JPG|300px]]
<br>
2. Darstellung als <b> <font color="green"> Adjazenzmatrix </font></b> <br>
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):<br>
[[Bild:S3anbrem_GRAPH_ADJ.PNG|300px]] [[Bild:S3anbrem_Graph_adj2.PNG|300px]]
3. Darstellung als <b><font color="green">Adjazenzliste</font></b>.<br>
Für jeden Knoten wird die Liste seiner Nachbarn
angegeben (Liste von Listen).
<br>[[Bild:S3anbrem_Adj3.JPG|600px]]<br>
Für die Behandlung algorithmischer Probleme sind oft <b>Adjazenzlisten</b> die Datenstruktur
der Wahl, weil sie die wahre Größe eines Graphen (Anzahl der Kanten) widerspiegeln.
<br>
''Die Klassenkameraden haben im vorigen Woche eine Vollständige Graphen vorgestellt und Grundbegriffe der Graphentheorie erklärt.''
Ein Graph heißt <b><font color="green"> vollständig </font></b>, wenn jede Ecke mit jeder anderen durch genau eine Kante verbunden ist.
Das heißt, bei einem vollständigen Graphen sind je zwei Ecken verbunden, aber nur durch eine Kante. Der vollständige Graph mit n Ecken wird mit K_n bezeichnet.<br>
[[Bild:S3anbrem_VollständigerGraph.png]]
<b> Dagegen möchten wir heute andere Typen von Graphen vorstellen.</b> <br>
1. Bipartite Graphen.<br>
2. Gerichtete Graphen und Multigraphen<br>
3. Bewertete Graphen <br>
4. Bäume und Wälder<br>
5. Gozinto-Graphen<br>
<br>
= <b>Bipartite Graphen</b> =
=== Definition ===
<center><b> Ein bipartiter oder paarer Graph ist ein mathematisches Modell für Beziehungen zwischen den Elementen zweier Mengen.</b>
</center>
<center>
</center>
<div style= "background-color:#D6D6C2; padding:10px">
<b>Definition:</b> Ein Graph '''G = (V,E)''' ('''V''' = Menge der Knoten, '''E''' = Menge der Kanten) heißt <b><i>bipartit</i></b>, wenn man seine Knoten so in zwei Teilmengen <font color="red">S</font color> und <font color="blue">T</font color> aufteilen kann, dass folgende Regeln gelten:
<ul>
<li> Die Mengen der Knoten besitzen keine gemeinsamen Elemente (disjunkt) und ergeben zusammen alle Knoten
<li> Kanten verlaufen immer nur von einer Teilmenge zur Anderen.
Zwischen den Knoten, innerhalb der Teilmengen, verlaufen keine Kanten
</ul>
</div>
<center>
[[Bild:S3anbrem_Bip1g.PNG]]
</center>
===<b>Vollständig Bipartit</b><br>===
<div style= "background-color:#D6D6C2; padding:10px">
Der Graph '''G''' heißt <b><i>vollständig bipartit</i></b>, wenn jeder Knoten aus <font color="red">S</font color> mit jedem Knoten aus <font color="blue">T</font color> verbunden ist und somit die Anzahl der Kanten maximal ist.<br>
</div>
<center>
[[Bild:S3anbrem_Vbg.PNG]]<br>
</center>
<br><br>
Der vollständige bipartite Graph '''G''' hat genau <font color="red">S</font color> + <font color="blue">T</font color> Ecken und <font color="red">S</font color> · <font color="blue">T</font color> Kanten<br>
Ein vollständig bipartiter Graph, bei dem <font color="red">S</font color>=1 oder <font color="blue">T</font color>=1 ist, heißt <i><b>Sterngraph </b></i>.<br>
<center>
[[Bild:S3anbrem_Sterngraph.PNG]]
</center>
<br>
== <font color="black">'''n-partiter Graph'''</font color> ==
<div style= "background-color:#D6D6C2; padding:10px">
Ein Graph heißt n-partit wenn er den Regeln der Bipartiten Graphen gehorcht, dessen Knotenmenge jedoch beliebig viele Teilmengen besitzt.
Einen n-partiten Graph mit maximal möglicher Kantenzahl nennt man '''vollständig n-partit'''.
</div>
<center>
[[Bild:S3anbrem_Bip234.PNG]]
</center>
== '''Eigenschaften''' ==
<ul>
<li>Ein Graph ist genau dann bipartit, wenn es <b>keinen</b> aus einer ungeraden Anzahl von Kanten bestehenden geschlossenen Weg gibt. Kanten zwischen
den Elementen einer Teilmenge sind dabei natürlich nicht erlaubt.
<li> Bei einem zusammenhängenden bipartiten Graphen ist die Zerlegung der Menge V = <font color="red">S</font color> + <font color="blue">T</font color> eindeutig bestimmt.
<li> Ist <b>G=(V,E)</b> bipartit mit V = <font color="red">S</font color> + <font color="blue">T</font color> , so gilt:
<ul>
<li>Bei einem aus einer geraden Anzahl von Kanten bestehenden Weg gehören Start- und Endpunkt zur selben Menge <font color="red">S</font color> oder <font color="blue">T</font color>.
<li>Bei einem aus einer ungeraden Anzahl von Kanten bestehenden Weg gehören Start- und Endpunkt zu verschiedenen Mengen.
</ul>
<li>In einem bipartiten Graphen sind keine Kreise ungerader Länge möglich.
</ul>
== '''Ein Baum,als bipartiter Graph gezeichnet.''' ==
<center>
[[Bild:S3anbrem_S3anbrem_Bg1.png|500px]]
</center>
== <b><font color="black">Konstruktion einer Zerlegung von V in <font color="red">S</font color> und <font color="blue">T</font color></font color></b><br> ==
Sei <b>G = (V,E)</b> ein zusammenhängender Graph, welcher eine disjunkte Zerlegung der Knotenmenge V in die Teilmengen <font color="red">S</font color> und <font color="blue">T</font color> erhalten soll.
Gelingt dies, so ist der Graph bipartit.
Ein möglicher Algorithmus zur Zerlegung sieht wie folgt aus:
# Markiere einen (beliebigen) Startknoten mit <font color="red">s</font color>.<br>
# Markiere alle unmarkierten Knoten, die einen mit <font color="red">s</font color> markierten Nachbarknoten haben mit <font color="blue">t</font color>.<br>
# Markiere alle unmarkierten Knoten, die einen mit <font color="blue">t</font color> markierten Nachbarknoten haben mit <font color="red">a</font color>.<br>
# Wiederhole Schritt 2 und 3 so lange, bis entweder<br>
<ul>
<li> alle Knoten markiert sind oder <br>
<li> zwei benachbarte Knoten die gleiche Markierung haben. In diesem Fall ist der Graph nicht bipartit und der Algorithmus kann abgebrochen werden.
</ul>
Im günstigstem Fall erreicht man bei der Umsetzung dieses Algorithmus einen <b>linearen Aufwand</b> von <b> $\mathcal{O}(V+E)$ </b>
<br>
<br>
==''' Beispiel zu Bipartität''' ==
<br>
In einem Dorf gibt es drei Häuser und drei Brunnen. Jedes der Häuser soll nun mit jedem der
Brunnen durch einen Weg verbunden werden. Modelliert man dieses Problem mithilfe eines Graphen.<br>
<center>
[[Bild:S3anbrem_Bip2.jpg]]
</center>
<ul>
<li> Dieser Graph kommt auch als sogenannter <b> GEW-Graph</b> vor. Dieser Name basiert auf einer äquivalenten Realisierung des Problems mit drei Häusern und Werken für Gas, Elektrizität und Wasser.
<li>
Die Menge der 6 Knoten lässt sich in 2 Teilmengen einteilen: die Häuser und die Brunnen. Dazwischen werden Kanten gezeichnet, aber innerhalb der Teilmengen finden sich keine Kanten: Kein Haus soll etwa mit einem anderen verbundenwerden.
</ul>
<br>
== <font color="green">Anwendung</font color> ==
Biparität eignet sich sehr gut zur Modellierung und zur Untersuchung von Zuordnungs- sowie Optimierungsproblemen. Des Weiteren lassen sich besonders für bipartite Graphen, aufgrund der bekannten Eigenschaften, viele Grapheneigenschaften mit deutlich weniger Aufwand berechnen als dies im allgemeinen Fall möglich ist.<br>
<ul>
<li>In der Informatik finden <b>Bipartite Graphen</b> besonders zur Modellierung Anwendung.<br>
z.B. in den <b>Endlichen Automaten</b>, in welchen eine Biparität zwischen den Terminalen/Nichtterinalen und den Zuständen herrscht.<br>
<li>Auch <b>n-partite Graphen</b> finden in der Modellierung anwendung.<br>
z.B. können in <b>Neuronalen Netzen</b> mehrere Schichten gebildet werden, welche eingehende Reize intern bekannten Mustern zuordnen und daraus wiederum eine reaktion
generieren. Diese Schichten bilden somit Teilmengen der Gesamtmenge Neuronen(Knoten).
</ul>
== <font color="green">Matchings</font color> ==
<div style= "background-color:#D6D6C2; padding:10px">
<b>Definition: </b> Sei der Graph <b>G = (V,E)</b> bipartit mit V = <font color="red">S</font color> + <font color="blue">T</font color>. Eine Teilmenge <b>M</b>, der Kantenmenge <b>E</b>, nennt man ein Matching(oder Paarung), wenn jeder Knoten zu maximal einer Kante aus <b>M</b> inzident ist.<br>
Ein Matching heißt maximal, wenn es kein anderes Matching gibt, welches mehr Kanten enthält.
Eine vollständige Paarung ist ein maximales Matching <b>M</b> und defniert eine bijektive Abbildung (1:1-Zuordnung) von <font color="red">S</font color> auf <font color="blue">T</font color>, sodass jeder Knoten mit einer Kante aus <b>M</b> inzident ist. Nur möglich wenn |<font color="red">S</font color>|==|<font color="blue">T</font color>|.
</div>
<popup name="Beispiel">
<center>
[[Bild:S3anbrem_Qw.PNG]]
</center>
</popup>
<b><font color="green"> Anwendungsbeispiel </font color></b><br>
Männer und Frauen nehmen an einem Tanzkurs teil. Es sollen möglichst viele Paarungen gebildet
werden, jedoch keine bei denen sich Mann und Frau nicht mögen. Wieviele Paarungen kann
man maximal bilden?
{| class="wikitable"
|-
! !! Beziehungsgraph !! Antwort !!
|-
| || <popup>[[Bild:S3anbrem_12345617890.JPG]]</popup> || <popup>Jeder kann einen Tanzpartner bekommen.<br> 4 Paarungen sind möglich</popup> ||
|}
In dem gezeigten Beispiel war die richtige Antwort durch bloßes hinsehen ersichtlich.
Hat man jedoch Graphen mit hunderten von Knoten, so benötigt man entweder sehr viel Zeit oder einen Computer, welcher die Aufgabe mit einem Algorithmus löst.<br>
So kann man die maximale Paarung beispielsweise bestimmen, indem man den maximalen Fluss berechnen lässt.
¨
Dazu muss der Graph folgendermaßen transformiert werden:
<ul>
<li> Füge eine Quelle hinzu und verbinde alle Knoten der ersten Teilmengeenge durch eine gerichtete Kante mit der Quelle<br>
<li> Fuge eine Senke hinzu und verbinde alle Knoten der zweiten Teilmengeenge durch eine gerichtete Kante mit der Senke <br>
<li> Ersetze die ungerichteten Kanten zwischen den beiden Mengen durch gerichtete Kanten <br>
<li> Weise jeder Kante das Gewicht 1 zu <br>
</ul>
Berechnet man auf diesem Graphen den maximalen Fluss, also den Maximalbetrag welcher in der Senke ankommen kann,
erhält man das maximale bipartite Matching. Dies funktioniert da alle Kanten den selben Wert besitzen und somit der maximale Fluss der maximalen Anzahl von Kanten entspricht.
<br>
[[Bild:S3anbrem_12.JPG]]
<br>
== '''Übung''' ==
[[1.]] Ist diese Graph bipartite?
[[Bild:S3anbrem_Bn.png]]
<popup name="*">
Nein.
</popup>
[[Bild:S3anbrem_Bj.png]]
<popup name="*">
Ja, weil wir mit diese Graph zeigen können :
[[Bild:S3anbrem_Bj2.JPG]]
</popup>
<br>
<br>
[[2.]] Fünf Jugendliche treffen sich zu einem gemeinsamen Frühstück. Jeder bringt etwas mit. Dazu wird eine Liste angelegt:<br>
<b> Steffi </b> Brötchen , Tee <br>
<b> Niko </b> Butter, Marmelade <br>
<b> Robert </b> Marmelade, Saft <br>
<b> Anja </b> Milch,Tee <br>
<b> Lars </b> Käse ,Brötchen <br>
<b> ? </b> Kaffe <br>
<br>
Man kann statt der Liste auch einen Graphen zeichen: <br>
<popup name="*">
[[Bild:S3anbrem_123.PNG]]
</popup>
<br>
Ist diese Graph bipartit?
<popup name="*">
In unserem Beispiel gibt es keine Kanten zwischen den Leuten und keine Kanten zwischen den Lebensmitteln, also ist der Graph bipartit.
</popup>
<br>
Der Vorteil des Graphen ist, dass man ihn in zwei Richtungen lesen kann: Man sieht nicht nur, was die einzelnen Personen mitbringen, sondern man sieht auch auf einem Blick, wer eine bestimmte Speise mitbringt.
<br>Der Graph enthält zwei Sorten von Ecken: Leute und Lebensmittel. Und Kanten gibt es nur zwischen Leuten und Lebensmittel.
=<font color="green"><u>Gerichtete Graphen und Multigraphen</u></font color>=
Einige Praxisanwendungen erfordern eine Erweiterung des bisherigen Graphenbegriffs, und
zwar in zweierlei Hinsicht, nämlich den Kanten eine Richtung zu geben und Mehrfachkanten
zuzulassen.
<h2><font color="green">Gerichteter Graph</font color></h2>
<p>
<div style= "background-color:#D6D6C2; padding:10px">
<b>Definition:</b>
Ein Graph <b>G = (V,E)</b> heißt gerichtet (auch: Digraph, von engl.: directed graph), falls seine
Kanten zusätzlich eine Orientierung erhalten. Diese orientierten Kanten nennen wir dann
auch Pfeile.<br>
Die Richtung einer Kante in einem gerichteten Graphen wird in der Notation durch die Reihenfolge der Knotenangaben ersichtlich.<br>
Eine Kante <b>e(u, v)</b> verläuft gerichtet von u nach v.
</div>
</p>
Das Einführen der Graphenrichtung hat nun zur Konsequenz, dass, wenn ein Weg in beide Richtungen möglich sein soll,
eine einzelne Kante nichtmehr ausreicht.
<p>
<h2><font color="green">Multigraph</font color></h2>
<div style= "background-color:#D6D6C2; padding:10px">
<b>Definition:</b>
Ein (gerichteter oder ungerichteter) Graph <b>G = (V,E)</b> heißt Multigraph, falls er mehrfache
Kanten (d. h. verschiedene Kanten mit den gleichen Knoten) erlaubt, sowie auch solche
Kanten, die einen Knoten mit sich selber verbinden (sogenannte Schleifen oder Schlingen).<br>
Zwei Kanten <b>a, b</b> mit <b>a = (u, v)</b> und <b>b = (u, v)</b> heißen parallel;<br>
zwei Kanten <b>a, b</b> mit <b>a = (u, v)</b> und <b>b = (v, u)</b> heißen invers.
</div>
</p>
<h1><font color="green">Bewertete Graphen</font color></h1>
<p>
<div style= "background-color:#D6D6C2; padding:10px">
<b>Definition:</b>
Eine Knotenmarkierung eines Graphen <b>G =(V, E)</b> ist eine Abbildung <b>b:V->M</b>
die jedem Knoten <b>v</b> einen Wert oder ein Symbol zuordnet.
</div>
</p>
<p>
<div style= "background-color:#D6D6C2; padding:10px">
<b>Definition:</b>
Eine Kantenmarkierung eines Graphen <b>G =(V, E)</b> ist eine
Abbildung <b>b:E->M</b> die jeder Kante e einen Wert oder ein Symbol zuordnet.
Für die Bewertung der Kante <b>{u, v}</b> schreiben wir dann kurz <b>b(u, v)</b>.
</div>
</p>
<h2><font color="green">Anwendungen</font color></h2>
Gerichtete Graphen ergeben sich in natürlicher Weise aus vielen Anwendungsproblemen:
<ul>
<li><b>Routenplanung</b></li>
<ul>
<li>Bei <b>Straßennetzwerken</b> enstehen gerichtete Graphen, sobald es Einbahnstraßen gibt.</li><br>
<li>Verwendet man Gewichte, um die erwarteten <b>Fahrzeiten/Strecke</b> entlang einer Straße zu kodieren, gibt es Asymmetrien z.B. dann, wenn Straßen in einer Richtung bergab, in der anderen bergauf befahren werden. Hier existieren zwar Kanten in beiden Richtungen, sie haben aber unterschiedliche Gewichte.<br></li>
</ul><br>
<li><b>zeitliche oder kausale Abhängigkeiten</b></li>
<ul>
<li>Wenn die Knoten <b>Ereignisse</b> repräsentieren, von denen einige die Ursache von anderen sind, diese wiederum die Ursache der nächsten usw., verbindet man die Knoten zweckmäßig durch gerichtete Kanten, die die <b>Kausalitätsbeziehungen</b> kodieren. Handelt es sich um logische "wenn-dann"-Regeln, erhält man einen Implikationengraph. Handelt es sich hingegen um <b>Wahrscheinlichkeitsaussagen</b>, erhält man ein Bayessches Netz.</li><br>
<li>Wenn bestimmte Aufgaben erst begonnen werden können, nachdem andere Aufgaben erledigt sind, erhält man einen <b>Abhängigkeitsgraphen</b>.</li><br>
</ul><br>
<li><b>Sequence Alignment</b></li>
<ul>
<li>Eine gute Rechtschreibprüfung markiert nicht nur fehlerhafte Wörter, sondern macht auch plausible Vorschläge, was eigentlich gemeint gewesen sein könnte. Dazu muss sie das gegebene Wort mit den Wörtern eines Wörterbuchs <b>vergleichen</b> und die <b>Ähnlichkeit</b> bewerten. Ein analoges Problem ergibt sich, wenn man DNA Fragmente mit der Information in einer Genomdatenbank abgleichen will.</li><br>
</ul><br>
</ul>
<h1><font color="green">Beispiele</font color></h1>
<p>
Wir betrachten den ungerichteten Graphen G im folgenden Bild. Man kann die Bewertungen
seiner Kanten beispielsweise als <b>Entfernungen</b> zwischen durch die Knoten gegebenen
Orten auffassen – oder als <b>Kosten</b>, um ein gewisses Gut entlang der entsprechenden
Kante zu transportieren.<br>
Für den <b>Weg(123)</b> auf <b>G</b> gilt dann:
<b>l(123)= 2+9 = 11</b>. <br>
Für den <b>Weg(54236)</b> auf <b>G</b> ergibt sich entsprechend
<b>l(54236)= b(5,4)+b(4,2)+b(2,3)+b(3,6)= 1+5+9+1= 16</b>. <br>
</p>
{| class="wikitable"
|-
! !! Graph-G !! Entfernungs-Matrix !!
|-
| || <popup>[[Datei:Unger1.PNG]]</popup>|| <popup>[[Datei:Matrunger.PNG]]</popup> ||
|}
<p>
Schwierigkeiten können sich beispielsweise ergeben,
wenn die Kanten zusätzlich gerichtet sind: Betrachten wir etwa den gerichteten Graphen <b>G'</b>, so könnte man hier analog zum
ungerichteten Graphen die Länge:<br>
<b>l(123)= 2+9= 11 </b><br>
berechnen, da dieserWeg über die Pfeile tatsächlich durchlaufen werden kann. Hingegen gibt
es den <b>Weg(54236)</b> in dem Graphen <b>G'</b> nicht.
</p>
{| class="wikitable"
|-
! !! Graph-G' !! Entfernungs-Matrix !!
|-
| || <popup>[[Datei:Gerichtet1.PNG]]</popup>|| <popup>[[Datei:Matrger.PNG]]</popup> ||
|}
<h2><font color="green">Gozinto-Graphen</font color></h2>
<p>
Der <b>Gozintograph</b> ein Graph, der in der <b>Fertigungsplanung zur Produkt- und Teilbedarfsrechnung</b> sowie als Vorstufe zur Fertigungstermin- und Maschinenbelegungsplanung dient.
Vazsonyi prägte den Begriff scherzhaft, indem er die Vorgehensweise auf den (nicht existierenden) italienischen Mathematiker Gozinto zurückführte,
dessen Name für „the part that goes into” steht.<br>
</p>
<p>
Für jedes Erzeugnis der industriellen Produktion lässt sich angeben,
aus welchen <b>Baugruppen</b> und <b>Einzelteilen</b> es besteht und wie viele Mengeneinheiten davon benötigt werden,
um eine Einheit des Erzeugnisses zu produzieren.<br>
</p>
<p>
Angenommen wir haben einen Endprodukt <b>P5</b>, welches selber aus den beiden Baugruppen <b>B4</b> und <b>E1</b>.
Baugruppe <b>B4</b> besteht aus den Teilen <b>T1</b> und <b>T2</b>. Wir haben nun eine Bestellung
über <b>100 P5</b> und <b>20 B4</b> erhalten und rechnen uns nun mit Hilfe des Gozinto-Graphens den Bedarf an Teilen aus.
Die Struktur der Produktion sieht im Gozinto-Graphen
dann so aus:
</p>
{| class="wikitable"
|-
! !! Gozinto-Graph !! Produktionsebenen/Primärbedarf !!
|-
| || <popup><b>Die Werte a den Kanten stehen für den jeweiligen Bedarf zur Herstellung.</b>[[Datei:Basch_Gozintograph.PNG]]</popup>|| <popup>[[Datei:Basch_Gozlist.PNG]]</popup> ||
|}
<b>Herangehensweise:</b>
--> 1.Direktbedarfsmatrix (Knoten x Knoten) aufstellen
--> 2.Direktbedarfsmatrix von Einheitsmatrix subtrahieren
--> 3.Matrix Invertieren
--> 4.Inverse mit Primärbedarfsvektor multiplizieren
</p>
{| class="wikitable"
|-
! !! Schritt 1 & 2 !! Schritt 3 !! Schritt 4 !!
|-
| || <popup>[[Datei:Basch_Gozmatr2.PNG]]</popup>|| <popup>[[Datei:Basch_Gozmatr3.PNG]]</popup> || <popup>[[Datei:Basch_Gozmatr4.PNG]]</popup> ||
|}
= Bäume und Wälder =
<ul>
<li>Eine fuer Anwendungen sehr wichtige Klasse von Graphen sind Bäume.
<li>In vielen Gebieten wie, z.B '''beim Compilerbau''' oder ''bei Datenbanksystem'' werden sie haeuftig zur Darstellung von hierarchischen Beziehungen verwendet.
<li>In diesem Teil werden Anwendungen auf Bäumen besierender '''Sortieralgorithmus''' vorgestellt und eine effiziente Realisierung von Vorrang-Warteschlangen diskutiert.
<li>Ferner werden zwei Algorithmen zur Bestimmung von ''minimalen aufspannenden Bäumen'' und ein Verfahren zur Datenkompression beschreiben.
</ul>
<br>
[[Bild:S3anbrem_Baum2.jpeg]][[Bild:S3anbrem_Baum2.jpeg]][[Bild:S3anbrem_Baum2.jpeg]][[Bild:S3anbrem_Baum2.jpeg]][[Bild:S3anbrem_Baum2.jpeg]][[Bild:S3anbrem_Baum2.jpeg]]<br>
== Definition ==
<ul><li>'''Ein Baum''' B ist ein zusammenhängender Graph ohne Kreis. Einen nicht zusammenhängenden Graphen , dessen Zusammenhangskomponenten Bäume sind, nennt man einen''' Wald'''.<br>
<li>Ein Knoten v e V(B) mit d(v) = 1 heißt '''Blatt'''.<br>
<li>Gibt es bei einem gerichteten Baum B einen ausgezeichneten Knoten , von dem aus sämtliche anderen Knoten von B erreichbar sind und der sinerseits von keinem anderen Knoten aus erreicht werden kann. Man nennt diesen Knoten '''die Wurzel''' von B und spricht in diesem Fall von einem''' gewurzelten Baum.'''
</ul><br>
[[Bild:S3anbrem_Baaumabbau.JPG]]
== Beispiele ==
<ul>
<li>Die Abbildung zeigt drei Bäume, die zusammen einen <b>Wald</b> bilden. Also einen (ungerichteten) Graph, dessen Zusammenhangskomponenten Bäume sind, wird ein Wald genannt, d.h. jeder kreisfreie Graph ist ein Wald.<br><br>
<li>Die folgende Abbildung zeigt einen aus vier Bäumen bestehen Wald.<br>
[[Bild:S3anbrem_B1b.JPG]]
<br>
<li>Bäume mit drei Knoten: ein ungerichteter, drei gerichtete.<br>
[[Bild:S3anbrem_B1a.JPG]]
<br>
<li>Die folgende Abbildung zeigt die Liste aller Bäume mit 6 Knoten.<br>
[[Bild:S3anbrem_B2a.JPG]]
</ul>
== Charakterisierung von Bäumen ==
<b>Satz</b>: Sei G = (V, E) ein Graph, dann sind die folgenden drei Bedingungen aquivalent:
<br>
<ol>
<li> G ist ein Baum.<br>
<li> Je zwei Ecken von G sind durch genau einen Weg verbunden.<br>
<li>G ist zusammenhängend und |E| = |V| − 1
</ol>
== Anwendung ==
<ul>
<li>Für den Informatiker sind Bäume ein sehr wichtiges Werkzeug.
<li> Dabei stellt die Tatsache, dass sich eine Reihe praktischer Problemstellungen auf die Konstruktion von aufspannenden Bäumen (bzw. Wäldern)zurückführen lassen, nur einen Teilaspekt des gesamten Anwendungsspektrums dar.
<li>In der theoretischen Informatik dienen
sogenannte <b>Entscheidungsbäume</b> als Modell für Berechnungen.
<li> Schließlich spielen
Bäume als Datenstruktur für Such- und Sortierprozesse eine wichtige Rolle<br>
</ul>
<br>
[[Bild:S3anbrem_Bauum.JPG]]
== Eigenschaften ==
<ul>
<li>Jeder Baum mit Knotenanzahl n > 1 hat mindestens zwei Knoten vom Grad 1 (Blätter).
Jeder Baum mit Knotenanzahl n hat Kantenanzahl
n − 1.
<li> Jeder kreislose Graph mit Knotenanzahl n und Kantenanzahl n − 1 ist ein Baum
<li>Sind u, v zwei verschiedene Knoten in einem Baum T, dann gibt es in T genau einen Weg mit den Endpunkten u und v
</ul><br>
==Aufspannender Baum und Wald ==
<ul>
<li> Definition: Sei G = (V, E) ungerichtet und zusammenhängend mit |V| = n.
Ein Untergraph T auf allen n Knoten, der ein Baum ist, heißt '''aufspannender Baum''' von G.
<li> Analog definiert man einen '''aufspannenden Wald''' als Vereinigung von aufspannenden Bäumen von allen Zusammenhangskomponenten eines nichtzusammenhängenden Graphen.
</ul>
== Anzahl ungerichteter Bäume mit n Knoten==
<ul>
<li>Bäume mit zwei bzw. drei Knoten gibt es ganz sicher jeweils nur einen, wie man sich schnell klar macht. <br>
<li>Bäume mit vier Knoten gibt es imWesentlichen zwei, Bäume mit fünf Knoten drei verschiedene. <br>
<li>Für die Anzahl der ungerichteten Bäume mit n Knoten gibt es leider definitiv keine einfache Formel; in Tabelle sind die ersten Anzahlen aufgelistet:
</ul>
[[Bild:S3anbrem_Baumanzahl.JPG]]
== '''Binärbaum'''==
'''Ein Binärbaum''' B ist ein gerichteter (und damit gewurzelter) Baum, bei dem jeder Knoten maximal zwei Nachfolger hat. Ein Binärbaum heißt geordnet, falls jeder innere Knoten einen linken und eventuell einen rechten Nachfolger besitzt (linker Nachfolger muss, rechter
Nachfolger kann). Man bezeichnet einen Binärbaum als voll, wenn jeder Knoten, der kein Blatt ist, genau zwei Nachfolger hat. Ein voller Binärbaum heißt vollständig, wenn alle Blätter die gleiche Tiefe haben.
<br>
[[Bild:S3anbrem_Bina.JPG]]
== '''Termbaum''' ==
'''Ein Termbaum''' dient dazu, einen Rechenterm wie z. B. (x+3)*(2x-5) strukturell zu repräsentieren.<br>
[[Bild:S3anbrem_Term.JPG]]<br>
Ziel: Entwicklung eines Programms zur Verarbeitung von Term(bäum)en.
== Aufbau Bäume ==
'''Bäume Pfad:''' alle Knoten von einem Knoten k_1 zu einem Knoten k_2 (z. B. 6--> 2--> 8)<br>
'''Pfadlänge:''' Anzahl der Knoten von einem Knoten k_1 zu einem Knoten k_2<br>
'''Tiefe des Baumes:''' das Maximum aller Pfadlängen von der Wurzel zu einem Blatt <br>
'''Tiefe eines Knotens:''' Pfadlänge von der Wurzel zu diesem Knoten <br>
'''Unterbaum:''' beliebiger Knoten k mit allen Nachfolgern, k als Wurzel Pfad
Unterbaum<br>
[[Bild:S3anbrem_Ub.JPG]]
== UBUNG ==
1. Ist diese Graph einen Baum?
<br>
[[Bild:S3anbrem_BU.png]]<br>
<popup name="*">
Nein, kein Baum wegen Zyklus OAB.
</popup>
<br>
[[Bild:S3anbrem_BU2.png]]<br>
<popup name="*">
Nein,da nicht verbunden
</popup>
[[Bild:S3anbrem_Baum.png]]
<br>
<popup name="*">
Ja ;)
</popup>
= <b><font color="green"> Zusammenfassung </font color></b> =
Ein '''Graph''' besteht aus einer Menge von '''Knoten''' und '''Kanten'''. Die '''Knoten''' tragen Namen und sind durch die '''Kanten''' verbunden.
<br>
[[Bild:S3anbrem_G1.JPG]]<br>
Kann jede Kante eines Graphen in genau einer Richtung durchlaufen werden, so ist der Graph '''gerichtet'''.<br>
[[Bild:S3anbrem_G2.JPG]]<br>
Ist jeder Kante eines Graphen ein Wert zugewiesen, so ist der Graph '''gewichtet'''. <br>
[[Bild:S3anbrem_G3.JPG]]<br>
<b> Baum </b>
[[Bild:S3anbrem_Baumabbau.JPG]]
<b> Multigraph:</b> Es kann mehr als eine Kante zwischen denselben Knoten geben.<br>
Existiert für mind. ein Paar (x,y) kein Paar (y,x),so nennt man den Graphen <b>gerichtet</b>.<br>
Bei einem <b> bewerteten Graphen</b> ist jeder Kante ein Wert
zugeordnet. <br>
Existiert für jedes Paar (x,y) auch ein Paar (y,x), so nennt man den Graphen<b> ungerichtet.</b><br>
Ein (ungerichteter) Graph ist ein <b>Baum</b>, wenn er zusammenhängend ist und keinen Kreis enthält.<br>
= <b><font color="green"> Bibliografie </font color></b> =
André Krischke, Helge Röpcke - Graphen und Netzwerktheorie <br>
Volker Turau, Algorithmische Graphentheorie
<br>
http://www.uni-protokolle.de/Lexikon/Typen_von_Graphen_in_der_Graphentheorie.html#Wichtige_spezielle_Graphen <br>
https://de.wikipedia.org/wiki/Graphentheorie <br>
http://www2.cs.uni-paderborn.de/cs/ag-klbue/de/courses/ws09/model/folien/kb-graphen.pdf <br>
http://wvsg.schulen2.regensburg.de/joomla/images/Faecher/Informatik/Informatik_11/informatik_11_3_1_Einfache%20Graphen.html<br>
http://www14.in.tum.de/lehre/2010WS/ds/2011-02-01.pdf<br>
https://www2.informatik.hu-berlin.de/alkox/lehre/lvss03/ti03/vl1507.pdf
http://www.stefan-enderle.de/SS08/GrundlagenDerInformatik-II-3-Graphen.pdf
http://mathworld.wolfram.com/BipartiteGraph.html