Билет 15 теория Знаковые графы
.docx-
Знаковый граф-это граф, вершины которые соответствуют членам групп. Дуги между вершинами обозначаются знаками “+” и “-“. Знак + означает, что отношения между участниками хорошие, знак “-“ плохие. Если знаки между вершинами отсутствуют, это означает что между участниками отношение безразличия. Пример:
-
Определение сбалансированности группы: Группа N состоящая из n участников является сбалансированной, если её можно разбить на 2 подгруппы N1 и N2, такие что, все участники внутри групп относятся положительно друг к другу или равнодушны, а любые два участника из разных групп находятся в антипатии друг к другу.
-
Определение сбалансированного знакового графа: знаковый граф сбалансирован, если множество его вершин можно разбить на 2 группы, в каждой из которых отношения буду описываться “+” , а любые две взятые вершины из разных групп будут со знаком “-“.
Пример сбалансированного графа :
Данный граф сбалансирован, так как есть два множества N1, N2: N1=[a,b,c]; N2=[e,d] в которых отношения имеют знак “+” а между любыми вершинами разных групп отношения описываются знаком “-“.
-
Критерий сбалансированности графа: Введем понятие цикла, как знака произведения входящих в него дуг. Дуга, входящая в этот цикл со знаком «+» будет иметь коэффициент =+1, дуга со знаком -, будет иметь коэффициент со знаком -1. Таким образом, граф сбалансирован, если любой цикл входящий в него будет положительным.( подробная инфомрация на стр. 183 Алискеров)
-
Мера сбалансированности графа :
С+= число положительных простых циклов, С- число всех простых циклов.( Простой цикл- в котором начальная вершина совпадает с конечным)
Пример нахождения меры сбалансированности:
Дан граф G:
Определим знаки простых циклов: