Структурная теорема Хайдера, Харари и Картрайта.

Знаковый граф сбалансирован, если и только если все множество его вершин может быть разбито на два подмножества таких, что в каждом из них вершины соединены ребром с положительным знаком, а вершины, принадлежащие разным подмножествам соединены между собой ребром с отрицательным знаком.

Оценка степени сбалансированности знакового графа:

b(G) = C₊(G)/C(G)

 

C₊(G) – число положительных циклов в графе;

C(G) – общее число циклов в графе.

Расчет знака в цикле – перемножение знаков ребер.

 

b₁(G) = ₃Sⁿ 1/k*P_k/ ₃Sⁿ1/k*D_k

 

где к – длина цикла (3, 4, 5 и т.д.); P_k – число положительных циклов длины k, а в знаменателе подсчитывается общее число циклов разных длин.

Рассмотрим для примера модель группы из трёх индивидов, два из которых являются друзьями, и они оба плохо относятся к третьему члену группы. Модель социальной группы представляет объект , где - не ориентированный граф отношений, А – множество вершин графа, В – множество ребер графа, - множество состояний отношений между индивидами состоящее из элементов –1, 1. Каждому субъекту социальной группы ставится в соответствие вершина графа. Тот факт что между субъектами существуют отношения означает что между вершинами графа, поставленным в соответствие двум этим субъектам существует ребро, то какие чувства они испытывают друг к другу определяется знаком ребра + или -, будем считать что это отношение симметрично, то есть чувства взаимны.

Соответственно моделью группы из трёх индивидов будет связанный не ориентированный граф, состоящий из трех вершин. Связанным будем называть граф каждая вершина которого связана ребром со всеми остальными вершина­ми графа. Итак, модель группы из трёх индивидов будет иметь вид как на Рис.4.2.

Из ранее описанных соображений делается вывод, что все субъекты группы будут чувствовать себя достаточно комфортно, если число отрицательных ребер четно, и они будут испытывать дискомфорт, если число отрицательных ребер не четно. Ф. Хайдер назвал состояние, когда члены группы чувствуют себя комфортно состоянием баланса, противоположенную ситуацию назвал состоянием дисбаланса. Следующая таблица демонстрирует все возможные ситуации баланса и дисбаланса для группы из трёх индивидов.

 

Х1 и Х2	Х1 и Х3	Х2 и Х3	Структура находится в состоянии:
+	+	+	Баланса
+	-	-	Баланса
-	+	-	Баланса
-	-	+	Баланса
+	+	-	Дисбаланса
+	-	+	Дисбаланса
-	+	+	Дисбаланса
-	-	-	Дисбаланса

 

Если же рассматривать более сложные системы, состоящие более, чем из трёх индивидов, то сбалансированной такая система будет только в случае, если все циклы в графе соответствующей этой системе будут положительны. Циклом в графе будем называть замкнутый путь без пересечений, это означает, что ни одна вершина, кроме исходной вершины, не встречается в графе более одного раза. То есть цикл - путь в графе, начало и конец которого совпадают. Путь в графе - это кратчайшая последовательность ребер, соединяющая одну вершину с другой.

Соответственно получим следующую трансляцию данных о социальной группе в термины математической модели.

 

 

 

Кроме того, Д.Картрайтом (D. Cartwright) и Ф. Харари(F. Harary) был определён коэффициент сбалансированности графа, который, напомним, определяется по формуле

,

где b(G) – коэффициент сбалансированности графа G;

C+(G) – число положительно определённых циклов в графе G;

C(G) – общее число циклов в графе G.

Коэффициент сбалансированности графа b(G) принимает значения от 0 до 1. Соответственно при значении b(G) равном 1, граф будет сбалансирован, при всех остальных значениях граф будет несбалансирован, а степень не стабильности моделируемой социальной группы будет обратно пропорциональна коэффициенту сбалансированности.

Вычисление коэффициента сбалансированности связано с большим объемом вычислений: необходимо выделить все циклы в графе, посчитать знак каждого из них, и только затем вычислить коэффициент сбалансированности. Перед студентом ВМК – А.Ставером была поставлена задача: разработать и реализовать алгоритм, позволяющий вычислять при помощи ЭВМ коэффициент сбалансированности графа. Известно, что графу отношений можно поставить в соответствие матрицу отношений, следующим образом:

 

 

