Издательство Cambridge University Press, 1999, -187 pp.
This research monograph is conceed with two dual structures in graphs. These structures, one based on the concept of a circuit and the other on the concept of a cutset are strongly interdependent and constitute a hybrid structure called a graphoid. This approach to graph theory dealing with graphoidal structures we call hybrid graph theory. A large proportion of our material is either new or is interpreted from a fresh viewpoint. Hybrid graph theory has particular relevance to the analysis of (lumped) systems of which we might take electrical networks as the archetype. Electrical network analysis was one of the earliest areas of application of graph theory and it was essentially out of developments in that area that hybrid graph theory evolved. The theory emphasises the duality of the circuit and cutset spaces and is essentially a vertex independent view of graphs. In this view, a circuit or a cutset is a subset of the edges of a graph without reference to the endpoints of the edges. This naturally leads to working in the domain of graphoids which are a generalisation of graphs. In fact, two graphs have the same graphoid if they are 2-isomorphic and this is equivalent to saying that both graphs (within a one-to-one correspondence of edges) have the same set of circuits and cutsets.
Historically, the study of hybrid aspects of graphs owes much to the foundational work of Japanese researchers dating from the late 1960's. Here we omit the names of individual researchers, but they may be readily identified through our bibliographic notes.
First two chapters could be seen as a bridge between traditional graph theory and the graphoidal perspective. They may be also taken as a kind of separate subtext. The proofs to be found in these pages are usually different from those of the traditional literature. The central bulk (Chapers 3, 4, and 5) of the text is then pure hybrid graph theory. It may be noted that the presentation of this material is such that it is easily viewed from a matroidal perspective. The last sections of Chapters 1 to 4 are devoted to fundamental aspects of network analysis in a form which is rather formal. Such an approach could be suitable for readers who appreciate an abstract and formal point of view in traditional engineering texts such as engineering theorists, computer scientists and mathematicians.
The body of theorems and propositions developed in the text provides a solid basis for the correctness of algorithms presented. Although the question of their complexity has not been addressed in detail, wherever the quantity of output is polynomially bound, the algorithms clearly run in low order polynomial time, mostly involving elementary graph operations such as the removal or contraction of edges of the graph.
We have adopted the practice of only referring to sources of material within the Bibliographic notes which are appended to each chapter. Our mathematical notation is generally standard although we have adopted the local convention of using bold face type to denote sets of sets and plain font for other sets.
Two Dual Structures of a Graph.
Independence Structures.
Basoids.
Pairs of Trees.
Maximally Distant Pairs of Trees.
This research monograph is conceed with two dual structures in graphs. These structures, one based on the concept of a circuit and the other on the concept of a cutset are strongly interdependent and constitute a hybrid structure called a graphoid. This approach to graph theory dealing with graphoidal structures we call hybrid graph theory. A large proportion of our material is either new or is interpreted from a fresh viewpoint. Hybrid graph theory has particular relevance to the analysis of (lumped) systems of which we might take electrical networks as the archetype. Electrical network analysis was one of the earliest areas of application of graph theory and it was essentially out of developments in that area that hybrid graph theory evolved. The theory emphasises the duality of the circuit and cutset spaces and is essentially a vertex independent view of graphs. In this view, a circuit or a cutset is a subset of the edges of a graph without reference to the endpoints of the edges. This naturally leads to working in the domain of graphoids which are a generalisation of graphs. In fact, two graphs have the same graphoid if they are 2-isomorphic and this is equivalent to saying that both graphs (within a one-to-one correspondence of edges) have the same set of circuits and cutsets.
Historically, the study of hybrid aspects of graphs owes much to the foundational work of Japanese researchers dating from the late 1960's. Here we omit the names of individual researchers, but they may be readily identified through our bibliographic notes.
First two chapters could be seen as a bridge between traditional graph theory and the graphoidal perspective. They may be also taken as a kind of separate subtext. The proofs to be found in these pages are usually different from those of the traditional literature. The central bulk (Chapers 3, 4, and 5) of the text is then pure hybrid graph theory. It may be noted that the presentation of this material is such that it is easily viewed from a matroidal perspective. The last sections of Chapters 1 to 4 are devoted to fundamental aspects of network analysis in a form which is rather formal. Such an approach could be suitable for readers who appreciate an abstract and formal point of view in traditional engineering texts such as engineering theorists, computer scientists and mathematicians.
The body of theorems and propositions developed in the text provides a solid basis for the correctness of algorithms presented. Although the question of their complexity has not been addressed in detail, wherever the quantity of output is polynomially bound, the algorithms clearly run in low order polynomial time, mostly involving elementary graph operations such as the removal or contraction of edges of the graph.
We have adopted the practice of only referring to sources of material within the Bibliographic notes which are appended to each chapter. Our mathematical notation is generally standard although we have adopted the local convention of using bold face type to denote sets of sets and plain font for other sets.
Two Dual Structures of a Graph.
Independence Structures.
Basoids.
Pairs of Trees.
Maximally Distant Pairs of Trees.