Hybrid Graph Theory and Network Analysis

✍ Scribed by Ladislav Novak, Alan Gibbons

• Publisher: Cambridge University Press
• Year: 2009
• Tongue: English
• Leaves: 187
• Series: Cambridge Tracts in Theoretical Computer Science 49
• Category: Library

✦ Synopsis

This book combines traditional graph theory with the matroid view of graphs in order to throw light on the mathematical approach to network analysis. The authors examine in detail two dual structures associated with a graph, namely circuits and cutsets. These are strongly dependent on one another and together constitute a third, hybrid, vertex-independent structure called a graphoid, whose study is here termed hybrid graph theory. This approach has particular relevance for network analysis. The first account of the subject in book form, the text includes many new results as well as the synthesizing and reworking of much research done over the past thirty years (historically, the study of hybrid aspects of graphs owes much to the foundational work of Japanese researchers). This work will be regarded as the definitive account of the subject, suitable for all working in theoretical network analysis: mathematicians, computer scientists or electrical engineers.

✦ Table of Contents

Cover......Page 1
Title......Page 4
Copyright......Page 5
Dedication......Page 6
Contents......Page 8
Preface......Page 10
1.1 Basic concepts of graphs......Page 12
1.2 Cuts and circs......Page 16
1.3 Cut and circ spaces.........Page 20
1.4 Relationships between cut and circ spaces......Page 23
1.5 Edge-separators and connectivity......Page 27
1.6 Equivalence relations among graphs......Page 30
1.7 Directed graphs......Page 33
1.8 Networks and multiports......Page 36
1.9 Kirchhoff's laws......Page 44
1.10 Bibliographic notes......Page 49
2.1 The graphoidal point of view......Page 50
2.2 Independent collections of circs and cuts......Page 53
2.3 Maximal circless and cutless sets......Page 59
2.4 Circ and cut vector spaces......Page 66
2.5 Binary graphoids and their representations......Page 73
2.6 Orientable binary graphoids and Kirchhoff's laws......Page 82
2.7 Mesh and nodal analysis.......Page 87
2.8 Bibliographic notes......Page 90
3.1 Preliminaries......Page 91
3.2 Basoids of graphs........Page 92
3.3 Transitions from one basoid to another.......Page 98
3.4 Minor with respect to a basoid.......Page 102
3.5 Principal sequence......Page 105
3.6 Principal minor and principal partition......Page 110
3.7 Hybrid rank and basic pairs of subsets......Page 113
3.8 Hybrid analysis of networks........Page 116
3.9 Procedure for finding an optimal basic pair.......Page 120
3.10 Bibliographic notes......Page 124
4.1 Diameter of a tree.......Page 126
4.2 Perfect pairs of trees......Page 130
4.3 Basoids and perfect pairs of trees.......Page 137
4.4 Superperfect pairs of trees......Page 141
4.5 Unique solvability of affine networks.......Page 145
4.6 Bibliographic notes.......Page 150
5.1 Preliminaries......Page 152
5.2 Minor with respect to a pair of trees......Page 156
5.3 Principal sequence......Page 160
5.4 The principal minor......Page 166
5.5 Hybrid pre-rank and the principal minor.......Page 170
5.6 Principal partition and Shannon's game.......Page 175
5.7 Bibliographic notes......Page 178
Bibliography......Page 179
Index......Page 185