3 - Basoids

Summary

In this chapter maximal edge subsets that are both circuit-less and cutsetless (which we call basoids) and the related concepts of principal minor and principal partition of a graph are considered. The fact that basoids may have different cardinalities provides a rich structure which is described through several propositions. Transitions from one basoid to another (which provides a basis for augmenting basoids in turn) and the concept of a minor of a graph with respect to a dyad (a maximum cardinality basoid) are also investigated in detail. It is shown that there exists a unique minimal minor with respect to every dyad of a graph G.This edge subset, called the principal minor and its dual called the principal cominor, define a partition of the edge set of Gcalled the principal partition. The hybrid rank of a graph is defined to be the cardinality of a dyad of the graph. This is a natural extension of the definitions of rank and corank of a graph, defined as the cardinalities of a maximum circuit-less subset and a maximum cutset-less subset of the graph, respectively. In the last section of this chapter an application to hybrid topological analysis of networks is considered. An algorithm for finding a maximum cardinality topologically complete set of network variables is also described.

The material of this chapter is general in the sense that it can be easily extended from graphs to matroids. To ensure this generality, the Painting Theorem, the matroidal version of the Orthogonality Theorem as well as the Circuit and the Cutset axioms are widely used to prove propositions.