Bedienung einer Straße
Graph zur Bedienenung einer Straße
Die Modellierung eines Gaphen der wirklichen Welt:
Nodes N und Arcs A bilden einen gerichteten Graph G = (N,A). Jede gerichtete Kante u aller m Kanten aus A kann durchfahren werden von der Quelle b(u) zur Senke e(u).
Jede Kante hat einn Bei einer Leerfahrt über die Kante u entstehen Kosten c(u). Jede Kante kann ein Andorderung (Job) haben.
Die Teilmenge der Kanten mit Anforderungen im Graphen G heissen R, die einzelne Anforderung einer Kante u aus R somit r(u).
Die gerichteten Kanten u2 (b->a) und u3 (a->b) können oBdA wie Einbahnstraßen zusammengefasst werden. Bei jeder Duchfahrt werden die Anforderungen r1 und r2 auf beiden Seiten bedient.
Die ungerichtete Kante u1 ( a->b, b->a) bedient beide Seiten in beiden Richtungen. Der Job an dieser Straßen kann also in beiden Richtungen erledingt werden.
Deshalb gibt es zwei Kanten v1 und v2 im Graphen G mit Verweisen v1 = inv(v2) und v2 = inv(v1) zueinander. Wenn die Kante nicht "Windy" ist, so sind die Bedienkosten in beiden Richtungen gleich r(v1) = r(v2). Im Weiteren ist darauf zu achten, dass es sich bei den Kanten v1 und v2 aber nur um eine Anforderung r(u1) an der ungerichteten Kante u1 handelt, wenn inv(v1) existiert.
Keine Kommentare:
Kommentar veröffentlichen