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.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 1

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

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 2

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)

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 3

Die Anzahl der Kanten eines Graphen ergeben sich bei einem Baum zu:

m = n-1 , mit n = Anzahl der Knoten

Ein vollständiger Graph hat

m = n*(n-1) / 2

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

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 4

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

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 5

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:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 6

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)

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.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 1

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

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 2

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)

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 3

The number of edges for trees amount to :

m = n-1 , with n = number of nodes

A complete graph has

m = n*(n-1) / 2

edges.

Gozinto-graph

The gozinto-graph is a typical example of a directed graph. The term 'gozinto' originates from the expression „that part that goes into“. 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

For illustration, we consider the following example of quantity calculation. We want to fabricate 20 units of product A.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 4

In this example we suppose procuct A (finished product) to be a table. To produce this table we need 2 wooden boards. These are illustrated by node B. Since we have to use 2 wooden boards per table and we want to fabricate 20 tables,we need a total number of 40 wooden boards. This clearly demonstrates: The value of node B results from the placed over node A's amount multiplied by the connecting edge's value. In our example node C represents table legs. Each table requires 3 table legs, since 20 tables are meant to be produced we need a total number of 60 pieces. Node B and node C are termed as modules, they themselves are made of other components without being the end product. The undermost nodes represent the production's single components. Node D is supposed to correspond screws, node E wood glue and node F nails. To produce the required amount of 40 wooden boards 5 screws and 2ml wood glue are needed per board. Furthermore a screw, 4ml wood glue and 3 nails are required to produce a table leg. By this it becomes clear that a total amount of 5 * 40 + 1 * 60 = 260 screws are consumed. If one means of production is used for producing several intermediate products (screws for producing table legs and wooden boards) the different usages are added at the node.

A concluding summary about quantity calculation: - top down calculation - multiplication at edges - addition at nodes

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 5

Two exceptions:

• Reduction of inventory:

The number -10 in node B means that 10 quantity units are already available in stock. Consequently 30 instead of 40 have to be produced. This is also calculationally logical, since the addition delivers 40 + (-10) = 30.

• Enlargement of inventory/ another primary product:

Node F already has a positive value of 20. This means that always 20 additional quantity units of F are needed independent of the production output. These additional quantity units may be caused by a direct sale of F as primary product. Another reason may be production-based deviations where a number of 20 spare parts are ordered in advance.

Cost accounting with the help of gozinto graphs

Secondly we want to show how to calculate costs by using gozinto graphs.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 6

The costs for the spare parts D,E and F are known. By this example the fundamental difference between cost and quantity calculation is visible. Cost calculation proceeds from „bottom to top“, while quantity calculation is implemented from „ top to bottom“. To produce intermediate product B 5 quantity units of D as well as 2 quantity units of E are required. Consequently the total price of B results from the Addition of the spare part's prices multiplied by the needed amount. Thus we calculate for the intermediate product B: 3QU(D) * 5MU + 2QU (E) * 2MU = 19MU (QU=Quantity Unit, MU= Monetary Unit). This way of calculation is implemented until the costs of the end product are calculated.

Lecture

A video lecture on the topic portrayed above is available.

Graphentheorie (English)
Graphentheorie/Gozintograph (English)