Search

In this chapter we study applications of directed and edge-coloured graphs to quantum mechanics, embedded computing, the traveling salesman problem, constraint satisfaction, genetics and other areas.

In the previous chapters, we considered various properties of cycles in digraphs. In this chapter, we consider the question of how few vertices have to be deleted to get rid of all cycles. We will also consider the arc version of this question (i.e., to destroy all cycles we delete arcs rather than vertices). The last question leads us to the notion of an ‘optimal’ ordering of a digraph which is of interest in various applications. We will see that the minimum number of vertices (arcs) required to destroy all cycles is related to the maximum number of vertex-disjoint (arc-disjoint) cycles in the digraph under consideration. We will also consider the question of decreasing the number of cycles by reversing arcs.

In this chapter, we study the class of edge-coloured multigraphs which is one of the most investigated generalizations of directed multigraphs. The fact that edge-coloured multigraphs generalize directed multigraphs follows, in particular, from Haggkvist’s transformation described in Section 16.1. Apart from edge-coloured multigraphs, there are many other generalizations of directed multigraphs such as arc-coloured digraphs, hypertournaments and star hypergraphs.

In this chapter we study problems dealing with packing subdigraphs into a digraph, covering the vertices of a digraph by certain structures or decomposing a digraph into pieces with given properties. Many results fall into this very general description and we can only cover some representative ones.

We saw in Chapter 5 that it is easy to check (e.g., using flows) whether a directed multigraph D=(V,A) has k (arc)-disjoint paths P1,P2,…,P k from a subset X⊂V to another subset Y⊂V and we can also find such paths efficiently. On many occasions (e.g., in practical applications) we need to be able to specify the initial and terminal vertices of each P i , i=1,2,…,k, that is, we wish to find a so-called linkage from X={x1,x2,…,x k } to Y={y1,y2,…,y k } such that P i is an (x i ,y i )-path for every i∈[k]. This problem is considerably more difficult and is in fact \(\mathcal{NP}\)-complete already when k=2. In this chapter we start by giving a proof of this fact and then we discuss a number of results on sufficient conditions for the existence of linkages, polynomial algorithms for special classes of digraphs, including acyclic, planar and semicomplete digraphs in the case of vertex disjoint paths and acyclic digraphs and some generalizations of tournaments in the case of arc-disjoint paths. The reader will see that quite a lot can be said about the linkage problems for special classes of digraphs and that still the problems are not trivial for these classes of digraphs. Finally we briefly discuss topics such as multi commodity flows and subdivisions of transitive tournaments in digraphs with large out-degree.

The purpose of this chapter is to discuss various aspects of orientations of (multi)graphs. There are many ways of looking at such questions. We can ask which graphs can be oriented as a digraph of a certain type (e.g., a locally semicomplete digraph). We can try to obtain orientations containing no directed cycles of even length, or no long paths. We can try to relate certain parameters of a graph to the family of all orientations of this graph (e.g., what does high chromatic number imply for orientations of a graph). We can also look for conditions which guarantee orientations with high arc-strong connectivity or high in-degree at every vertex, etc. There are hundreds of papers dealing with orientations of graphs in one way or another and we can only cover some of these topics. Hence we have chosen some of those mentioned above. Finally, we also study briefly the theory of submodular flows, which generalizes standard flows in networks and turns out to be a very useful tool (not only theoretically, but also algorithmically) for certain types of connectivity questions as well as orientation problems. We illustrate this by applying the submodular flow techniques to questions about orientations of mixed graphs and by giving a short proof of Nash-Williams’ orientation theorem. In Section 13.1 we also use submodular flows to give an algorithmic proof of the Lucchesi-Younger Theorem.

In this chapter we will consider the hamiltonian path and cycle problems for digraphs as well as some related problems such as the longest or vertex-heaviest path and cycle problems. We describe and prove a number of results in the area as well as formulate several open questions.

