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.
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).
Signed graphs appeared first in a mathematical paper of Frank Harary in 1953. 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 balanced 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.
...
Wikipedia