Graph Theory and Its Engineering Applications (Advanced Series in Electrical and Computer Engineering)

Cover......Page 0000_0001.djvu
Title......Page 0001_0001.djvu
Preface......Page 0005_0001.djvu
CONTENTS......Page 0007_0001.djvu
1. Introduction......Page 0013_0001.djvu
2.1. General definitions......Page 0015_0001.djvu
2.2. Isomorphism......Page 0018_0001.djvu
2.3. Connectedness......Page 0020_0001.djvu
2.4. Rank and nullity......Page 0023_0001.djvu
2.5. Degrees......Page 0024_0001.djvu
3. Operations on graphs......Page 0025_0001.djvu
4.1. Planar graphs......Page 0029_0001.djvu
4.2. Separable and nonseparable graphs......Page 0031_0001.djvu
4.3. Bipartite graphs......Page 0034_0001.djvu
5. Directed graphs......Page 0035_0001.djvu
5.1. Basic concepts......Page 0036_0001.djvu
5.2. Directed-edge sequence......Page 0039_0001.djvu
5.3. Outgoing and incoming degrees......Page 0041_0001.djvu
5.4. Strongly-connected directed graphs......Page 0042_0001.djvu
5.5. Some important classes of directed graphs......Page 0043_0001.djvu
7. Conclusions......Page 0044_0001.djvu
Problems......Page 0045_0001.djvu
CHAPTER 2. Foundations of electrical network theory......Page 0048_0001.djvu
1.1. The node-edge incidence matrix......Page 0049_0001.djvu
1.2. The circuit-edge incidence matrix......Page 0053_0001.djvu
1.3. The cut-edge incidence matrix......Page 0058_0001.djvu
1.4. Interrelationships among the matrices A, B and Q......Page 0065_0001.djvu
1.5. Vector spaces associated with the matrices Ba and Qa......Page 0069_0001.djvu
2. The electrical network problem......Page 0070_0001.djvu
3. Solutions of the electrical network problem......Page 0074_0001.djvu
3.2. Loop system of equations......Page 0075_0001.djvu
3.3. Cut system of equations......Page 0082_0001.djvu
3.4. Additional considerations......Page 0088_0001.djvu
4.1. A brief history......Page 0089_0001.djvu
4.2. Preliminary considerations......Page 0090_0001.djvu
4.3. The loop and cut transformations......Page 0095_0001.djvu
4.4. Network matrices......Page 0097_0001.djvu
4.5. Generalized cofactors of the elements of the network matrix......Page 0107_0001.djvu
5. Invariance and the incidence functions......Page 0119_0001.djvu
6.1. Network determinants and trees and cotrees......Page 0123_0001.djvu
6.2. Generalized cofactors and 2-trees and 2-cotrees......Page 0126_0001.djvu
6.3. Topological formulas for RLC two-port networks......Page 0134_0001.djvu
7. The existence and uniqueness of the network solutions......Page 0137_0001.djvu
8. Conclusions......Page 0144_0001.djvu
Problems......Page 0145_0001.djvu
CHAPTER 3. Directed-graph solutions of linear algebraic equations......Page 0152_0001.djvu
1. The associated Coates graph......Page 0153_0001.djvu
1.1. Topological evaluation of determinants......Page 0154_0001.djvu
1.2. Topological evaluation of cofactors......Page 0158_0001.djvu
1 3. Topological solutions of linear algebraic equations......Page 0161_0001.djvu
1.4. Equivalence and transformations......Page 0167_0001.djvu
2. The associaed Mason graph......Page 0179_0001.djvu
2.1. Topological evaluation of determinants......Page 0181_0001.djvu
2.2. Topological evaluation of cofactors......Page 0184_0001.djvu
2.3. Topological solutions of linear algebraic equations......Page 0186_0001.djvu
2.4. Equivalence and transformations......Page 0189_0001.djvu
3.1. Modifications of Coates graphs......Page 0201_0001.djvu
3.2. Modifications of Mason graphs......Page 0209_0001.djvu
4. The generation of subgraphs of a directed graph......Page 0211_0001.djvu
4.1. The generation of 1-factors and 1-factorial connections......Page 0213_0001.djvu
4.2. The generation of semifactors and k-semifactors......Page 0215_0001.djvu
5. The eigenvalue problem......Page 0218_0001.djvu
6. The matrix inversion......Page 0222_0001.djvu
Problems......Page 0228_0001.djvu
CHAPTER 4. Topological analysis of linear systems......Page 0236_0001.djvu
1. The equicofactor matrix......Page 0237_0001.djvu
2. The associated directed graph......Page 0242_0001.djvu
2.1. Directed-trees and first-order cofactors......Page 0243_0001.djvu
2.2. Directed 2-trees and second-order cofactors......Page 0256_0001.djvu
3. Equivalence and transformations......Page 0263_0001.djvu
4.1. Directed trees, 1-factors, and semi factors......Page 0274_0001.djvu
4.2. Directed 2-trees, 1-factorial connections, and 1-semifactors......Page 0278_0001.djvu
5.1. Algebraic formulation......Page 0281_0001.djvu
5.2. Iterative procedure......Page 0284_0001.djvu
5.3. Partial factoring......Page 0291_0001.djvu
6.1. Open-circuit transfer-impedance and voltage-gain functions......Page 0293_0001.djvu
6.2. Short-circuit transfer-admittance and current-gain functions......Page 0301_0001.djvu
6.3. Open-circuit impedance and short-circuit admittance matrices......Page 0306_0001.djvu
6.4. The physical significance of the associated directed graph......Page 0309_0001.djvu
6.5. Direct analysis of the associated directed graph......Page 0314_0001.djvu
7. Conclusions......Page 0323_0001.djvu
Problems......Page 0324_0001.djvu
1. The characterizations of a tree......Page 0332_0001.djvu
2. The codifying of a tree-structure......Page 0337_0001.djvu
2.1. Codification by paths......Page 0338_0001.djvu
2.2. Codification by terminal edges......Page 0340_0001.djvu
3. Decomposition into paths......Page 0342_0001.djvu
4. The Wang-algebra formulation......Page 0344_0001.djvu
4.1. The Wang algebra......Page 0345_0001.djvu
4.2. Linear dependence......Page 0346_0001.djvu
4.3. Trees and cotrees......Page 0350_0001.djvu
4.4. Multi-trees and multi-cotrees......Page 0352_0001.djvu
4.5. Decomposition......Page 0357_0001.djvu
5.1. Essential complementary partitions of a set......Page 0365_0001.djvu
5.2. Algorithm......Page 0368_0001.djvu
5.3. Decomposition without duplications......Page 0371_0001.djvu
6.1. The enumeration of major submatrices of an arbitrary matrix......Page 0377_0001.djvu
6.2. Trees and cotrees......Page 0380_0001.djvu
6.3. Directed trees and directed 2-trees......Page 0382_0001.djvu
7. Elementary transformations......Page 0385_0001.djvu
8. Hamilton circuits in directed-tree graphs......Page 0391_0001.djvu
9. Directed trees and directed Euler lines......Page 0396_0001.djvu
10. Conclusions......Page 0401_0001.djvu
Problems......Page 0402_0001.djvu
1. Existence and realization as a (p, s)-digraph......Page 0410_0001.djvu
1.1. Directed graphs and directed bipartite graphs......Page 0412_0001.djvu
1.2. Existence......Page 0413_0001.djvu
1.3. A simple algorithm for the realization......Page 0425_0001.djvu
1.4. Degree invariant transformations......Page 0431_0001.djvu
1.5. Realizability as a connected (p, s)-digraph......Page 0434_0001.djvu
2. Realizability as a symmetric (p, s)-digraph......Page 0439_0001.djvu
2.1. Existence......Page 0440_0001.djvu
2.2. Realization......Page 0445_0001.djvu
2.3. Realizability as connected, separable and nonseparable graphs......Page 0448_0001.djvu
3. Unique realizability of graphs without self-loops......Page 0452_0001.djvu
3.1. Preliminary considerations......Page 0453_0001.djvu
3.2. Unique realizability as a connected graph......Page 0455_0001.djvu
3.3. Unique realizability as a graph......Page 0458_0001.djvu
4. Existence and realization of a (p, s)-matrix......Page 0460_0001.djvu
5. Realizability as a weighted directed graph......Page 0464_0001.djvu
6. Conclusions......Page 0466_0001.djvu
Problems......Page 0467_0001.djvu
1. State equations in normal form......Page 0476_0001.djvu
2. Procedures for writing the state equations......Page 0484_0001.djvu
3. The explicit form of the state equation......Page 0492_0001.djvu
4. An alternative representation of the state equation......Page 0502_0001.djvu
5. Physical interpretations of the parameter matrices......Page 0503_0001.djvu
6. Order of complexity......Page 0511_0001.djvu
6.1. Relations between det H(s) and network determinant......Page 0516_0001.djvu
6.2. RLC networks......Page 0520_0001.djvu
6.3. Active networks......Page 0523_0001.djvu
7. Conclusions......Page 0526_0001.djvu
Problems......Page 0527_0001.djvu
1. Introduction......Page 0530_0001.djvu
2. The Bouwkamp code......Page 0533_0001.djvu
3. The electrical network associated with a dissected rectangle......Page 0536_0001.djvu
4. Characterization of the c-nets and c-digraphs......Page 0547_0001.djvu
5. Perfect subdivision of the general rectangle......Page 0553_0001.djvu
5.1. The perfect rectangles Rn......Page 0554_0001.djvu
5.2. The perfect square Sn......Page 0556_0001.djvu
5.3. Sequence of perfect squares......Page 0563_0001.djvu
6. Extension to perfect rectangular parallelepiped......Page 0565_0001.djvu
7. VLSI layout......Page 0566_0001.djvu
7.1. The zero wasted area floorplan with continuous aspect ratios......Page 0569_0001.djvu
7.2. Solving the nonlinear nodal equations......Page 0586_0001.djvu
7.3. Floorplan area optimization with constrained aspect ratio......Page 0593_0001.djvu
7.4. From digraphs to layout......Page 0608_0001.djvu
7.5. Graph-theoretic characterization of the minimum area layout......Page 0610_0001.djvu
8. Conclusions......Page 0617_0001.djvu
Problems......Page 0619_0001.djvu
1. Totally unimodular matrix......Page 0624_0001.djvu
2. Regular and binary matrices......Page 0640_0001.djvu
3. Circuit and cutset matrices......Page 0651_0001.djvu
4. 2-isomorphism......Page 0665_0001.djvu
5. Graph realization......Page 0668_0001.djvu
6. Conclusions......Page 0676_0001.djvu
Problems......Page 0677_0001.djvu
Bibliography......Page 0683_0001.djvu
Symbol index......Page 0696_0001.djvu
Subject index......Page 0702_0001.djvu