0 Replies - 9320 Views - Last Post: 08 September 2013 - 02:41 PM Rate Topic: -----

#1 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10397
  • View blog
  • Posts: 38,475
  • Joined: 27-December 08

Algebraic Graph Theory- Vertex and Edge Spaces

Posted 08 September 2013 - 02:41 PM

Algebraic Graph Theory- Vertex and Edge Spaces

This tutorial will introduce Algebraic Graph Theory, covering vector spaces related to vertices, edges, cycles, and cuts. Algebraic Graph Theory can be studied either in the context of Linear Algebra (as is discussed in this tutorial) or in the context of Abstract Algebra with Group Theory. Basic graph theory knowledge is assumed. If you do not already have a graph theory background, check out this tutorial for a good starting point.

Vertex Space and Edge Space
Vertex Space and Edge Space are considered to be vector spaces. They are defined over the field B = {0, 1} with operations of vector addition and scalar multiplication. The elements of Vertex and Edge Spaces are subsets of the vertex and edge sets respectively. The operations of vector addition and scalar multiplication are defined differently than in other vector spaces like Rn.

Consider scalar multiplication, where x is an element of the appropriate vector space:
  • 0 * x = {}
  • 1 * x = x


Vector addition is defined for Vertex and Edge Spaces using the symmetric difference operation. Note that the symmetric difference of two sets is defined: (A - B) U (B - A).

Now consider two distinct elements from either Vertex Space or Edge Space: {x1} and {x2}. That is, x1 and x2 are both vertices (or edges, if referring to edge space). Adding these elements produces the set: {x1, x2}.

Expanding this out, it is easy to see how the null set can only be obtained from a linear combination of elements whose coefficients are 0.

Now consider V = {v1, v2, ..., vn} with x1 = {v1, v2} and x2 = {v2, v3}.

Thus, 1 * x1 + 1 * x2 is calculated by the symmetric difference. The first part (x1 - x2) subtracts common elements found in both sets from x1. Thus, 1 * x1 + 1 * x2 = {v1} U {v3} = {v1, v3}.

Notice how the symmetric difference operation for vector addition removed the common element in both sets- v2. The symmetric difference operation for vector addition, coupled with use of a finite field, keeps both vector spaces finite. That is, since common elements of two vectors will be removed, no vector can have more than |V| or |E| elements for Vertex and Edge spaces respectively. Since the field |B| = 2, there are 2|V| or 2|E| possible vectors.

The operation of vector addition has another interesting consequence- each vector is its own additive inverse. Since a vector is equivalent to itself, v + v = {} U {} = {}. Thus, {} is the zero-vector associated with Vertex and Edge spaces.

The other properties of vector spaces can easily be verified for Vertex and Edge Spaces, but will be left to the reader.

Cycle Space
The Cycle Space of a Graph is a subspace of Edge Space. It is the smallest possible set of edge disjoint cycles and the null set. To understand why all the cycles in the Cycle Space don't share edges, let's examine the subspace proof.

In order to show that a subset of a vector space is a subspace, it is necessary to show three conditions: the subset contains the zero-vector, closure under scalar multiplication, and closure under vector addition.

Consider scalar multiplication. Since the field that Edge Space (and thus Cycle Space) is defined over is {0, 1}, it is easy to check both those values:
  • 0 * x = {}, which shows that the zero-vector (the null set) is in Cycle Space
  • 1 * x = x, which is the identity.


Thus, Cycle Space is closed under scalar multiplication.

Now consider vector addition. Remember that since Cycle Space is a subspace of Edge Space, the operation of vector addition is defined as the symmetric difference of the two vectors. Thus, two cycles (or unions of cycles) that don't share edges will not share edges under vector addition. The symmetric difference operator will simply act as a union operator. However, if there are two vectors in the Cycle Space: x1 and x2, such that x1 and x2 share edges, then they also share cycles in common. Thus, the operation x1 + x2 will remove the common edges and thus the common cycles. Thus, x1 + x2 returns the union of two cycles that don't share edges.

Therefore, since Cycle Space contains the zero-vector (the null set), is closed under vector addition, and is closed under scalar multiplication, it is a vector space and subspace of Edge Space.


Now that Cycle Space has been proven to be a subspace, let's look at an example. Consider the Wheel graph on four vertices. It is displayed in the image, with its cycle space below it. Note again that different graphs have different cycle spaces. Notice the null set, the four instances of C3, as well as the three instances of C4. The C4 graphs were obtained by taking the symmetric difference of each pair of of the C3 graphs. Since in simple graphs, no cycle can have fewer than 3 edges, the C3 cycles are the starting points for this cycle space. As a vector space is a set of vectors, no duplicate cycles were included. Also note that W4 is not in its own cycle space.
Attached Image


