Взвешенный граф, взвешенный орграф - граф (орграф), каждому ребру которого приписан некоторый вес.

Знаковый граф, знаковый орграф - граф (орграф), каждому ребру которого приписан некоторый знак.

Знак пути, цепи, замкнутого пути, замкнутой цепи, контура, цикла и т.д. определяется как произведение знаков входящих в них дуг или ребер, если знак плюс заменить на +1, а знак минус на -1. Очевидно, что путь, цепь и т.д. имеют знак минус, если число дуг или ребер, содержащихся в них, нечетно, иначе они имеют знак плюс.

Хейдер изучал задачи из области социологии малых групп людей (Heider F. Attitudes and Cognitive Organization. - J. of Phych., 21, 1946, p. 107-112).

Его результаты - полный обзор вариантов знаковых графов для группы из трех человек в условиях явно выраженной выраженной симпатии / антипатии представлены на рисунках.

Группы из трех лиц по Хейдеру психологически

сбалансированные

несбалансированные

Анализ этого и огромного количества других примеров из самых разных областей человеческой деятельности привел Картрайта и Харари (Cartwright D. and Harary F. Structural Balance: A Generalization of Heider's Theory. - Psych. Rev., 63, 1956, p. 277-293) к следующей математической модели баланса:

Малая группа является сбалансированной, если представляющий ее знаковый граф сбалансирован.

Знаковый граф называется сбалансированным, если каждый цикл в нем положителен.

Теорема о структуре (теорема Харари о балансе)

Для знакового графа G=(V,E) следующие утверждения эквивалентны:

1. Граф G сбалансирован.

2. Каждая замкнутая цепь в G положительна.

3. Любые две цепи между любыми двумя вершинами ui и uj имеют одинаковый знак.

4. Множество вершин V можно разбить на два подмножества A и B так, что каждое положительное ребро соединяет вершины одного подмножества и каждое отрицательное соединяет вершины различных подмножеств.

Последнее утверждение называют также критерием баланса.