Last, but not least wirkt die Netz-Metapher auch tief greifend auf den Umgang mit dem Faktor „Mensch“ in den Unternehmen, wie es der amerikanische Business-Autor Don Tapscott in seinem Buch „The Digital Economy“ theoretisch auf den Punkt gebracht hat: „Das neue Unternehmen hat nunmehr eine molekulare Struktur. Es basiert auf dem einzelnen Menschen. Der Wissensarbeiter — das menschliche Molekul — agiert als selbstandige Geschaftseinheit. Dabei handelt es sich um motivierte, selbst lernende, unternehmerische Mitarbeiter mit entsprechenden Befugnissen und Vollmachten, die in der Lage sind, mit Hilfe neuer Werkzeuge mit ihrem Wissen und ihrer Kreativitat zur Wertschopfung beizutragen.“ Gewiss: eine ausgemachte Idealvorstellung — bestenfalls reprasentativ fur einen in ferner Zukunft durch den standigen Umgang mit der allgegenwartigen Vernetzung runderneuerten Typus des Homo oeconomicus.

Schnitt. Szenenwechsel. Gehen wir auf eine Zeitreise in die nahere Zukunft — irgendwann zwischen 2010 und 2020. Allgegenwartig in unserer Lebenswelt haben sich winzige Computer eingenistet: Zur Miniatur geschrumpfte Web-Server — manche davon nur mehr reiskorngros, andere und leistungsfahigere noch in der Dimension einer Streichholzschachtel — verleihen nunmehr auch den Dingen des Alltags ein Mehr an kommunikativer Intelligenz.

Schnitt. Erneuter Szenenwechsel. Reden wir vom Geschaft. Mit der „Dritten Welle“ und ihrer synergetischen Erganzung und Aufwertung der Sprachtelefonie mit der ortsunabhangigen Datenkommunikation wird das gewohnte Handynetz zu einer mobilen „Shopping Mall“ fur diverse dafur geeignete Businesses. Es wird zu einer medialen Piazza fur Freizeitvergnugen und Entertainment von Musik uber Comics und Spiele bis hin zu Video-Clips. Und es wird zu einem Marktplatz von wertvoller Information, die ad hoc und der Situation adaquat abgerufen werden kann — gegen einen in der Regel bescheidenen Obulus.

The purpose of this chapter is to discuss various aspects of orientations of (multi)graphs. There are many ways of looking at such questions. We can ask which graphs can be oriented as a digraph of a certain type (e.g. a locally semicomplete digraph). We can try to obtain orientations containing no directed cycles of even length, or no long paths. We can try to relate certain parameters of a graph to the family of all orientations of this graph (e.g. what does high chromatic number imply for orientations of a graph). We can also look for conditions which guarantee orientations with high arc-strong connectivity or high in-degree at every vertex, etc. There are hundreds of papers dealing with orientations of graphs in one way or another and we can only cover some of these topics. Hence we have chosen some of those mentioned above. Finally we also study briefly the theory of submodular flows which generalizes standard flows in networks and turns out to be a very useful tool (not only theoretically, but also algorithmically) for certain types of connectivity questions as well as orientation problems. We illustrate this by applying the submodular flow techniques to questions about orientations of mixed graphs as well as to give short proofs of the Lucchesi-Younger Theorem and Nash-Williams’ orientation theorem. We recall that n and m usually stand for the number of vertices and arcs (edges) of the (di)graph in question.

Zugegeben: Dieser immer multidimensionaler werdende Bezug zum Kunden ergibt aus der Sicht der Netzbetreiber oder Service– und Content-Anbieter ein sehr komplexes Konglomerat an vielen kleinen Marktsegmenten, von denen jedes einen ganz eigenen Entwicklungs- und Handlungsbedarf auf die kommenden Monate und Jahre hin erfordert. Vom Kunden aus gesehen prasentiert sich die Sache viel einfacher: Er ahnt intuitiv, dass er historisch ganz nahe daran ist, zum Mittelpunkt und Zentrum aller vitalen Aktionen der vernetzten Welt zu werden. Und mit dem weiteren Heranreifen der Epoche der allseitigen technologischen Vernetzung, mit dem „Evernet“ der nachsten ein bis zwei Jahrzehnte, wird es endgultig zum okonomischen Einmaleins, dass der Kunde (und kein noch so groser multinationaler Konzern) zum Epizentrum des Business geworden ist. Er ist die Konstante, und sein Wunsch ist Befehl, weil er im allseitigen Netz effektiv dafur sorgen kann, dass er gehort und vor allem gut bedient wird.

