{
  "id": "enwiki-001283605114",
  "slug": "gain-graph",
  "title": "Gain graph",
  "qid": "",
  "lead": "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 &minus;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.",
  "body": "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 &nbsp;&minus;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. ==Applications== 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&nbsp; n given by equations of the form x j = g&nbsp;x i . 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 x j = g x i . 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 x j = x i + 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 x j = x i + g. These hyperplanes are studied via the lift matroid of the gain graph (Zaslavsky 2003). Suppose the gain group has an action on a set Q. Assigning an element s i 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 s j = s i &nbsp;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. An important problem in physics, especially in the theory of spin glasses, is to determine a state with the fewest frustrated edges. ==Related concepts== Gain graphs used in topological graph theory as a means to construct graph embeddings in surfaces are known as \"voltage graphs\" (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&mdash;and have been&mdash;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. ==References== Jonathan L. Gross (1974), Voltage graphs. Discrete Mathematics, Vol. 9, pp.&nbsp;239&ndash;246. J.L. Gross and T.W. Tucker (1977), Generating all graph coverings by permutation voltage assignments. Discrete Mathematics, Vol. 18, pp.&nbsp;273&ndash;283. Thomas Zaslavsky (1989), Biased graphs. I. Bias, balance, and gains. Journal of Combinatorial Theory, Series B, Vol. 47, 32&ndash;52. Thomas Zaslavsky (1991), Biased graphs. II. The three matroids. Journal of Combinatorial Theory, Series B, Vol. 51, 46&ndash;72. Thomas Zaslavsky (1999). A mathematical bibliography of signed and gain graphs and allied areas. Electronic Journal of Combinatorics, Dynamic Surveys in Combinatorics, #DS8. Thomas Zaslavsky (2003), Biased graphs IV: Geometrical realizations. Journal of Combinatorial Theory, Series B, Vol. 89, no. 2, pp.&nbsp;231&ndash;297.",
  "categories": [
    "23118434",
    "23603337",
    "29176322",
    "29176491"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1283605114",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1743598638.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001283605114",
    "type": "webpage",
    "title": "Gain graph",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/gain-graph",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          17
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          17
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001283605114",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1283605114",
    "note": "Immutable snapshot enwiki-001283605114"
  }
}