Gain graph
Encyclopedia
A gain graph is a graph
whose edges are labelled "invertibly", or "orientably", by elements of a group
G. This means that, if an edge e in one direction has label g (a group element), then in the other direction it has label g −1. The label function φ therefore has the property that it is defined differently, but not independently, on the two different orientations, or directions, of an edge e. The group G is called the gain group, φ is the gain function, and the value φ(e) is the gain of e (in some indicated direction). A gain graph is a generalization of a signed graph, where the gain group G has only two elements. See Zaslavsky (1989, 1991).
A gain should not be confused with a weight on an edge, whose value is independent of the orientation of the edge.
Some reasons to be interested in gain graphs are their connections to network flow
theory in combinatorial optimization
, to geometry
, and to physics
.
Gain graphs used in topological graph theory
as a means to construct graph embedding
s in surfaces are known as "voltage graph
s" (Gross 1974; Gross and Tucker 1977). The term "gain graph" is more usual in other contexts, e.g., biased graph
theory and matroid theory. The term group-labelled graph has also been used, but it is ambiguous since "group labels" may be—and have been—treated as weights.
Since much of the theory of gain graphs is a special case of that of biased graphs (and much of the theory of biased graphs is a generalization of that of gain graphs), the reader should refer to the article on biased graph
s for more information and examples.
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
whose edges are labelled "invertibly", or "orientably", by elements of a group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
G. This means that, if an edge e in one direction has label g (a group element), then in the other direction it has label g −1. The label function φ therefore has the property that it is defined differently, but not independently, on the two different orientations, or directions, of an edge e. The group G is called the gain group, φ is the gain function, and the value φ(e) is the gain of e (in some indicated direction). A gain graph is a generalization of a signed graph, where the gain group G has only two elements. See Zaslavsky (1989, 1991).
A gain should not be confused with a weight on an edge, whose value is independent of the orientation of the edge.
Some reasons to be interested in gain graphs are their connections to network flow
Network flow
In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in Operations Research, a directed graph is called a network, the vertices are called nodes and the edges are...
theory in combinatorial optimization
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
, to geometry
Geometry
Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....
, and to physics
Physics
Physics is a natural science that involves the study of matter and its motion through spacetime, along with related concepts such as energy and force. More broadly, it is the general analysis of nature, conducted in order to understand how the universe behaves.Physics is one of the oldest academic...
.
- The mathematics of a network with gains, or generalized network, is connected with the frame matroidBiased graphIn mathematics, a biased graph is a graph with a list of distinguished circles , such that if two circles in the list are contained in a theta graph, then so is the third circle of the theta graph...
of the gain graph.
- Suppose we have some hyperplaneHyperplaneA hyperplane is a concept in geometry. It is a generalization of the plane into a different number of dimensions.A hyperplane of an n-dimensional space is a flat subset with dimension n − 1...
s in R n given by equations of the form xj = g xi . The geometry of the hyperplanes can be treated by using the following gain graph: The vertex set is {1,2,...,n}. There is an edge ij with gain g (in the direction from i to j) for each hyperplane with equation xj = g xi . These hyperplanes are treated through the frame matroid of the gain graph (Zaslavsky 2003).
- Or, suppose we have hyperplanes given by equations of the form xj = xi + g. The geometry of these hyperplanes can be treated by using the gain graph with the same vertex set and an edge ij with gain g (in the direction from i to j) for each hyperplane with equation xj = xi + g. These hyperplanes are studied via the lift matroidBiased graphIn mathematics, a biased graph is a graph with a list of distinguished circles , such that if two circles in the list are contained in a theta graph, then so is the third circle of the theta graph...
of the gain graph (Zaslavsky 2003).
- Suppose the gain group has an actionGroup actionIn algebra and geometry, a group action is a way of describing symmetries of objects using groups. The essential elements of the object are described by a set, and the symmetries of the object are described by the symmetry group of this set, which consists of bijective transformations of the set...
on a set Q. Assigning an element si of Q to each vertex gives a state of the gain graph. An edge is satisfied if, for each edge ij with gain g (in the direction from i to j), the equation sj = si g is satisfied; otherwise it is frustrated. A state is satisfied if every edge is satisfied. In physics this corresponds to a ground state (a state of lowest energy), if such a state exists, but it may not exist. An important problem in physics, especially in the theory of spin glassSpin glassA spin glass is a magnet with frustrated interactions, augmented by stochastic disorder, where usually ferromagnetic and antiferromagnetic bonds are randomly distributed...
es, is to determine a state with the fewest frustrated edges.
Gain graphs used in topological graph theory
Topological graph theory
In mathematics topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces. It also studies immersions of graphs....
as a means to construct graph embedding
Graph embedding
In topological graph theory, an embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs are associated to edges in such a way that:...
s in surfaces are known as "voltage graph
Voltage graph
In graph-theoretic mathematics, a voltage graph is a directed graph whose edges are labelled invertibly by elements of a group. It is formally identical to a gain graph, but it is generally used in topological graph theory as a concise way to specify another graph called the derived graph of the...
s" (Gross 1974; Gross and Tucker 1977). The term "gain graph" is more usual in other contexts, e.g., biased graph
Biased graph
In mathematics, a biased graph is a graph with a list of distinguished circles , such that if two circles in the list are contained in a theta graph, then so is the third circle of the theta graph...
theory and matroid theory. The term group-labelled graph has also been used, but it is ambiguous since "group labels" may be—and have been—treated as weights.
Since much of the theory of gain graphs is a special case of that of biased graphs (and much of the theory of biased graphs is a generalization of that of gain graphs), the reader should refer to the article on biased graph
Biased graph
In mathematics, a biased graph is a graph with a list of distinguished circles , such that if two circles in the list are contained in a theta graph, then so is the third circle of the theta graph...
s for more information and examples.