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 Σ is a pair (G, σ) that consists of a graph G = (V, E) and a sign mapping or signature σ from E to the sign group {+,−}. The graph may have loops and multiple edges as well as half-edges (with only one endpoint) and loose edges (with no endpoints). Half and loose edges do not receive signs. (In the terminology of the article on graphs, it is a multigraph, but we say graph because in signed graph theory it is usually unnatural to restrict to simple graphs.) The sign of a circle (this is the edge set of a simple cycle) is defined to be the product of the signs of its edges; in other words, a circle is positive if it contains an even number of negative edges and negative if it contains an odd number of negative edges. The fundamental fact about a signed graph is the set of positive circles, denoted by B(Σ). A signed graph, or a subgraph or edge set, is called balanced if every circle in it is positive (and it contains no half-edges). Two fundamental questions about a signed graph are: Is it balanced? What is the largest size of a balanced edge set in it? The first question is not difficult; the second is computationally intractable (technically, it is NP-hard).

Signed graphs were first introduced by Harary to handle a problem in social psychology (Cartwright and Harary, 1956). They have been rediscovered many times because they come up naturally in many unrelated areas. For instance, they enable one to describe and analyze the geometry of subsets of the classical root systems. They appear in topological graph theory and group theory. They are a natural context for questions about odd and even cycles in graphs. They appear in computing the ground state energy in the non-ferromagnetic Ising model; for this one needs to find a largest balanced edge set in Σ. They have been applied to data classification in correlation clustering.

Read more about Signed Graph:  Examples, Adjacency Matrix, Orientation, Incidence Matrix, Switching, Fundamental Theorem, Frustration, Matroid Theory, Other Kinds of "signed Graph", Generalizations

Other articles related to "signed graph, graph":

Signed Graph - Generalizations
... A signed graph is a special kind of gain graph, where the gain group has order 2 ... The pair (G, B(G)) is a special kind of biased graph ...
Unimodular Matrix - Total Unimodularity - Common Totally Unimodular Matrices
... The unoriented incidence matrix of a bipartite graph, which is the coefficient matrix for bipartite matching, is totally unimodular (TU) ... (The unoriented incidence matrix of a non-bipartite graph is not TU.) More generally, in the appendix to a paper by Heller and Tompkins, A.J ... later that these conditions define an incidence matrix of a balanced signed graph thus, this example says that the incidence matrix of a signed graph is totally unimodular if the signed graph is ...

Famous quotes containing the words graph and/or signed:

    In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.
    W.N.P. Barbellion (1889–1919)

    You watched and you saw what happened and in the accumulation of episodes you saw the pattern: Daddy ruled the roost, called the shots, made the money, made the decisions, so you signed up on his side, and fifteen years later when the women’s movement came along with its incendiary manifestos telling you to avoid marriage and motherhood, it was as if somebody put a match to a pile of dry kindling.
    Anne Taylor Fleming (20th century)