Cycle Space - The Integral Cycle Space

The Integral Cycle Space

The foregoing development can be carried out over the integers, Z. The integral edge space is the abelian group ZE of functions from the edge set E to the integers. It is necessary (for the notation) to choose an arbitrary orientation of the graph in order to define the cycle space, but the definition does not depend on that choice. An integral cycle is a function such that the sum of values on edges oriented into a vertex x equals the sum of values on edges oriented out of x, for every vertex x. The set of integral cycles is a subgroup of the integral edge space. A cycle that never takes the value zero is called nowhere zero.

Reversing the orientation of an edge negates the value of a cycle on that edge. It is in this sense that the theory is independent of the arbitrary orientation. Given any one cycle, the orientation can be chosen so that cycle takes only nonnegative values.

An integral cycle whose maximum absolute value on any edge is less than k, a positive integer, is sometimes called a k-flow on G. W.T. Tutte developed an extensive theory of nowhere-zero k-flows that is in some ways dual to that of graph coloring.

Read more about this topic:  Cycle Space

Famous quotes containing the words integral, cycle and/or space:

    Make the most of your regrets; never smother your sorrow, but tend and cherish it till it come to have a separate and integral interest. To regret deeply is to live afresh.
    Henry David Thoreau (1817–1862)

    The cycle of the machine is now coming to an end. Man has learned much in the hard discipline and the shrewd, unflinching grasp of practical possibilities that the machine has provided in the last three centuries: but we can no more continue to live in the world of the machine than we could live successfully on the barren surface of the moon.
    Lewis Mumford (1895–1990)

    Though seas and land be ‘twixt us both,
    Our faith and troth,
    Like separated souls,
    All time and space controls:
    Above the highest sphere we meet
    Unseen, unknown, and greet as angels greet.
    Richard Lovelace (1618–1658)