Соответственно ребру графа, связывающему элементы х₁ и х₂, будет соответствовать элемент а₁₂. Кроме того, так как субъекты испытывают друг к другу симметричные отношения, матрица будет симметричной относительно своей главной диагонали, то есть а_ij = a_ji.

Для иллюстрации построим матрицу, соответствующую графу описывающему социальную группу из четырёх субъектов. Пусть описываемой социальной группе соответствует следующий граф отношений (Рис.4.3.):

Рис.4.3. Граф отношений взаимных симпатий и антипатий в группе из 4-х субъектов.

Матрица отношений, соответствующая графу G, будет иметь следующий вид:

 

 

Рассматривая элементы матрицы A_ij, мы получаем информацию о графе, каждый цикл кодируется последовательностью соответствующих элементом матрицы A_ij. Например циклу Х₁ , Х₄, Х₂, Х₁ из выше приведенного графа G, будет соответствовать последовательность элементов a₁₄, a₄₂, a₂₁ соответствующей ему матрицы A_ij. Кроме того, элементы матрицы A_ij содержат информацию не только о существовании ребра между двумя вершинами, но и о знаке ребра, что дает возможность вычислить знак цикла. Для поиска всех существующих циклов в графе было использовано представление маршрутов графа в виде дерева. Так максимальная длина цикла равняется N+1, где N - число вершин в графе (единица добавляется вследс­твие того, что первая вершина, откуда начинается цикл, является и конечной, т.е. учитывается дважды), то глубина дерева также равняется N+1. Каждый узел дерева имеет N-1 потомка вследствие того, что граф не содержит петель. Ниже приведен пример такого дерева для графа из трех вершин (Рис.4.4).

 

Рис. 4.4. Представление маршрутов в виде дерева для графа из трех вершин.

Поиск существующих циклов происходит во время обхода дерева. Каждый путь, содержащий более трёх не повторяющихся узлов дерева и у которого последний узел равен первому, является циклом. Данное дерево строится для каждой вершины графа, то есть функция обхода дерева вызывается N раз, а каждый вновь найденный цикл сравнивается с уже найденными. Если он уникален, то вычисляется его знак, и изменяются счетчики общего числа циклов и числа положительных циклов.

Как ранее говорилось, коэффициент сбалансированности показывает то, насколько моделируемая социальная группа близка или далека от состояния баланса, то есть насколько комфортно чувствуют себя субъекты внутри группы. Используя данную модель, можно на основании вычисления коэффициента сбалансированности дать рекомендации по повышению устойчивости моде­лируемой группы, как, например, обосновать изменение отношений между субъектами группы: исключение или добавление субъекта в группу. Повышение устойчивости благоприятно скажется на жизнедеятельности всей группы, так как это будет означать улучшение социального климата внутри группы.

Но, несмотря на эти результаты, модель всё же дает только прибли­женную картину действительной ситуации, так как она строилась с использо­ванием целого ряда допущений. Например, в модели не учитывается 1) влияние окружения на отношение двух субъектов, 2) что отношения между субъектами считаются симметричными, а могут быть в одну сторону положительными, а в другую отрицательными. Кроме того, модель статична, она оценивает коэффициент сбалансированности на данный момент времени, не показывая возможный вариант развития ситуации.

 

 

 

 

Упорядочение компонентов

Исследовалась “сплоченность производственного коллектива”[4]. Под этим понятием подразумевалась совокупность следующих взаимосвязанных факторов:

К – коллективизм как отношение товарищей по труду, проявляющееся во взаимопомощи, взаимовыручке и т.п.;

Е – единодушие (например, членов бригады) в решении того или иного производственного вопроса;

Н – настроение как выражение психологического климата в данном произ­водственном коллективе (например, в бригаде);

И – информированность членов коллектива (бригады) о производственных де­лах;

О – ответственность членов производственного коллектива (бригады) за порученное дело, соблюдение общественных (групповых) норм и рабочих традиций;

А – активность каждого представителя коллектива (бригады) в сфере производства;

У – управляемость членами коллектива (бригады) по административной линии.

Была поставлена задача: используя статистические данные анкетирования и интервьюирования работников производственных коллективов, получить в рамках порядковой шкалы систему приоритетов для названных семи факторов, обеспечивающую, по мнению опрашиваемых, наилучшее комплексное управление уровнем сплоченности в коллективе.

