Quelltext der Seite Block 1

==Grundlagen zur Graphentheorie==

===Begriffserklärungen===
Ein '''Graph''' ist ein Netzwerk aus Knoten und verbindenden Strecken, den so genannten Kanten.
Die '''Knoten''' (Kreise) stellen Orte, Bauteile oder Aktivitäten dar. Die '''Kanten''' (Linien) verbinden die Knoten untereinander und beschreiben die Entfernungen, die zeitlichen Abstände, oder auch die Stückzahlen.

Kann ein Graph nur in einer Richtung durchlaufen werden, so spricht man von einem '''gerichteten''' Graphen. Die Kanten werden in diesem Fall als Pfeile dargestellt.
'''Vollständige''' Graphen zeichnen sich dadurch aus, dass alle Knoten direkt miteinander verbunden sind, andernfalls spricht man von unvollständigen Graphen.
Ein '''planarer''' Graph ist dadurch gekennzeichnet, dass sich alle Kanten überschneidungsfrei zeichnen lassen. Somit kann z.b. ein vollständiger Graph mit mehr als 4 Knoten niemals planar sein. Er wird als nichtplanar bezeichnet.
Des Weiteren wird ein Graph als '''Baum''' bezeichnet, wenn jeder Knoten des Graphen von jedem anderen aus über genau einen Weg zu erreichen ist.


===Beispiele===
*	Dies ist ein vollständiger Graph mit 5 Knoten. Jeder Knoten ist direkt mit allen anderen Knoten verbunden. Da sich die Kanten überschneiden ist er nichtplanar.

<center>http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/grafik/Graph1.jpg</center>
<center>''Abb. 1''</center>

*       Dies ist ein gerichteter Graph mit 6 Knoten. Die Kanten überschneiden sich nicht, somit ist er planar, allerdings unvollständig.

<center>http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/grafik/Graph2.jpg</center>
<center>''Abb. 2''</center>

===Teile eines Graphen===
Graphen können wiederum in verschiedene Einzelteile untergliedert werden (vgl. HMM 7.1):
* Kette: Der Graph ist ungerichtet und linear angeordnet (siehe Abbildung 3.1)
* Pfad: Der Graph ist gerichtet und linear angeordnet (siehe Abbildung 3.2)
* Masche: (siehe Abbildung 3.3)
* Schleife: (siehe Abbildung 3.4)

<center>http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/grafik/GraphenVersch.jpg</center>
<center>''Abb. 3''</center>

Die Anzahl der Kanten eines Graphen ergeben sich bei einem Baum zu:
<br><center>'''m = n-1'''   , mit n = Anzahl der Knoten</center>

Ein vollständiger Graph hat 
<center>'''m = n*(n-1) / 2''' </center> 

Kanten.

===Gozinto-Graph===
Ein typisches Beispiel eines gerichteten Graphen ist der Gozinto-Graph. Der Begriff des Gozinto-Graphen stammt vom englischen &#8222;that part that goes into&#8220; ab. Mit seiner Hilfe werden vor allem in der Produktionstheorie mehrstufige Produktionsprozesse vereinfacht abgebildet. Anhand des Graphen kann später auch eine Stückliste erstellt werden.
Die zwei wichtigsten Anwendungen sind in der Mengen- und Kostenrechnung zu sehen. Die Anwendung werden wir am folgenden Beispiel genauer erklären:

====Mengenrechnung mit Hilfe des Gozinto-Graphen====
Im ersten Beispiel betrachten wir die Mengenrechnung. Von einem Produkt A wollen wir 20 

<center>http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/grafik/GozintoMenge.jpg</center>
<center>''Abb. 4''</center>