In this chapter we introduce several classes of digraphs. We study these classes with respect to their properties, characterization, recognition and decomposition. Further properties of the classes are studied in the following chapters of this book.

Am Anfang war das Mobiltelefon noch nicht wirklich „handy“ — also komfortabel und tragbar, kurz: handlich. Und seine Genesis reicht weit in die vordigitale Zeitrechnung zuruck: In den spaten 6oer Jahren machte der US-Telekom-Gigant ATT / Bell System den weltweit ersten Vorschlag fur ein allgemein zugangliches mobiles Kommunikationsnetz: Das „Advanced Mobile Phone System“ (AMPS) war damit aus der Taufe gehoben. Zwar gab es zu diesem Zeitpunkt bereits eine bescheidene Anzahl mobiler Funknetze, das erste Bell-Mobil-Patent datiert immerhin aus dem Jahr 1947, die praktische Nutzung war hingegen immer noch Militars oder aber zivilen Einsatzkraften wie Polizei oder Rettung vorbehalten. Dennoch: Obwohl fur ein Massenpublikum konzipiert, dauerte es noch zwei Jahrzehnte, bis die ersten analogen Funknetze a la AMPS „abzuheben“ begannen. Dermasen schwer wogen anfangs die Endgerate, und derart teuer kam jede Gesprachsminute, dass nur die mobilsten gesellschaftlichen Akteure sich „so etwas“ leisteten — meist Business-Leute oder Politiker, bei denen die standige Erreichbarkeit die Aufwendungen lohnte. Mobil-Telefonie bis weit in die 8oer Jahre bedeutete eben in der Regel: einen tragbaren Koffer mit sich zu schleppen und jedes Monatsende die aufgelaufenen Gesprachskosten sinnvoll gegenuber Firma oder Steuerberater argumentieren zu mussen.

In this chapter, several results proved for digraphs are extended to edge-coloured graphs, arc-coloured digraphs and hypertournaments. We will see that some results remain the same with respect to their formulation, but their proofs become much more involved. Other results do not hold any more. This gives an additional insight to the theory of digraphs. In particular, we can more clearly see which properties of digraphs allow us to obtain various results on them.

In the previous chapters, especially in Chapters 5 and 6, we considered various properties of cycles in digraphs. The study of cycle structure of digraphs is one of the most important areas in the theory of digraphs, and since several very interesting topics in this area have remained uncovered in the previous chapters, we discuss these topics in this chapter. We will mostly consider (directed) cycles; in most cases the adjective ‘directed’ is omitted. Sometimes we will use oriented cycles, i.e. orientations of undirected cycles.

The purpose of this chapter is to describe basic elements of the theory and applications of network flows. This topic is probably the most important single tool for applications of digraphs and perhaps even of graphs as a whole. At the same time, from a theoretical point of view, flow problems constitute a beautiful common generalization of shortest path problems and problems such as finding internally (arc)-disjoint paths from a given vertex to another. The theory of flows is well understood and fairly simple. This, combined with the enormous applicability to real-life problems, makes flows a very attractive topic to study. From a theoretical point of view, flows are well understood as far as the basic questions, such as finding a maximum flow from a given source to a given sink or characterizing the size of such a flow, are concerned. However, the topic is still a very active research field and there are challenging open problems such as deciding whether an O(nm) algorithm exists for the general maximum flow problem.

