Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Signed graph
open-in-new
<p>In the area of <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a> in <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, a signed graph is a graph in which each edge has a positive or negative sign. </p><p>A signed graph is balanced if the product of edge signs around every <a href="/facts/Cycle_(graph_theory)/Is44edrv">cycle</a> is positive. The name "signed graph" and the notion of balance appeared first in a mathematical paper of <a href="/facts/Frank_Harary/3J2P7l4w">Frank Harary</a> in 1953. <a href="/facts/D%C3%A9nes_K%C5%91nig/wNMBmsYK">Dénes Kőnig</a> had already studied equivalent notions in 1936 under a different terminology but without recognizing the relevance of the sign group. At the Center for <a href="/facts/Group_dynamics/Jo0C0Dfa">Group Dynamics</a> at the <a href="/facts/University_of_Michigan/6e1Ea5xh">University of Michigan</a>, <a href="/facts/Dorwin_Cartwright/yCC972M6">Dorwin Cartwright</a> and Harary generalized <a href="/facts/Fritz_Heider/Ij3CzkEH">Fritz Heider</a>'s psychological theory of <a href="/facts/Balance_theory/D40nqJ69">balance</a> in triangles of sentiments to a psychological theory of balance in signed graphs. </p><p>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 <a href="/facts/Root_system/TFaEdwMU">root systems</a>. They appear in <a href="/facts/Topological_graph_theory/TAQ2DdVB">topological graph theory</a> and <a href="/facts/Group_theory/NfowcI5H">group theory</a>. They are a natural context for questions about odd and even <a href="/facts/Cycle_(graph_theory)/Is44edrv">cycles</a> in graphs. They appear in computing the <a href="/facts/Ground_state/ML7cfCug">ground state</a> energy in the non-ferromagnetic <a href="/facts/Ising_model/lvBpj2h1">Ising model</a>; for this one needs to find a largest balanced edge set in Σ. They have been applied to data classification in <a href="/facts/Correlation_clustering/15lt5A49">correlation clustering</a>. </p>