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:
“We read poetry because the poets, like ourselves, have been haunted by the inescapable tyranny of time and death; have suffered the pain of loss, and the more wearing, continuous pain of frustration and failure; and have had moods of unlooked-for release and peace. They have known and watched in themselves and others.”
—Elizabeth Drew (1887–1965)