Block 1
Inhaltsverzeichnis
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.
- Dies ist ein gerichteter Graph mit 6 Knoten. Die Kanten überschneiden sich nicht, somit ist er planar, allerdings unvollständig.
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)
Die Anzahl der Kanten eines Graphen ergeben sich bei einem Baum zu:
Ein vollständiger Graph hat
Kanten.
Gozinto-Graph
Ein typisches Beispiel eines gerichteten Graphen ist der Gozinto-Graph. Der Begriff des Gozinto-Graphen stammt vom englischen „that part that goes into“ 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
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
Zwei Besonderheiten:
- Lagerbestand abbauen:
Die Zahl –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:
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 „unten nach oben“ durchgeführt, die Mengenrechnung von „oben nach unten“. 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 Betrachten der Vorlesung.
24.10.2006
Graphentheorie 24.10.2006 (Download)
Graphentheorie 24.10.2006 (Stream)
Graphentheorie 24.10.2006 (scaled Stream)
31.10.2006
Graphentheorie 31.10.2006 (Download)
Graphentheorie 31.10.2006 (Stream)
Graphentheorie 31.10.2006 (scaled Stream)
