Details

Autor(en) / Beteiligte

• Fournier, Jean-Claude

Titel

Graph theory and applications with exercises and problems

Beschreibungen/Notizen

• Description based upon print version of record.
• Includes bibliographical references and index.
• Graph Theory and Applications with Exercises and Problems; Table of Contents; Introduction; Chapter 1. Basic Concepts; 1.1 The origin of the graph concept; 1.2 Definition of graphs; 1.2.1 Notation; 1.2.2 Representation; 1.2.3 Terminology; 1.2.4 Isomorphism and unlabeled graphs; 1.2.5 Planar graphs; 1.2.6 Complete graphs; 1.3 Subgraphs; 1.3.1 Customary notation; 1.4 Paths and cycles; 1.4.1 Paths; 1.4.2 Cycles; 1.4.3 Paths and cycles as graphs; 1.5 Degrees; 1.5.1 Regular graphs; 1.6 Connectedness; 1.7 Bipartite graphs; 1.7.1 Characterization; 1.8 Algorithmic aspects
• 1.8.1 Representations of graphs inside amachine1.8.2 Weighted graphs; 1.9 Exercises; Chapter 2. Trees; 2.1 Definitions and properties; 2.1.1 First properties of trees; 2.1.2 Forests; 2.1.3 Bridges; 2.1.4 Tree characterizations; 2.2 Spanning trees; 2.2.1 An interesting illustration of trees; 2.2.2 Spanning trees in a weighted graph; 2.3 Application: minimum spanning tree problem; 2.3.1 The problem; 2.3.2 Kruskal's algorithm; 2.3.3 Justification; 2.3.4 Implementation; 2.3.5 Complexity; 2.4 Connectivity; 2.4.1 Block decomposition; 2.4.2 k-connectivity; 2.4.3 k-connected graphs
• 2.4.4 Menger's theorem2.4.5 Edge connectivity; 2.4.6 k-edge-connected graphs; 2.4.7 Application to networks; 2.4.8 Hypercube; 2.5 Exercises; Chapter 3. Colorings; 3.1 Coloring problems; 3.2 Edge coloring; 3.2.1 Basic results; 3.3 Algorithmic aspects; 3.4 The timetabling problem; 3.4.1 Roomconstraints; 3.4.2 An example; 3.4.3 Conclusion; 3.5 Exercises; Chapter 4. Directed Graphs; 4.1 Definitions and basic concepts; 4.1.1 Notation; 4.1.2 Terminology; 4.1.3 Representation; 4.1.4 Underlying graph; 4.1.5 "Directed" concepts; 4.1.6 Indegrees and outdegrees; 4.1.7 Strongly connected components
• 4.1.8 Representations of digraphs inside a machine4.2 Acyclic digraphs; 4.2.1 Acyclic numbering; 4.2.2 Characterization; 4.2.3 Practical aspects; 4.3 Arborescences; 4.3.1 Drawings; 4.3.2 Terminology; 4.3.3 Characterization of arborescences; 4.3.4 Subarborescences; 4.3.5 Ordered arborescences; 4.3.6 Directed forests; 4.4 Exercises; Chapter 5. Search Algorithms; 5.1 Depth-first search of an arborescence; 5.1.1 Iterative form; 5.1.2 Visits to the vertices; 5.1.3 Justification; 5.1.4 Complexity; 5.2 Optimization of a sequence of decisions; 5.2.1 The eight queens problem
• 5.2.2 Application to game theory:finding a winning strategy5.2.3 Associated arborescence; 5.2.4 Example; 5.2.5 The minimax algorithm; 5.2.6 Implementation; 5.2.7 In concrete terms; 5.2.8 Pruning; 5.3 Depth-first search of a digraph; 5.3.1 Comments; 5.3.2 Justification; 5.3.3 Complexity; 5.3.4 Extended depth-first search; 5.3.5 Justification; 5.3.6 Complexity; 5.3.7 Application to acyclic numbering; 5.3.8 Acyclic numbering algorithms; 5.3.9 Practical implementation; 5.4 Exercises; Chapter 6. Optimal Paths; 6.1 Distances and shortest paths problems; 6.1.1 A few definitions
• 6.1.2 Types of problems
• This book provides a pedagogical and comprehensive introduction to graph theory and its applications. It contains all the standard basic material and develops significant topics and applications, such as: colorings and the timetabling problem, matchings and the optimal assignment problem, and Hamiltonian cycles and the traveling salesman problem, to name but a few. Exercises at various levels are given at the end of each chapter, and a final chapter presents a few general problems with hints for solutions, thus providing the reader with the opportunity to test and refine their knowledge on the
• English