Applied Graph Theory
- 1st Edition - November 13, 2012
- Author: Wai-Kai Chen
- Language: English
- Paperback ISBN:9 7 8 - 0 - 4 4 4 - 5 7 0 0 3 - 1
- eBook ISBN:9 7 8 - 0 - 4 4 4 - 6 0 1 9 3 - 3
Applied Graph Theory provides an introduction to the fundamental concepts of graph theory and its applications. The five key topics that are covered in depth are: (i) foundations… Read more
Purchase options
Institutional subscription on ScienceDirect
Request a sales quoteApplied Graph Theory provides an introduction to the fundamental concepts of graph theory and its applications. The five key topics that are covered in depth are: (i) foundations of electrical network theory; (ii) the directed-graph solutions of linear algebraic equations; (iii) topological analysis of linear systems; (iv) trees and their generation; and (v) the realization of directed graphs with prescribed degrees. Previously, these results have been found only in widely scattered and incomplete journal articles and institutional reports. This book attempts to present a unified and detailed account of these applications. A special feature of the book is that almost all the results are documented in relationship to the known literature, and all the references which have been cited in the text are listed in the bibliography. Thus, the book is especially suitable for those who wish to continue with the study of special topics and to apply graph theory to other fields.
Chapter 1. Basic theory 1. Introduction 2. Basic concepts of abstract graphs 2.1. General definitions 2.2. Isomorphism 2.3. Connectedness 2.4. Rank and nullity 2.5. Degrees 3. Operations on graphs 4. Some important classes of graphs 4.1. Planar graphs 4.2. Separable and nonseparable graphs 4.3. Bipartite graphs 5. Directed graphs 5.1. Basic concepts 5.2. Directed-edge sequence 5.3. Outgoing and incoming degrees 5.4. Strongly-connected directed graphs 5.5. Some important classes of directed graphs 6. Mixed graphs 7. Conclusions ProblemsChapter 2. Foundations of electrical network theory 1. Matrices and directed graphs 1.1. The node-edge incidence matrix 1.2. The circuit-edge incidence matrix 1.3. The cut-edge incidence matrix 1.4. Interrelationships among the matrices A, Bf, and Qf 1.5. Vector spaces associated with the matrices Ba and Qa 2. The electrical network problem 3. Solutions of the electrical network problem 3.1. Branch-current and branch-voltage systems of equations 3.2. Loop system of equations 3.3. Cut system of equations 3.4. Additional considerations 4. Invariance and mutual relations of network determinants and the generalized cofactors 4.1. A brief history 4.2. Preliminary considerations 4.3. The loop and cut transformations 4.4. Network matrices 4.5. Generalized cofactors of the elements of the network matrix 5. Invariance and the incidence functions 6. Topological formulas for RLC networks 6.1. Network determinants and trees and cotrees 6.2. Generalized cofactors and 2-trees and 2-cotrees 6.3. Topological formulas for RLC two-port networks 7. The existence and uniqueness of the network solutions 8. Conclusions ProblemsChapter 3. Directed-graph solutions of linear algebraic equations 1. The associated Coates graph 141 1.1. Topological evaluation of determinants 1.2. Topological evaluation of cofactors 1.3. Topological solutions of linear algebraic equations 1.4. Equivalence and transformations 2. The associated Mason graph 2.1. Topological evaluation of determinants 2.2. Topological evaluation of cofactors 2.3. Topological solutions of linear algebraic equations 2.4. Equivalence and transformations 3. The modifications of Coates and Mason graphs 3.1. Modifications of Coates graphs 3.2. Modifications of Mason graphs 4. The generation of subgraphs of a directed graph 4.1. The generation of 1-factors and 1-factorial connections 4.2. The generation of semifactors and k-semifactors 5. The eigenvalue problem 6. The matrix inversion 7. Conclusions ProblemsChapter 4. Topological analysis of linear systems 1. The equicofactor matrix 2. The associated directed graph 2.1. Directed-trees and first-order cofactors 2.2. Directed 2-trees and second-order cofactors 3. Equivalence and transformations 4. The associated directed graph and the Coates graph 4.1. Directed trees, 1-factors, and semifactors 4.2. Directed 2-trees, 1-factorial connections, and 1-semifactors 5. Generation of directed trees and directed 2-trees 5.1. Algebraic formulation 5.2. Iterative procedure 5.3. Partial factoring 6. Direct analysis of electrical networks 6.1. Open-circuit transfer-impedance and voltage-gain functions 6.2. Short-circuit transfer-admittance and current-gain functions 6.3. Open-circuit impedance and short-circuit admittance matrices 6.4. The physical significance of the associated directed graph 6.5. Direct analysis of the associated directed graph 7. Conclusions ProblemsChapter 5. Trees and their generation 1. The characterizations of a tree 2. The codifying of a tree-structure 2.1. Codification by paths 2.2. Codification by terminal edges 3. Decomposition into paths 4. The Wang-algebra formulation 4.1. The Wang algebra 4.2. Linear dependence 4.3. Trees and cotree s 4.4. Multi-trees and multi-cotrees 4.5. Decomposition 5. Generation of trees by decomposition without duplications 5.1. Essential complementary partitions of a set 5.2. Algorithm 5.3. Decomposition without duplications 6. The matrix formulation 6.1. The enumeration of major submatrices of an arbitrary matrix 6.2. Trees and cotrees 6.3. Directed trees and directed 2-trees 7. Elementary transformations 8. Hamilton circuits in directed-tree graphs 9. Directed trees and directed Euler lines 10. Conclusions ProblemsChapter 6. The realizability of directed graphs with prescribed degrees 1. Existence and realization as a (p, s)-digraph 1.1. Directed graphs and directed bipartite graphs 1.2. Existence 1.3. A simple algorithm for the realization 1.4. Degree invariant transformations 1.5. Realizability as a connected (p, s)-digraph 2. Realizability as a symmetric (p, s)-digraph 2.1. Existence 2.2. Realization 2.3. Realizability as connected, separable and nonseparable graphs 3. Unique realizability of graphs without self-loops 3.1. Preliminary considerations 3.2. Unique realizability as a connected graph 3.3. Unique realizability as a graph 4. Existence and realization of a (p, s)-matrix 5. Realizability as a weighted directed graph 6. Conclusions ProblemsBibliographySymbol indexSubject index
- No. of pages: 498
- Language: English
- Edition: 1
- Published: November 13, 2012
- Imprint: North Holland
- Paperback ISBN: 9780444570031
- eBook ISBN: 9780444601933
Read Applied Graph Theory on ScienceDirect