Итоговым представлением статистического эмпирического материала служила квадратная матрица “0,1”, в которой число строк и столбцов – 7 * 7 – отвечает результатам сравнения друг с другом статусов названного множества факторов (К, И, Н, О, А, У, Е).

 

 

	И	Е	К	У	Н	О	А
И	Х
Е		Х
К			Х
У				Х
Н					Х
О						Х
А							Х

 

Матрица построена так, что:

1) по главной диагонали находятся пустые клетки, статус каждого фактора в данной системе не больше, но и не меньше самого себя – в соответствующем матрице графе не существует петель в вершинах графа;

2) «1» ставится на пересечении строки для сравнения статуса соответствующего фактора со статусом фактора, представленного столбцом, если фактически достоверно устанавливается приоритет статуса первого фактора над статусом второго;

3) «0» ставится в противоположном случае;

4) если не удается установить приоритета для статусов ни одного из сравниваемых факторов, то ставятся две «1» симметрично главной диагонали – она помечена на матрице косыми крестами;

5) в случае отсутствия прямого сравнения двух факторов друг с другом симметрично главной диагонали проставляются нули.

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

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

Теоретико-графовой задачей реализующей указанное условие, является задача нахождения гамильтоновых путей на графе, отвечающем указанной матрице «0,1». Насколько содержательна такая постановка задачи, показывает число комбинаторных вариантов упорядочения семи факторов – 7! = 5040.

Чтобы убедиться в наличии хотя бы одного гамильтонова пути (а это прохождение вершин графа по одному разу), обратимся к теореме Кёнига.

Теорема Кёнига. В полном графе (любая пара вершин которого соединена хотя бы в одном направлении) всегда существует гамильтонов путь.

Орграф, отвечающий нашей матрице, удовлетворяет условиям теоремы.

Рецептура поиска гамильтонова пути при наличии матрицы орграфа рекомендует начинать это поиск с обнаружения «конечной» или «начальной» вершины для множества искомых гамильтоновых путей.

Признаком «конечной» вершины является столбец из одних единиц (с учетом «косых крестов диагонали» переименованных в единицы), т.е. сюда только сходятся дуги графа. Признаком «начальной» вершины является столбец из одних нулей (за вычетом единицы на главной диагонали), а строка для той же вершины из одних единиц, т.е. отсюда только выходят дуги графа.

В нашей матрице таковой вершиной – начальной – оказалась вершина, поименованная как «О».

Зачеркивается соответствующий столбец и строка, что трансформирует исходную матрицу «N x N» в «(N-1) x (N-1)». Если в новой матрице ситуация аналогична, то упрощающая трансформация матрицы продолжается. Если таким образом, упорядочение вершин невозможно, то применяется процедура алгоритма Фаулкса, представление о котором дано в Приложении к Лекции.

В симметрическом графе две смежные вершины х и у всегда соединены двумя противоположно ориентированными дугами.

Теорема Дирака.

Если (Х, Г) – симметрический связный граф без петель и если |Гх| ³ 0.5|Х| для всех х Î Х, то существует гамильтонов контур.

Применение этого алгоритма позволило найти искомый порядок для факторов сплоченности: ОИКЕНАУ.

 

Пример анализа построений русских войск на Куликовом поле

 

При построении плана сражения воевода-полководец Василий Боброк – главный помощник (на современном языке – начальник штаба) в.к. Дмитрия Ивановича исходил из следующих тактических особенностей, сильных и слабых сторон татаро-монгольского войска:

1) основой войска являлась конница, разделяемая на главные силы и стратегический резерв; конница была сильна во фланговых прорывах и слаба (в противовес русским войскам) во фронтальном наступлении;

2) сильным тактическим приемом монгольской конницы, резко ослабляющим мощь войск противника до его вхождения в непосредственное кульминационное бое столкновение, было длительное осыпание стрелами со значительного расстояния стоящих боевых порядков противника;

3) монгольский конник помимо оружия нападения – сабли, лука со стрелами и пики имел оружие защиты – нагрудный щиток – от стрел, дротиков, пик, но сзади – со спины защиты не имел, возможно, из соображений: «чтобы реже отступал».

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

Для этого надо было выбрать такое место сражения и так построить войска, чтобы было место для этой ловушки и чтобы вся монгольская конница, как главные силы, так и стратегический резерв, в ней оказались.

Но чтобы добиться этого, надо было сохранить боеспособность русских полков, т.е. не дать их расстрелять до главных событий.