Kommen wir bewusst noch einmal darauf zuruck: Das Handy hat man in (fast) jeder Lebenssituation dabei. Es hat sich in kurzester Zeit einen ebenso seltenen wie werthaltigen Status erworben — dass es namlich zum noch nicht so ganz unaufdringlichen, jedenfalls aber unabdinglichen Alltagsbegleiter zu werden vermochte. Allenfalls fur Schlussel aller Art, Geldborse samt Bankomat- und Kreditkarten, Ausweisdokumente, bei Businessleuten meist noch Terminkalender oder Palm Organizer, kann man Ahnliches feststellen. In dieser Tatsache allein schon begrundet sich eine gewichtige medienhistorische Gewissheit: Kein aktives Kommunikationsmittel — mit Ausnahme der menschlichen Stimme — hat bislang diese hautnah begleitende Prasenz erlangen konnen. Und kein technisches Medium hat sich dermasen schnell zur „popularen Notwendigkeit“ beziehungsweise zum unverzichtbaren Bedurfnis von grosen Mehrheiten der Bevolkerung entwickelt. Mehr noch: In dieser Eigenschaft gelang dem Handy bei der breiten Masse, was vorher nur dem Sony Walkman (allerdings dort sehr alters-/schichtspezifisch) gegluckt war: namlich die durch Beruf, Schule und andere Alltagspflichten limitierte tagliche Konsumzeit fur technische Medienkommunikation aufzubrechen und zu erweitern.

Wie erstaunlich vielseitig die Nutzung der Handys der nachsten Generationen sein kann — und zweifellos auch wird —, das kann erst in Konturen erahnt werden. Konturen, die sich aus zwei Gesichtspunkten ergeben: zum einen aus der Betrachtung der technologischen Moglichkeiten, die in diesem Kommunikationswerkzeug inharent angelegt sind — oder zumindest ohne viel Muhe als nutzlicher Zusatz integriert werden konnen; zum anderen aus einer Ermessung der Bedurfnisse und Note, die uns Menschen, die wir mit gesteigerter Flexibilitat und Mobilitat konfrontiert werden, eben gewollt oder ungewollt erwachsen. Gerade das Letztere muss in Anbetracht der Vielfalt der neuartigen technischen Moglichkeiten zum primaren Leitsatz der „Dritten Welle“werden, den man etwa so formulieren konnte: „Nicht all das, was technologisch im Bereich des Moglichen liegt, soll den Menschen aufoktroyiert werden. Sondern: Was die Menschen unserer Zeit zur Vereinfachung, Erleichterung und Erweiterung ihres beruflichen wie privaten Lebens benotigen, soll technologisch unterstutzt und ermoglicht werden.“

Erinnern wir uns: Der Personal Computer mutierte uber die vergangenen drei Jahrzehnte in wachsender Progression zum personlichen mobilen Weg- und Arbeitsbegleiter in Gestalt von Notebooks oder Palm Handhelds. Parallel dazu ereignete sich fast „naturgesetzlich“ der Wandel von einzelnen universitaren, militarischen oder industriellen Netzwerk-Inseln zum vorerst noch via erdgebundener Telekommunikation betriebenen Internet. Bis zeitgleich mit der Jahrtausendwende die ersten zaghaft einsetzenden Vorlaufer der „Dritten Welle der Mobilkommunikation“ auch eine Wende zum nachsten Gestaltwandel der globalen Vernetzung ankundigten: Nun kommt das „mobile Internet“! Ein Neo-Terminus, den unvermittelt selbst seriose Business-Journale wie „Fortune“ in seltenem Einklang mit (heute leiser gewordenen) Internet-Hype-Magazinen wie „Fast Company“ verwendeten. Eine unpassende Wortwahl: Setzt sie doch das Internet als Modell ungebrochen positiv voraus — und fugt in dieses „Vorbild“ die Mobilkommunikation quasi als erweiterte Eigenschaft bedenkenlos ein. Man vergisst dabei, dass die Mobilkommunikation per se nicht nur mit einer eigenstandig gewachsenen Art der Vernetzung, sondern auch mit ganz anderen Business-Modellen und Benutzergewohnheiten gros geworden ist.

