The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Den Begriff des Isomorphismus zwischen zwei Graphen hatten wir bereits am Anfang eingeführt (Definition 2.4). Wir haben zwei gerichtete Graphen G = (V, R, α, ω) und G′ = (V′, R′,α′,ω′) als isomorph bezeichnet, wenn es bijektive Abbildungen σ: V →V′ und τ: R→R′ gibt, die in G inzidente bzw. adjazente Objekte auf solche in G′ abbilden. In diesem Kapitel beschäftigen wir uns erneut mit Graphenisomorphie...
Wir haben Matchings bereits in Abschnitt 9.10 (Heiratssatz, Satz von König) kennengelernt. Ein Matching in einem ungerichteten Graphen G ist eine Teilmenge M ⊆ E(G) der Kantenmenge E(G), so dass keine zwei Kanten aus M inzidieren. In diesem Kapitel beschäftigen wir uns mit weiteren Eigenschaften von Matchings und ihrer algorithmischen Bestimmung. Als Grundvoraussetzung sei in diesem Kapitel stets...
In Kapitel 1 haben wir im Zusammenhang mit der Routenplanung und dem Königsberger Brückenproblem bereits von Wegen bzw. Kreisen in einem Graphen gesprochen. In diesem Kapitel werden wir diese Begriffe exakt fassen und wichtige Eigenschaften herleiten. Unter anderem kommen wir dabei auf das Königsberger Brückenproblem zurück und beweisen — wie angekündigt — den Satz von Euler (in verschiedenen Variationen),...
In diesem Abschnitt beschäftigen wir uns mit der sogenannten Tiefensuche DFS (depth first search), einem effizienten Verfahren, um strukturelle Informationen über einen Graphen, etwa über seine Zusammenhangskomponenten, zu gewinnen.
The input for the hotlink assignment problem consists of a node weighted directed acyclic graph with a designated root node r. The goal is to minimize the weighted shortest path length rooted at r by adding a restricted number of outgoing arcs (hotlinks) to each node. The (h, k)-hotlink assignment problem is defined on k-regular complete trees, and at most h hotlinks can be assigned to each node.We...
An instance of the maximum coverage problem is given by a set of weighted ground elements and a cost weighted family of subsets of the ground element set. The goal is to select a subfamily of total cost of at most that of a given budget maximizing the weight of the covered elements. We formulate the problem on graphs: In this situation the set of ground elements is speci.ed by the nodes of a graph,...
We focus on MIP-formulations for flowshop scheduling problems of the kind Fm | lwt | γ, with the restriction lwt indicating that jobs are allowed to wait on a fixed limited number of buffers between machine levels. Most of the models discussed in literature only consider permutation schedules, i.e., schedules in which jobs are processed in identical order on all...
In the problem of Online Call Admission in Optical Networks, briefly called OCA ,we are given a graph G = (V,E) together with a set of wavelengths W and a finite sequence σ = r1, r2,...of calls which arrive in an online fashion. Each call rj specifies a pair of nodes to be connected and an integral demand indicating the number of required lightpaths. A lightpath is a...
Strömungen und Flüsse sind wichtige Werkzeuge zur Modellierung vieler Optimierungsprobleme. Informell besteht das »Maximalfluss-Problem« darin, in einem Netz mit Kapazitäten auf den Pfeilen so viel Fluss wie möglich von einer ausgezeichneten Quelle s zu einer ausgezeichneten Quelle t zu schicken. Dabei dürfen die Kapazitäten nicht überschritten werden.
Sollen in einer Region n Orte v1, ..., vn verbunden werden (mittels Glasfaser-Netz, Straßennetz, Wasserleitung o.Ä.), so fallen bei der Realisierung einer direkten Verbindung von vi nach vj Kosten cij ∈ ℝ+ an. Durch geographische Vorgaben sind dabei...
In Kapitel 1 haben wir im Zusammenhang mit der Routenplanung und dem Königsberger Brückenproblem bereits von Wegen bzw. Kreisen in einem Graphen gesprochen. In diesem Kapitel werden wir diese Begriffe exakt fassen und wichtige Eigenschaften herleiten. Unter anderem kommen wir dabei auf das Königsberger Brückenproblem zurück und beweisen – wie angekündigt – den Satz von Euler (in verschiedenen Variationen),...
Den Begriff des Isomorphismus zwischen zwei Graphen hatten wir bereits am Anfang eingeführt (Definition 2.4). Wir haben zwei gerichtete Graphen $$G = (V,R,\alpha ,\omega)$$ und $$G' = (V',R',\alpha ',\omega ')$$ als isomorph bezeichnet, wenn es bijektive Abbildungen $$\sigma :V \to V'$$ und $$\tau :R \to R'$$ gibt, die in G inzidente bzw. adjazente Objekte auf solche in $$G'$$ abbilden. In diesem...
In der Einleitung haben wir ein kürzeste-Wege-Problem aus dem Bereich der Routenplanung kennengelernt. Das älteste dokumentierte kürzeste-Wege-Problem stammt nach [24] aus Schillers Schauspiel »Wilhelm Tell« [140, IV. Aufzug, 1. Szene]: Tell befindet sich nach dem Apfelschuss am Ufer des Vierwaldstätter Sees nahe beim Ort Altdorf.
Ein gerichteter Graph (kurz Graph) ist ein Quadrupel G = (V; R; α ω) mit folgenden Eigenschaften: (i) V ist eine nicht leere Menge, die Eckenmenge des Graphen(ii) R ist eine Menge, die Pfeilmenge des Graphen.(iii)Es gilt V∩R = Φ.(iv)α : R→V und ω : R→V sind Abbildungen (α(r) ist die Anfangsecke, Anfangsecke ω(r) die Endecke des Pfeils r).
Ein gerichteter Graph (kurz Graph) ist ein Quadrupel G = (V, R, α, ω) mit folgenden Eigenschaften: (i) V ist eine nicht leere Menge, die Eckenmenge des Graphen. (ii) R ist eine Menge, die Pfeilmenge des Graphen. (iii) Es gilt V ∩ R = Ø (iv) α: R → V und ω: R → V sind Abbildungen (α(r) ist die Anfangsecke, ω(r) die Endecke des Pfeils r). ...
Das Problem 2-SAT besteht aus der Einschränkung des aussagenlogischen Erfüllbarkeitsproblems SAT (vgl. Abschnitt 2.6) auf diejenigen Instanzen, in denen jede Klausel genau zwei Literale enthält. Jede Klausel ist daher dann von der Form $$ \{ L_i ,L_j \} $$ mit $$ L_i \in \{ x_i \ddot x_i \} $$ und $$ L_j \in \{ x_j \ddot x_j \} $$.
In diesem Abschnitt beschäftigen wir uns mit der sogenannten Tiefensuche DFS (depth first search), einem effizienten Verfahren, um strukturelle Informationen über einen Graphen, etwa über seine Zusammenhangskomponenten, zu gewinnen.
In der Einleitung haben wir ein kürzeste-Wege-Problem aus dem Bereich der Routenplanung kennengelernt. Das älteste dokumentierte kürzeste-Wege-Problem stammt nach [24] aus Schillers Schauspiel »Wilhelm Tell« [141, IV. Aufzug, 1. Szene]: Tell befindet sich nach dem Apfelschuss am Ufer des Vierwaldstätter Sees nahe beim Ort Altendorf. Er muss vor dem Reichsvogt Hermann Geßler die Hohle Gasse in Küßnacht...
Im Vernetzungs-Problem aus Abschnitt 6.1 sollten alle Orte miteinander verbunden werden. Was passiert, wenn wir nur eine Teilmenge der Orte verbinden müssen?
Strömungen und Flüsse sind wichtige Werkzeuge zur Modellierung vieler Optimierungsprobleme. Informell besteht das »Maximalfluss-Problem« darin, in einem Netz mit Kapazitäten auf den Pfeilen so viel Fluss wie möglich von einer ausgezeichneten Quelle s zu einer ausgezeichneten Quelle t zu schicken. Dabei dürfen die Kapazitäten nicht überschritten werden.
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.