Gain graph

Gain graph

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.

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.

* The mathematics of a network with gains, or generalized network, is connected with the frame matroid of the gain graph.

* Suppose we have some hyperplanes 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.)

* 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 matroid of the gain graph.)

* Suppose the gain group has an action 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 glasses, is to determine a state with the fewest frustrated edges.

Gain graphs used in topological graph theory as a means to construct graph embeddings in surfaces are known as "voltage graphs". 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 graphs for more information and examples.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Gain — For other uses, see Gain (disambiguation). In electronics, gain is a measure of the ability of a circuit (often an amplifier) to increase the power or amplitude of a signal from the input to the output. It is usually defined as the mean ratio of… …   Wikipedia

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia

  • Biased graph — In mathematics, a biased graph is a graph with a list of distinguished circles (edge sets of simple cycles), such that if two circles in the list are contained in a theta graph, then so is the third circle of the theta graph. A biased graph is a… …   Wikipedia

  • Signed graph — In the area of graph theory in mathematics, a signed graph is a graph in which each edge has a positive or negative sign.Formally, a signed graph Sigma; is a pair ( G , sigma;) that consists of a graph G = ( V , E ) and a sign mapping or… …   Wikipedia

  • Voltage graph — A voltage graph is a graph whose edges are labelled invertibly by elements of a group. It is formally identical to a gain graph, but it is generally used as a concise way to specify another graph called the derived graph of the voltage graph.… …   Wikipedia

  • Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… …   Wikipedia

  • Signal-flow graph — A signal flow graph (SFG) is a special type of block diagram[1] and directed graph consisting of nodes and branches. Its nodes are the variables of a set of linear algebraic relations. An SFG can only represent multiplications and additions.… …   Wikipedia

  • Asymptotic gain model — The asymptotic gain model [Middlebrook, RD: Design oriented analysis of feedback amplifiers ; Proc. of National Electronics Conference, Vol. XX, Oct. 1964, pp. 1 4] G {infin} T} . while in classical feedback theory, in terms of the open loop gain …   Wikipedia

  • List of mathematics articles (G) — NOTOC G G₂ G delta space G networks Gδ set G structure G test G127 G2 manifold G2 structure Gabor atom Gabor filter Gabor transform Gabor Wigner transform Gabow s algorithm Gabriel graph Gabriel s Horn Gain graph Gain group Galerkin method… …   Wikipedia

  • Matroid — In combinatorics, a branch of mathematics, a matroid (  /ˈmeɪ …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”