Next, let's introduce fundamental cycles. First, let's define a fundamental cycle. Consider G to be connected and T to be a spanning tree on G. A fundamental cycle is a cycle created by adding an edge e to T, where e is in G but not in T.

In fact, no fundamental cycle can be generated from linear combinations of other fundamental cycles, as the other fundamental cycles wouldn't share the added edge in common. Therefore, the set of fundamental cycles is linearly independent, and it is called the Fundamental System of Cycles (with respect to G). Notice as well that fundamental cycles are not unions of edge-disjoint cycles.

Now consider an arbitrary cycle C of the Cycle Space. It can be described only using fundamental cycles. Since C is a cycle, it has edges that do not appear in T. Therefore, a linear combination of a subset of the fundamental system of cycles is sufficient to generate C. In other words, if C = Sum_{i} ai Ci, where ai = 1 iff Ci contains a non-tree edge that overlaps with C. Otherwise, ai = 0.

Thus, the fundamental system of cycles for a connected graph can be considered a basis for its cycle space. This can actually be expanded out for a non-connected graph G as well. Let Bi represent the fundamental system of cycles for each connected component in G. Thus, the union of each Bi constitutes a basis for G.

The fundamental system of cycles can for W4 is pictured below. The red edges indicate the edges in W4 that are not in its spanning tree, and so set of the cycles formed by the addition of these red edges constitutes a fundamental system of cycles. Note that there are multiple possible spanning trees for W4, so the fundamental system of circuits may vary if a different spanning tree is chosen.
Attached Image


Understanding Cycle Space bases is important, as it actually has applications in determining the planarity of a graph. Mac Lane's planarity criterion state that an undirected graph is planar iff each the basis for the cycle space has two vectors containing all the edges in the graph. In fact, it is easy to see that W4 is planar at a glance. It is drawn in two dimensions with no overlapping edges. A basis for W4's cycle space that satisfies Mac Lane's criterion would be: { {C-A, A-D, D-B, B-C}, {A-D, D-B, A-B} }.

Other applications of cycle spaces include networking theory for computing and distributed systems, scheduling, and economics. Cycle spaces are also applied in circuit theory within certain aspects of physics, computer engineering, and computer science.


Cut Space
Cut Space is another subspace of Edge Space. The proof of this is nearly identical to that of Cycle Space, as are a number of the theorems. Rather than describing cycles in a graph G that don't share any edges, Cut Space describes all the edge-disjoint cuts of G. That is, if the removal of a set of edges from G partitions a component in G into two components, that set of edges is called a cut set. The Cut Space of a Graph contains all edge-disjoint cuts and the null set (the zero-vector).

Consider again the Graph W4, with its cut space below. Each element below, except for the null set, describes a set of edges that when removed from W4, partition the graph into multiple components. Since each vertex has a valency (or degree) of 3, a minimum of 3 edges must be removed from W4 to partition it into two components.
Attached Image

Similarly, a Cut Space contains Fundamental Cuts and a Fundamental System of Cuts. Given a spanning tree T on graph G, the removal of any edge in T constitutes a fundamental cut, since T is immediately partitioned into two components. The Fundamental System of Cuts consists of all subsets of E(T) minus a single edge. So if |E(T)| = n, then there are n edge sets in the fundamental system of cuts, each with n-1 elements. Each edge removed from T creates an additional component. Thus, removing all the edges in T produces |V| components, where |V| is the number of vertices in G. Just as the Fundamental System of Cycles forms a basis for the Cycle Space, the Fundamental System of Cuts forms a basis for the Cut Space of the graph.

For W4, any of the cuts with three edges can be used to find a fundamental system of cuts. As an example, the cut {C-A, A-D, A-B} will be used. Thus, removing any arbitrary edge produces a fundamental cut. So the fundamental system of cuts consists of { {C-A, A-D}, {A-D, A-B}, {A-C, A-B} }.

Cut Space has applications in networking theory, including flow maximization (such as with the Ford-Fulkerson algorithm). It also comes into play with Electricity and Magnetism, specifically in circuit theory and Kirchhoff's laws.

Conclusion
This tutorial was designed to provide an introduction to the important vector spaces used in graph theory. Each of these vector spaces can be studied further using a linear algebra toolset to discuss rank, nullity, dimension, linear transformations, eigentheory, and more.

Is This A Good Question/Topic? 3
  • +

Page 1 of 1