Grundlagen zur Graphentheorie: Unterschied zwischen den Versionen

Version vom 1. Februar 2014, 02:01 Uhr

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/Lecture

Sie können Sich zu diesem Themengebiet eine Vorlesung ansehen.

Graphentheorie (English)
Graphentheorie/Gozintograph (English)

Grundlagen zur Graphentheorie/ Englische Version (noch nicht korrigiert)

Definitions

A graph is a network composed of nodes (also called vertices) and connections, the so called edges. The nodes (circles) represent places, building components or activities. The edges(lines) connect the nodes and describe distances, as well as chronological distances or number of pieces.

Graphs are called directed graphs, when they are only passable in one direction. In that case edges are illustrated as arrows. Complete graphs are characterized by the circumstance, that all nodes are directly interconnected, otherwise we use the term of incomplete graphs. Planar graphs may be described as graphs in which all edges may be sketched without one overlapping. Consequently for example a complete graph containig more than 4 nodes might never be planar also termed non planar. Furthermore a graph is defined tree, if there is only one path to get from one node to another.

Examples

• The portrayed graph is a complete one containig 5 nodes. Every pair of distinct vertices is connected by a unique edge. Since the edges intersect the graph is non planar.

• The 6-node graph portrayed below is directed. The edges do not intersect therefore the graph is planar but incomplete.

Parts of a graph

Graphs may be subdivided in various components (cf. HMM 7.1):

• chain: The graph is undirected and linearly arranged (see Figure 3.1)
• directed path: A directed path is an oriented graph in a linear arrangement.(see Figure 3.2)
• mesh: (see Figure 3.3)
• loop: (see Figure 3.4)

The number of edges for trees amount to :

A complete graph has

edges.

Gozinto-graph

The gozinto-graph is a typical example of a directed graph. The term 'gozinto' originates from the expression #8222;that part that goes into&#8220. Gozinto-graphs may be especially helpful in production theory for simplified illustrations of multistage production processes. Later it is possible to create a piece list based on the graph. The two most important applications are to be found in quantity calculation and costing, which will be explained in more detail through the following example:

Quantity calculation with the help of gozinto-graphs