Graphentheorie

Hierbei beschreibt, analysiert und optimiert man reale Sachverhalte und Entscheidungsprobleme durch Graphen und zugehörige Methoden (z.B. Dijkstra- oder Kruskal-Algorithmus).

ist die theoretische Grundlegung für die Netzwerktechnik. Die Netzplantechnik ist somit die praktische Auslegung der Graphentheorie. Unabhänig von der amerikanischen Entdeckung der Netzplantechnik für die Planungsaufgaben wurde in Frankreich durch den Mathematiker Roy eine Methode der Netzplantechnik entwickelt, die auf die mathematischen Begriffe der Graphentheorie zurückgreift. Für die praktische Anwendung haben sich allerdings die Methoden der einfachen Netzplantechnik wie z.B. PERT, LESS, CPM usw. durchgesetzt.

Die Theorie der Graphen hat für die betriebliche Planung eine große Bedeutung erlangt. Insbesondere die Netzplantechnik baut auf der Graphentheorie auf.

- Critical Path Method

In der Wirtschaftssoziologie: mathematische Theorie, die in den Sozialwissenschaften zur Darstellung von Strukturen verwendet wird, die aus einer Menge von Elementen (z.B. Personen einer Gruppe oder Organisation) und Relationen (z.B. Sympathie-, Kommunikations- oder Anweisungsbeziehungen) bestehen. Ein Graph als Abbildung einer bestimmten Struktur besteht aus den Elementen oder Knoten (A, B ... N) und den Beziehungen oder Kanten (a, b, ... ri) zwischen den Elementen. Sind die Relationen symmetrisch (z.B. Verwandtschaft), ist der Graph ungerichtet (Fall 1), sind sie asymmetrisch (z.B. Anweisungsbefugnis), so heisst der Graph gerichtet (Fall 2). Neben der Formalisierung von sozialwissenschaftlichen Theorien (z.B. strukturelle Balance) wird die Graphentheorie in einer Reihe von Planungstechniken (z.B. Methode des kritischen Pfades) angewendet.

(Theorie der Netzwerke) Sammelbegriff für verschiedene Modelle und Verfahren der Planungsmathematik des 0perations Research. Besonders häufig angewandt werden die Modelle und Verfahren der Bestimmung von Wegen und der Optimierung von Flüssen in Netzen. Für beide Problemtypen lassen sich auch die Modelle und Verfahren der linearen Optimierung einsetzen; diese erfordern (bei computerunterstützter Bearbeitung) aber einen höheren Speicherbedarf und Rechenaufwand. Graphen (Netzwerke) sind Gebilde aus "Knoten" und sie verbindenden "Kanten". Jede Kante verbindet genau zwei Knoten. Wenn die Kanten eine Richtungsorientierung haben, nennt man sie auch "Pfeile". Ein "zusammenhängender" Graph mit n Knoten enthält zumindest n — 1 Kanten. In ihm ist jeder Knoten mit jedem anderen Knoten direkt oder indirekt verbunden. Zusammenhängende Graphen mit diesem Minimum an Kanten nennt man auch "Bäume" ( Entscheidungsbaumverfahren). In ihnen gibt es zwischen jedem Knotenpaar genau eine einzige Verbindung und keine Parallelwege über "Kreise", "Schleifen" oder "Maschen". Dem Baum als zusammenhängendem Graphen mit minimaler Kantenzahl steht der "vollständige" Graph gegenüber, in dem jeder Knoten mit jedem anderen Knoten genau einmal direkt verbunden ist. Er enthält bei n Knoten n(n — l)/2 Kanten (bzw. als gerichteter Graph n(n — 1) Pfeile). Graphen können z.B. repräsentieren: • Verkehrsnetze (Strassen, Schienen, Wasserstrassen, Flugwege), • Versorgungsnetze (Wasser, Strom, Gas, Fernwärme, Abwasser), • Nachrichtennetze (Telefon, Kabelfernsehen, Computer-Netze), • Organigramme (Organisationspläne aus Unternehmungen und öffentlichen Verwaltungen), • Input-Output-Zusammenhänge (Stücklisten, Gozinto-Graph, Input-Output- Funktionen; Produktionsplanungsmo- delle), • Strukturpläne von Projekten ( Netzplantechnik), • Wechselkursbeziehungen zwischen verschiedenen Währungen ( Devisenarbitrage). Die Modelle und Verfahren zur Bestimmung von Wegen lassen sich - unter geringfügigen Anpassungen an die Problemtypen - für recht unterschiedliche Fragestellungen verwenden, darunter: • Berechnung kürzester (schnellster, kostenminimaler etc.) Wege in gerichteten und ungerichteten Graphen, • Bestimmung der frühesten und spätesten Termine sowie des kritischen Weges in Ter- min-Netzplänen ( Netzplantechnik), • Mengenrechnung und Kostenrechnung in Gozinto-Graphen, • Bestimmung der günstigsten Devisen-Han- dels-Reihenfolge (Devisenarbitrage) zwischen verschiedenen Währungen. Die Verfahren zur Bestimmung von Wegen gliedern sich vor allem in zwei Gruppen: Zur Bestimmung der von einem einzigen vorbestimmten Knoten ausgehenden Wege eignen sich die Verfahren vom Typ Dijkstra und Bellman ( dynamische Optimierung), für die gleichzeitige Bestimmung der Wege zwischen sämtlichen Knoten jene vom Typ Floyd. Der Bestimmung von Wegen steht die Maximierung von Flüssen in Graphen gegenüber. Die entsprechenden Modelle und Verfahren dienen vor allem der Transportplanung in ka- pazitativ begrenzten Netzwerken ( Transportmodelle). Die für Wege und Flüsse in Graphen entwickelten Rechenverfahren sind sehr effizient und erlauben die Behandlung von Graphen mit vielen tausend Knoten. Literatur: Dijkstra, E. W., A Note on Two Problems in Connection with Graphs, in: Numerische Mathematik, l.Jg. (1951), S. 269ff. Even, S., Graph Algorithms, London 1979. Floyd, R. W., Algorithm 97, Shortest Path, in: Communications of the ACM, 5. Jg. (1962), S. 345. Ford, L. R./Ful- kerson, D. R., Flows in Networks, Princeton, N. J. 1962.

Vorhergehender Fachbegriff: Graph, zusammenhängender | Nächster Fachbegriff: Graphical Evaluation and Review Technique (GEBT)

Diesen Artikel der Redaktion als fehlerhaft melden & zur Bearbeitung vormerken

Weitere Begriffe : AKA Ausfuhrkreditgesellschaft mbH | Markenbewusstsein | Amortisationsrechnung, dynamische

Praxisnahe Definitionen

Nutzen Sie die jeweilige Begriffserklärung bei Ihrer täglichen Arbeit. Jede Definition ist wesentlich umfangreicher angelegt als in einem gewöhnlichen Glossar.

Marketing

Definition

Konditionenpolitik

Fachbegriffe der Volkswirtschaft

Die Volkswirtschaftslehre stellt einen Grossteil der Fachtermini vor, die Sie in diesem Lexikon finden werden. Viele Begriffe aus der Finanzwelt stehen im Schnittbereich von Betriebswirtschafts- und Volkswirtschaftslehre.

Investitionsrechnungen

Marktversagen

Umsatzsteuer