| Autore |
Fournier Jean-Claude
|
| Pubbl/distr/stampa |
London ; ; ISTE ; ; Hoboken, NJ, : Wiley, 2009
|
| Descrizione fisica |
1 online resource (284 p.)
|
| Disciplina |
511.5
511/.5
|
| Collana |
ISTE
|
| Soggetto topico |
Graph theory
|
| ISBN |
1-118-62309-6
1-282-25390-5
9786613814555
0-470-61154-5
0-470-39420-X
|
| Classificazione |
SK 890
|
| Formato |
Materiale a stampa  |
| Livello bibliografico |
Monografia |
| Lingua di pubblicazione |
eng
|
| Nota di contenuto |
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
|
| Record Nr. | UNINA-9910139510003321 |
Info
Graph theory and applications [Risorsa elettronica] : with exercises and problems / Jean-Claude Fournier
