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. In the area of graph theory in mathematics, a signed graph is a graph in which each edge has a positive or negative sign. A signed graph is balanced if the product of edge signs around every cycle is positive. Three fundamental questions about a signed graph are: Is it balanced? What is the largest size of a balanced edge set in it? What is the smallest number of vertices that must be deleted to make it balanced? The first question is easy to solve quickly; the second and third are computationally intractable (technically, they are NP-hard). The name 'signed graph' and the notion of balance appeared first in a mathematical paper of Frank Harary in 1953. Dénes Kőnig had already studied equivalent notions in 1936 under a different terminology but without recognizing the relevance of the sign group.At the Center for Group Dynamics at the University of Michigan, Dorwin Cartwright and Harary generalized Fritz Heider's psychological theory of balance in triangles of sentiments to a psychological theory of balance in signed graphs. Signed graphs 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. The adjacency matrix of a signed graph Σ on n vertices is an n × n matrix A(Σ). It has a row and column for each vertex. The entry avw in row v and column w is the number of positive vw edges minus the number of negative vw edges. On the diagonal, avv = 0 if there are no loops or half-edges; the correct definition when such edges exist depends on the circumstances. A signed graph is oriented when each end of each edge is given a direction, so that in a positive edge the ends are both directed from one endpoint to the other, and in a negative edge either both ends are directed outward, to their own vertices, or both are directed inward, away from their vertices. Thus, an oriented signed graph is the same as a bidirected graph. (It is very different from a signed digraph.) The (more correctly, 'an') incidence matrix of a signed graph with n vertices and m edges is an n × m matrix, with a row for each vertex and a column for each edge. It is obtained by orienting the signed graph in any way. Then its entry ηij is +1 if edge j is oriented into vertex i, −1 if edge j is oriented out of vertex i, and 0 if vertex i and edge j are not incident. This rule applies to a link, whose column will have two nonzero entries with absolute value 1, a half-edge, whose column has a single nonzero entry +1 or −1, and a loose edge, whose column has only zeroes. The column of a loop, however, is all zero if the loop is positive, and if the loop is negative it has entry ±2 in the row corresponding to its incident vertex. Any two incidence matrices are related by negating some subset of the columns. Thus, for most purposes it makes no difference which orientation we use to define the incidence matrix, and we may speak of the incidence matrix of Σ without worrying about exactly which one it is.