Frustration
Give each vertex a value of +1 or −1; we call this a state of Σ. An edge is called satisfied if it is positive and both endpoints have the same value, or it is negative and the endpoints have opposite values. The smallest number of frustrated edges in any state is called the frustration index (or line index of balance) of Σ. Finding the frustration index is hard, in fact, it is NP-hard. One can see this by observing that frustration index of an all-negative signed graph is equivalent to the maximum cut problem in graph theory, which is NP-hard. The reason is that the frustration index equals the smallest number of edges whose negation (or, equivalently, deletion; a theorem of Harary) makes Σ balanced. (This can be proved easily by switching.)
The frustration index is important in a model of spin glasses, the mixed Ising model. In this model, the signed graph is fixed. A state consists of giving a "spin", either "up" or "down", to each vertex. We think of spin up as +1 and spin down as −1. Thus, each state has a number of frustrated edges. The energy of a state is larger when it has more frustrated edges, so a ground state is a state with the fewest frustrated energy. Thus, to find the ground state energy of Σ one has to find the frustration index.
Read more about this topic: Signed Graph
Famous quotes containing the word frustration:
“The difference between tragedy and comedy is the difference between experience and intuition. In the experience we strive against every condition of our animal life: against death, against the frustration of ambition, against the instability of human love. In the intuition we trust the arduous eccentricities we’re born to, and see the oddness of a creature who has never got acclimatized to being created.”
—Christopher Fry (b. 1907)
“To achieve the larger goal of teaching her children consideration of others, a mother can tolerate some frustration of her own wishes, she can delay having what she wants, she can be flexible enough to compromise. And this is exactly what her child must also learn: that it is possible to survive frustration, it is possible to wait for what he wants, it is possible to compromise without capitulating.”
—Elaine Heffner (20th century)