Bienvenue chez nous !
Logo Ex Libris
 Laissez-vous inspirer ! 

Digraphs

  • eBook (pdf)
  • 798 Nombre de pages
(0) Donner la première évaluation
Évaluations
(0)
(0)
(0)
(0)
(0)
Afficher toutes les évaluations
Substantially revised, reorganised and updated, the second edition now comprises eighteen chapters, carefully arranged in... Lire la suite
Lisez confortablement vos ebooks dans l’appli gratuite Ex Libris Reader. Vous obtiendrez ici votre lien de téléchargement.
CHF 92.90
Download est disponible immédiatement
Informations sur les eBooks
Les eBooks conviennent également aux appareils mobiles (voir les instructions).
Les eBooks d'Ex Libris sont protégés contre la copie par ADOBE DRM: apprenez-en plus.
Pour plus d'informations, cliquez ici.
Ce produit n'est actuellement disponible que dans la boutique en ligne.

Description

Substantially revised, reorganised and updated, the second edition now comprises eighteen chapters, carefully arranged in a straightforward and logical manner, with many new results and open problems.

As well as covering the theoretical aspects of the subject, with detailed proofs of many important results, the authors present a number of algorithms, and whole chapters are devoted to topics such as branchings, feedback arc and vertex sets, connectivity augmentations, sparse subdigraphs with prescribed connectivity, and also packing, covering and decompositions of digraphs. Throughout the book, there is a strong focus on applications which include quantum mechanics, bioinformatics, embedded computing, and the travelling salesman problem.

Detailed indices and topic-oriented chapters ease navigation, and more than 650 exercises, 170 figures and 150 open problems are included to help immerse the reader in all aspects of the subject.



Texte du rabat

The theory of directed graphs has developed enormously over recent decades, yet this book (first published in 2000) remains the only book to cover more than a small fraction of the results. New research in the field has made a second edition a necessity.

Substantially revised, reorganised and updated, the book now comprises eighteen chapters, carefully arranged in a straightforward and logical manner, with many new results and open problems.

As well as covering the theoretical aspects of the subject, with detailed proofs of many important results, the authors present a number of algorithms, and whole chapters are devoted to topics such as branchings, feedback arc and vertex sets, connectivity augmentations, sparse subdigraphs with prescribed connectivity, and also packing, covering and decompositions of digraphs. Throughout the book, there is a strong focus on applications which include quantum mechanics, bioinformatics, embedded computing, and the travelling salesman problem.

Detailed indices and topic-oriented chapters ease navigation, and more than 650 exercises, 170 figures and 150 open problems are included to help immerse the reader in all aspects of the subject.

Digraphs is an essential, comprehensive reference for undergraduate and graduate students, and researchers in mathematics, operations research and computer science. It will also prove invaluable to specialists in related areas, such as meteorology, physics and computational biology.

Jørgen Bang-Jensen is a Professor in the Department of Mathematics and Computer Science at the University of Southern Denmark, Odense, Denmark.

Gregory Gutin is Professor of Computer Science at Royal Holloway College, University of London, UK.