In this chapter we concentrate on problems concerning (arc)-disjoint paths or trees (arborescences). We embark from the 2-path problem which concerns the existence of two disjoint paths with prescribed initial and terminal vertices. We give a proof by Fortune et al. showing that the 2-path problem is NP-complete. We proceed by studying the more general k-path problem for various classes of digraphs. We show that for acyclic digraphs, the k-path problem is polynomially solvable when k is not a part of the input. Then we describe several results on the k-path problem for generalizations of tournaments. Among other results, we show that the 2-path problem is polynomially solvable for digraphs that can be obtained from strong semi-complete digraphs by substituting arbitrary digraphs for each vertex of the semicomplete digraph. We briefly discuss the k-path problem for planar digraphs and indicate how to use the topological concept of planarity in proofs and algorithms for disjoint path problems in planar digraphs.

Sprechen wir also ganz offen auch von der sich erst langfristig realisierenden Idee. Also von der grosen Vision, die in wenigen Satzen in ihrer Tendenz wie folgt zusammengefasst werden kann: Kunftig konnen wir alle, immer und uberall mit einem „Netz aller Netze“ verbunden sein — zumindest wenn wir das auch dezidiert wollen. Wir konnen somit unser Leben gleichsam online fuhren — und dabei privat wie beruflich standig und weltweit mit allen anderen im Netz kommunizieren. Gemeinsamkeit entsteht dabei vor allem auch durch Gleichzeitigkeit: Wir sind „Always on“ — unabhangig von Ort, Zeitpunkt und gerade verwendetem Kommunikationsgerat. Und die Vision uberschreitet selbst diese ohnedies bereits weit gespannte Dimension: Menschen kommunizieren uber dieses allgegenwartige Netz nicht nur mit Menschen — Menschen kommunizieren auch mit intelligent programmierten Maschinen. Und: Maschinen kommunizieren selbsttatig mit anderen Maschinen.

Mit ebenso hoher Wahrscheinlichkeit wird daher erst die zweite Halfte des Jahrzehnts durch eine rasant beschleunigte Verwirklichung der bis dahin entwickelten und bereitgestellten Potenziale der „Dritten Welle“ gekennzeichnet sein. Mit anderen Worten: DANN GEHT ES LOS. Oder wie Bill Gates pointiert formulierte: „Diese Veranderungen kommen zwar spater als erwartet — dafur aber mit viel starkerer Kraft.“

In this chapter we will consider the hamiltonian path and cycle problems for digraphs as well as some related problems such as the longest path and cycle problems and the minimum path factor problem. We describe and prove a number of results in the area as well as formulate several open questions.

We describe a new type of sufficient condition for a digraph to be Hamiltonian. Conditions of this type combine local structure of the digraph with conditions on the degrees of non-adjacent vertices. The main difference from earlier conditions is that we do not require a degree condition on all pairs of non-adjacent vertices. Our results generalize the classical conditions by Ghouila-Houri and Woodall.

We prove that if $T$ is a tournament on $n\geq 7$ vertices and $x,y$ are distinct vertices of $T$ with the property that $T$ remains 2-connected if we delete the arc between $x$ and $y$, then there exist disjoint 3-cycles $C_x,C_y$ such that $x\in V(C_x)$ and $y\in V(C_y)$. This is best possible in terms of the connectivity assumption. Using this result, we prove that under the same connectivity assumption and if $n\geq 8$, then $T$ also contains complementary cycles $C''_x,C''_y$ (i.e. $V(C''_x)\cup V(C''_y)=V(T)$ and $V(C''_x)\cap V(C''_y)=\emptyset$) such that $x\in V(C''_x)$ and $y\in V(C''_y)$ for every choice of distinct vertices $x,y\in V(T)$. Again this is best possible in terms of the connectivity assumption. It is a trivial consequence of our result that one can decide in polynomial time whether a given tournament $T$ with special vertices $x,y$ contains disjoint cycles $C_x,C_y$ such that $x\in V(C_x)$ and $y\in V(C_y)$. This problem is NP-complete for general digraphs and furthermore there is no degree of strong connectivity which suffices to guarantee such cycles in a general digraph.

We survey results on the sequential and parallel complexity of hamiltonian path and cycle problems in various classes of digraphs which generalize tournaments. We give detailed informations on the difference in difficulties for these problems for the various classes as well as prove new results on hamiltonian paths starting in a specified vertex for a quite general class of digraphs.