Mengeneinheiten produzieren. Als Beispiel wollen wir annehmen das Produkt A (Fertigprodukt) wäre ein Tisch. Um den Tisch produzieren zu können benötigen wir 2 Holzplatten. Diese werden durch den Knoten B dargestellt. Da wir für jeden Tisch 2 Platten brauchen, und insgesamt 20 Tische produzieren wollen, werden nun also 40 Holzplatten gebraucht. Damit wird deutlich: Der Wert des Knotens B ergibt sich aus der Multiplikation der Menge des übergeordneten Knoten A mit der verbindenden Kante. Knoten C stellt in unserem Beispiel die Tischbeine dar. Hiervon werden je Tisch 3 Beine benötigt, insgesamt also 60 Stück. Die Knoten B und C werden als Baugruppen bezeichnet, da sie aus anderen Teilen zusammengesetzt werden, aber auch noch kein Endprodukt sind. Die untersten Knoten stellen die Einzelteile der Produktion dar. Angenommen Knoten D entspricht Schrauben, Knoten E entspricht Holzleim, und Knoten F entspricht Nägeln. Um die 40 benötigten Holzplatten zu produzieren werden je Platte 5 Schrauben, sowie 2 ml Holzleim verwendet. Zur Produktion der Tischbeine benötigt man jeweils eine Schraube, 4 ml Holzleim und 3 Nägel. Dadurch wird klar, dass insgesamt 5 * 40 + 1 * 60 = 260 Schrauben verbraucht werden. Wird ein Produktionsmittel für mehrere Zwischenprodukte benötigt ( Schrauben für Platten und Tischbeine), so werden die verschiedenen Verbräuche am Knoten addiert.

Ein abschließender kurzer Überblick über die Mengenrechnung:
-	von oben nach unten rechnen
-	an den Kanten multiplizieren
-	an den Knoten addieren

<center>http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/grafik/GozintoExtra.jpg</center>
<center>''Abb. 5''</center>


<u>Zwei Besonderheiten:</u>
* Lagerbestand abbauen: 
Die Zahl &#8211;10 in Knoten B besagt, dass 10 Mengeneinheiten bereits im Lager verfügbar sind. Somit müssen nur noch 30 anstatt 40 produziert werden. Dies ist rechnerisch ebenfalls logisch, da sich durch die Addition 40 + (-10) = 30 ergibt.

* Lagerbestand aufbauen / weiteres Primärprodukt:
Am Knoten F ist eine positiv Menge von 20 eingetragen. Dies bedeutet, dass unabhängig von der Produktionsmenge, 20 ME von F mehr benötigt werden. Diese können entweder dadurch entstehen, dass F auch als Primärprodukt direkt verkauft wird, oder dass für eventuell mögliche produktionsbedingte Abweichungen vorab 20 Ersatzteile mehr geordert werden.

====Kostenrechnung mit Hilfe des Gozinto-Graphen====
Als zweites wollen wir auf die Kostenrechnung mit Hilfe des Gozinto-Graphs eingehen:

<center>http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/grafik/GozintoKosten.jpg</center>
<center>''Abb. 6''</center>

Die Kosten für die Einzelteile D,E und F sind bekannt. Daran erkennt man den grundsätzlichen Unterschied zwischen der Mengen- und der Kostenrechnung. Die Kostenrechnung wird von &#8222;unten nach oben&#8220; durchgeführt, die Mengenrechnung von &#8222;oben nach unten&#8220;. Zur Herstellung des Zwischenproduktes B werden nun 5 ME von D und 2 ME von E benötigt. Somit setzt sich der Gesamtpreis für B aus der Summe der Preise der Einzelteile multipliziert mit den benötigten Mengen zusammen. Für das Zwischenprodukt B gilt: 3 ME (D) * 5 GE  +  2 ME (E) * 2 GE = 19 GE . So wird verfahren bis man die Kosten für das Endprodukt berechnet hat.

===Vorlesung===
Sie können Sich zu diesem Themengebiet eine Vorlesung ansehen. 
Bitte beachten Sie die Hinweise zum [[Allgemeine Hinweise zur Vorlesungsaufzeichnung|Betrachten]] der Vorlesung.

====24.10.2006====
[http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/wp/graphentheorie_241006/graphen_241006.zip Graphentheorie 24.10.2006 (Download)]
<br>[http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/wp/graphentheorie_241006/20061024teil3.svg Graphentheorie 24.10.2006 (Stream)]
<br>[http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/wp/graphentheorie_241006/20061024teil3_scale.svg  Graphentheorie 24.10.2006 (scaled Stream)]

====31.10.2006====
[http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/wp/graphentheorie_311006/graphen_311006.zip Graphentheorie 31.10.2006 (Download)]
<br>[http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/wp/graphentheorie_311006/20061031.svg Graphentheorie 31.10.2006 (Stream)]
<br>[http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/wp/graphentheorie_311006/20061031_scale.svg  Graphentheorie 31.10.2006 (scaled Stream)]