Contenu
1. Basic Terminology, Notation and Results. -1.1 Sets, Matrices and Vectors. -1.2 Digraphs, Subdigraphs, Neighbours, Degrees. -1.3 Isomorphism and Basic Operations on Digraphs. -1.4 Walks, Trails, Paths, Cycles and Path-Cycle Subdigraphs. -1.5 Strong and Unilateral Connectivity. -1.6 Undirected Graphs, Biorientations and Orientations. -1.7 Trees and Euler Trails in Digraphs. -1.8 Mixed Graphs, Orientations of Digraphs, and Hypergraphs. -1.9 Depth-First Search. -1.10 Exercises. -2. Classes of Digraphs. -2.1 Acyclic Digraphs. -2.2 Multipartite Digraphs and Extended Digraphs. -2.3 Transitive Digraphs, Transitive Closures and Reductions. -2.4 Line Digraphs. -2.5 The de Bruijn and Kautz Digraphs. -2.6 Series-Parallel Digraphs. -2.7 Quasi-Transitive Digraphs. -2.8 Path-Mergeable Digraphs. -2.9 Locally In/Out-Semicomplete Digraphs. -2.10 Locally Semicomplete Digraphs. -2.11 Totally F-Decomposable Digraphs. -2.12 Planar Digraphs. -2.13 Digraphs of Bounded Tree-Width -2.14 Other Families of Digraphs. -2.15 Exercises. -3. Distances. -3.1 Terminology and Notation on Distances. -3.2 Structure of Shortest Paths. -3.3 Algorithms for Finding Distances in Digraphs. -3.3.1 Breadth-First Search (BFS). -3.3.2 Acyclic Digraphs. -3.3.3 Dijkstra's Algorithm. -3.3.4 The Bellman-Ford-Moore Algorithm. -3.3.5 The Floyd-Warshall Algorithm. -3.4 Inequalities on Diameter. -3.5 Minimum Diameter of Orientations of Multigraphs. -3.6 Minimum Diameter Orientations of Some Graphs and Digraphs. -3.7 Kings in Digraphs. -3.8 (k, l)-Kernels. -3.9 Exercises. -4. Flows in Networks. -4.1 Definitions and Basic Properties. -4.2 Reductions Among Different Flow Models. -4.3 Flow Decompositions. -4.4 Working with the Residual Network. -4.5 The Maximum Flow Problem. -4.6 Polynomial Algorithms for Finding a Maximum (s, t)-Flow. -4.7 Unit Capacity Networks and Simple Networks. -4.8 Circulations and Feasible Flows. -4.9 Minimum Value Feasible (s, t)-Flows. -4.10 Minimum Cost Flows. -4.11 Applications of Flows.-4.12 Exercises. -5. Connectivity of Digraphs. -5.1 Additional Notation and Preliminaries. -5.2 Finding the Strong Components of a Digraph. -5.3 Ear Decompositions. -5.4 Menger's Theorem. -5.5 Determining Arc- and Vertex-Strong Connectivity. -5.6 Minimally k-(Arc)-Strong Directed Multigraphs. -5.7 Critically k-Strong Digraphs. -5.8 Connectivity Properties of Special Classes of Digraphs. -5.9 Disjoint X-paths in Digraphs. -5.10 Exercises. -6. Hamiltonian, Longest and Vertex-Cheapest Paths and Cycles. -6.1 Complexity. -6.2 Hamilton Paths and Cycles in Path-Mergeable Digraphs. -6.3 Hamilton Paths and Cycles in Locally In-Semicomplete Digraphs. -6.4 Hamilton Cycles and Paths in Degree-Constrained Digraphs. -6.5 Longest Paths and Cycles in Degree-Constrained Oriented Graphs. -6.6 Longest Paths and Cycles in Semicomplete Multipartite Digraphs. -6.7 Hamilton Paths and Cycles in Quasi-Transitive Digraphs. -6.8 Vertex-Cheapest Paths and Cycles. -6.9 Hamilton Paths and Cycles in Various Classes of Digraphs. -6.10 Exercises. -7. Restricted Hamiltonian Paths and Cycles. -7.1 Hamiltonian Paths with a Prescribed End-Vertex. -7.2 Weakly Hamiltonian-Connected Digraphs. -7.3 Hamiltonian-Connected Digraphs. -7.4 Hamiltonian Cycles Containing or Avoiding Prescribed Arcs. -7.5 Arc-Traceable Digraphs. -7.6 Oriented Hamiltonian Paths and Cycles. -7.7 Exercises. -8. Paths and Cycles of Prescribed Lengths. -8.1 Pancyclicity of Digraphs. -8.2 Colour Coding: Efficient Algorithms for Paths and Cycles. -8.3 Cycles of Length k Modulo p. -8.4 Girth. -8.5 Short Cycles in Semicomplete Multipartite Digraphs. -8.6 Exercises. -9. Branchings. -9.1 Tutte's Matrix Tree Theorem. -9.2 Optimum Branchings. -9.3 Arc-Disjoint Branchings. -9.4 Implications of Edmonds' Branching Theorem. -9.5 Out-Branchings with Degree Bounds. -9.6 Arc-Disjoint In- and Out-Branchings. -9.7 Out-Branchings with Extremal Number of Leaves. -9.8 The Source Location Problem. -9.9 Miscellaneous Topics. -9.10 Exercises. -10.

Informations sur le produit

Titre: Digraphs
Auteur:
Code EAN: 9781848009981
ISBN: 978-1-84800-998-1
Protection contre la copie numérique: filigrane numérique
Format: eBook (pdf)
Editeur: Springer
Genre: Bases
nombre de pages: 798
Parution: 17.12.2008
Année: 2008
Auflage: 2nd ed. 2009
Sous-titre: Englisch
Taille de fichier: 7.1 MB