1 - Two Dual Structures of a Graph
Published online by Cambridge University Press: 20 March 2010
Summary
The concept of graph inherently includes two dual structures, one based on circuits and the other based on cutsets. These two structures are strongly interdependent. They constitute the so-called graphoidal structure which is a deep generalization of the concept of graph and comes from matroid theory. The main difference between graph and graphoid is that the latter requires no concept of vertex while the first presumes vertex as a primary notion. After some bridging material, our approach will be entirely vertex-independent. We shall concentrate on the hybrid aspects of graphs that naturally involve both dual structures. Because of this approach, the material of this text is located somewhere between graph theory and the theory of matroids. This enables us to combine the advantages of both an intuitive view of graphs and formal mathematical tools from matroid theory.
Starting with the classical definition of a graph in terms of vertices and edges we define circs and cuts and then circuits and cutsets. In this context, a circuit (respectively, cutset) is a minimal circ (cut) in the sense that no proper subset of it is also a circ (cut). We consider some collective algebraic properties and mutual relationships of circs and cuts. Vertex and edge-separators are introduced and through these we define various kinds of connectivity. The immediate thrust is towards a vertex-independent description of graphs, so that later all theorems and propositions will be vertex-independent.
The last two sections of the chapter are devoted to the notions of multiports and Kirchhoff's laws which are basic concepts in network analysis.
- Type
- Chapter
- Information
- Hybrid Graph Theory and Network Analysis , pp. 1 - 38Publisher: Cambridge University PressPrint publication year: 1999