Schweitzer Fachinformationen
Wenn es um professionelles Wissen geht, ist Schweitzer Fachinformationen wegweisend. Kunden aus Recht und Beratung sowie Unternehmen, öffentliche Verwaltungen und Bibliotheken erhalten komplette Lösungen zum Beschaffen, Verwalten und Nutzen von digitalen und gedruckten Medien.
Zunächst werden in Abschnitt 2.1 Graphen und - als Spezialfälle - Bäume und Netzwerke eingeführt. Viele Fragestellungen des OR lassen sich durch Graphen abbilden. Oft folgt dann die Frage nach kürzesten Wegen in diesen Konstrukten, die in Abschnitt 2.2 vgl. S. 56 gelöst wird. Beispiel für die Suche nach längsten Wegen sind Netzpläne zur Projektsteuerung, die in Abschnitt 2.3 vgl. S. 64 erklärt werden. Viele Optimierungsprobleme, die sich in Graphen abbilden lassen, sind mit der Dynamischen Optimierung zu lösen, die in Abschnitt 2.4 vgl. S. 76 angesprochen wird.
Um Graphen mathematisch "erfassbar" zu machen, benötigen wir zunächst Sprechweisen und etwas Handwerkszeug. Mathematische Begriffe zur Modellierung sind hier Objekte, Mengen und Relationen.
In Modellen werden Objekte der Realwelt zur mathematischen Behandlung oft in Mengen zusammengefasst. Zur formalen Umsetzung von Beziehungen zwischen solchen Objekten einer oder mehrerer Mengen dienen Relationen.
Definition 2.1
Seien A und B (nicht-leere) Mengen. Eine Teilmenge
R ? A × B heißt (binäre) RELATION Glossar von A nach B
Dabei ist A × B das KARTESISCHE PRODUKT Glossar der Mengen A und B, das definiert wird durch
A × B = {(a, b) : a ? A, b ?B}
Eine Relation beinhaltet also in der Regel nicht alle Kombinationsmöglichkeiten, sondern einen Ausschnitt davon. Dieser Ausschnitt kann durch Aufzählung oder durch irgendwelche Kriterien definiert werden.
Kartesisches Produkt und Relationen lassen sich auch für mehr als zwei Mengen definieren: Ai ? , 1 = i = m,
R ? A1 × · · · × Am heißt Relation zwischen A1, . . . , Am
Definition 2.2 (Komposition/Inversion von Relationen)
Mit Relationen lässt sich auch "rechnen". Vorbild dabei sind die entsprechenden Operationen für Funktionen.
dann heißt R º S ? A × C Komposition von R und S und ist definiert durch
R º S = {(a, c) : ? b ? mit (a, b) ? R und (b, c) ? S}
dann ist R-1 ? B × A die inverse Relation, die definiert ist durch
R-1 = {(b, a) : (a, b) ? R}
Gegeben seien
Dann gilt:
R º S = {(1, 1), (1, 2), (2, 3), (2, 4), (3, 1), (3, 2)} ? A × C
R-1 = {(0, 1), (1, 2), (0, 3)} ? B × A
S-1 = {(1, 0), (2, 0), (3, 1), (4, 1)} ? C × B
Rechenregeln
=? (R º S) º T = R º ( S º T)
=? (R º S)-1 = S-1 º R-1
=? (R-1)-1 = R
Jede binäre Relation von einer endlichen Menge A nach einer endlichen Menge B lässt sich zwanglos graphisch darstellen.
Gegeben seien A = {1, 2, 3, 4} und B = {x, y, z}. Die Relation sei gegeben durch R = {(1, x), (1, z), (2, y), (3, y), (3, z), (4, x)}
Eine mögliche grafische Darstellung zeigt Abbildung 2.1.
Abbildung 2.1: Grafische Darstellung einer Relation
Formalisiert wird diese Darstellung durch die folgende Begriffsbildung.
GRAPHEN Glossar dienen der Darstellung von Strukturen, d.h. logischen und/oder zeitlichen Abhängigkeiten.
Definition 2.3
Sei V ? eine endliche Menge ("vertices", d.h. KNOTEN Glossar) und E eine Menge zweielementiger Teilmengen von V ("edges", d.h. KANTEN Glossar). Dann wird
G = (V, E)
als (ungerichteter) Graph bezeichnet.
V sei die Menge der (internationalen) Flughäfen in Deutschland. {v, w} ? E, falls zwischen v und w eine Direktverbindung besteht. Der Sachverhalt lässt sich durch ein Schaubild wie Abbildung 2.2 darstellen, das durchaus auch mal mehr als nur Knoten und Kanten enthält. (Die hier eingezeichneten Verbindungen sind nur zur Illustration gedacht und dürften mit den tatsächlichen Verbindungen vermutlich wenig zu tun haben.)
Abbildung 2.2: Flugverbindungen in Deutschland
Für die weitere Diskussion bauen wir uns ein übersichtliches Beispiel, in dem nur die relevanten Elemente abgebildet werden.
V = {1, 2, 3, 4, 5, 6}
E = {{1, 2}, {1, 3}, {1, 5}, {1, 6}, {2, 3}, {3, 4}, {3, 6}, {4, 5}, {5, 6}}
Eine einfache Darstellung des Graphen ist in Abbildung 2.3 zu sehen.
Abbildung 2.3: Beispielgraph
Die Anordnung der Knoten und Kanten im Raum ist nicht eindeutig festgelegt; insofern repräsentiert auch die Abbildung 2.4 denselben Graphen.
Abbildung 2.4: Beispielgraph in anderer Darstellung
Wir werden üblicherweise mit schlichten Graphen arbeiten, die definiert sind durch die Festlegungen:
Weitere Begriffe:
Gegeben sei eine Kante e = {v, w} ? E, dann sagt man:
Man benötigt zur Rechnung üblicherweise nicht die grafische Darstellung eines Graphen, sondern eine algorithmisch nutzbare Form, die denselben Sachverhalt darstellt. Möglich ist die algebraische Beschreibung eines Graphen G = (V, E), V = {v1, . . . , vm} mittels der ADJAZENZMATRIX Glossar A = [aij], 1 = i, j = m, die definiert ist durch die Einträge
Dem schon bekannten Graphen in Abbildung 2.5
Abbildung 2.5: Beispielgraph
entspricht die Adjazenzmatrix
Bemerkungen:
Weitere Sprechweisen:
Die Definition E | W := {{w, w´} ? E : w, w´ ? W} ergibt die Kanten, die nach Weglassen von Ecken noch Start- und Endpunkte...
Dateiformat: ePUBKopierschutz: Adobe-DRM (Digital Rights Management)
Systemvoraussetzungen:
Das Dateiformat ePUB ist sehr gut für Romane und Sachbücher geeignet – also für „fließenden” Text ohne komplexes Layout. Bei E-Readern oder Smartphones passt sich der Zeilen- und Seitenumbruch automatisch den kleinen Displays an. Mit Adobe-DRM wird hier ein „harter” Kopierschutz verwendet. Wenn die notwendigen Voraussetzungen nicht vorliegen, können Sie das E-Book leider nicht öffnen. Daher müssen Sie bereits vor dem Download Ihre Lese-Hardware vorbereiten.Bitte beachten Sie: Wir empfehlen Ihnen unbedingt nach Installation der Lese-Software diese mit Ihrer persönlichen Adobe-ID zu autorisieren!
Weitere Informationen finden Sie in unserer E-Book Hilfe.
