2 - Independence Structures
Published online by Cambridge University Press: 20 March 2010
Summary
Independence is a unifying concept for linear algebra and graphs. A deep generalization of both through this unification, is contained in the notion of graphoids. Every graph can be seen as an interpretation of a graphoid in a particular ‘coordinate system’, called a 2-complete basis. From this prospect, a graphoid is an essential, coordinate free, geometrical notion for which each associated graph, if it exists, is just a particular view of the same generality. The concept of a graphoid can also be seen as a pair of set systems (dual matroids) whose members are called circuits and cutsets. The set of all circuits (cutsets) together with all their distinct unions we call a circ (cut) space. In this chapter, in the context of circuits and cutsets, we concentrate on two concepts of independence within graphs and graphoids. We first introduce independent collections of circuits and cutsets and then we use this concept to define independent edge subsets, that is, circuit-less and cutset-less subsets. Prom this point on, we take circuits and cutsets as primary notions. This material may be seen as a bridge between traditional graph theory and matroid theory. We also give a brief overview of properties of graphoids and methods in topological analysis of networks.
The graphoidal point of view
The space of all graphs can be divided into disjoint classes such that two graphs belong to the same class if they are 2-isomorphic.
- Type
- Chapter
- Information
- Hybrid Graph Theory and Network Analysis , pp. 39 - 79Publisher: Cambridge University PressPrint publication year: 1999