LEADER 05441nam 2200733Ia 450 001 9910139510003321 005 20200520144314.0 010 $a9786613814555 010 $a9781118623091 010 $a1118623096 010 $a9781282253902 010 $a1282253905 010 $a9780470611548 010 $a0470611545 010 $a9780470394205 010 $a047039420X 035 $a(CKB)2550000000005876 035 $a(EBL)477664 035 $a(OCoLC)521028724 035 $a(SSID)ssj0000338275 035 $a(PQKBManifestationID)11230390 035 $a(PQKBTitleCode)TC0000338275 035 $a(PQKBWorkID)10297001 035 $a(PQKB)11458251 035 $a(MiAaPQ)EBC477664 035 $a(PPN)197881440 035 $a(Perlego)1008128 035 $a(EXLCZ)992550000000005876 100 $a20081015d2009 uy 0 101 0 $aeng 135 $aur|n|---||||| 181 $ctxt 182 $cc 183 $acr 200 10$aGraph theory and applications with exercises and problems /$fJean-Claude Fournier 210 $aLondon ;$aISTE ;$aHoboken, NJ $cWiley$d2009 215 $a1 online resource (284 p.) 225 1 $aISTE ;$vv.72 300 $aDescription based upon print version of record. 311 08$a9781848210707 311 08$a1848210701 320 $aIncludes bibliographical references and index. 327 $aGraph 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 327 $a1.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 327 $a2.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 327 $a4.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 327 $a5.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 327 $a6.1.2 Types of problems 330 $aThis 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 410 0$aISTE 606 $aGraph theory 606 $aGraph theory$vProblems, exercises, etc 615 0$aGraph theory. 615 0$aGraph theory 676 $a511/.5 686 $aSK 890$2rvk 700 $aFournier$b Jean-Claude$0521962 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910139510003321 996 $aGraph theory and applications$9835212 997 $aUNINA