A k -king in a digraph D is a vertex which can reach every other vertex by a directed path of length at most k . This definition generalizes the definition of a king in a tournament. We consider quasi-transitive digraphs - a generalization of tournaments recently investigated by the authors (Bang-Jensen and Huang, 1995). We prove that a quasi-transitive digraph has a 3-king if and only if it has an out-branching. We give several results on 3-kings in quasi-transitive digraphs which are analogous to well-known results about kings in tournaments.

We point out mistakes in two papers previously published in Discrete Applied Mathematics, dealing with highly strongly connected spanning local tournaments in locally semicomplete digraphs. We conjecture that every (2k−1)-strong locally semicomplete digraph on at least 2k+1 vertices contains a k-strong spanning local tournament and prove the conjecture for k=1,2. We also prove that every 5-strong locally semicomplete digraph which is not semicomplete contains a 3-strong spanning local tournament. We furthermore show that for semicomplete digraphs, which form a proper subclass of locally semicomplete digraphs, 2k−1 would be the best possible bound and for locally semicomplete digraphs which are not semicomplete we show that the correct bound is at least 2k−3.

We consider the problem of finding two disjoint directed paths with prescribed ends in a semicomplete digraph. The problem is NP - complete for general digraphs as proved in [4]. We obtain best possible sufficient conditions in terms of connectivity for a semicomplete digraph to be 2-linked (i.e., it contains two disjoint paths with prescribed ends for any four given endvertices). We also consider the algorithmically equivalent problem of finding a cycle through two given disjoint edges in a semicomplete digraph. For this problem it is shown that if D is a 5–connected semicomplete digraph, then D has a cycle through any two disjoint edges, and this result is best possible in terms of the connectivity. In contrast to this we prove that if T is a 3–connected tournament, then T has a cycle through any two disjoint edges. This is best possible, too. Finally we give best possible sufficient conditions in terms of local connectivities for a tournament to contain a cycle through af given pair of disjoint edges.

We consider the problem of finding a strongly connected spanning subdigraph with the minimum number of arcs in a strongly connected digraph. This problem is NP-hard for general digraphs since it generalizes the Hamiltonian cycle problem. We show that the problem is polynomially solvable for quasi-transitive digraphs. We describe the minimum number of arcs in such a spanning subdigraph of a quasi-transitive digraph in terms of the path covering number. Our proofs are based on a number of results (some of which are new and interesting in their own right) on the structure of cycles and paths in quasi-transitive digraphs and in extended semicomplete digraphs. In particular, we give a new characterization of the longest cycle in an extended semicomplete digraph. Finally, we point out that our proofs imply that the MSSS problem is solvable in polynomial time for all digraphs that can be obtained from strong semicomplete digraphs on at least two vertices by replacing each vertex with a digraph belonging to a family of digraphs whose path covering number can be decided in polynomial time.

Molecular Tracing of Viral Diseases in Aquaculture = Traçage Moléculaire des Maladies Virales en Aquaculture : Colloque, Montpellier (FRA), 2015/01/27-29; International audience

We discuss problems and conjectures on global connectivity of directed graphs. Lots of information on these and other problems can be found in the forthcoming book [1] which covers connectivity issues of directed graphs extensively. In this extended abstract all digraphs are finite and have no loops, but may have parallel arcs. Notation follows [1].

We consider edge-coloured multigraphs. A trail in such a multigraph is alternating if its successive edges differ in colour. Let G be a 2-edge-coloured complete graph and let M be a 2-edge-coloured complete multigraph. Bankfalvi and Bankfalvi (1968) obtained a necessary and sufficient condition for G to have a Hamiltonian alternating cycle. Generalizing this theorem, Das and Rao (1983) characterized those G which contain a closed alternating trail visiting each vertex v in G exactly f ( v ) > 0 times. We solve the more general problem of determining the length of a longest closed alternating trail T f visiting each vertex v in M at most f ( v ) > 0 times. Our result is a generalization of a theorem by Saad (1996) that determines the length of a longest alternating cycle in G . We prove the existence of a polynomial algorithm for finding the desired trail T f . In particular, this provides a solution to a question in Saad (1996).