В области теории графов в математике знаковый граф — это граф, в котором каждое ребро имеет положительный или отрицательный знак.
Знаковый граф сбалансирован , если произведение знаков ребер вокруг каждого цикла положительно. Название «знаковый граф» и понятие баланса впервые появились в математической статье Фрэнка Харари в 1953 году. [1] Денес Кёниг уже изучал эквивалентные понятия в 1936 году под другой терминологией, но без признания значимости группы знаков. [2] В Центре групповой динамики Мичиганского университета Дорвин Картрайт и Харари обобщили психологическую теорию баланса Фрица Хайдера в треугольниках настроений до психологической теории баланса в знаковых графах. [3] [4]
Знаковые графы были переоткрыты много раз, поскольку они естественным образом возникают во многих несвязанных областях. [5] Например, они позволяют описывать и анализировать геометрию подмножеств классических корневых систем . Они появляются в топологической теории графов и теории групп . Они являются естественным контекстом для вопросов о нечетных и четных циклах в графах. Они появляются при вычислении энергии основного состояния в неферромагнитной модели Изинга ; для этого нужно найти наибольшее сбалансированное множество ребер в Σ. Они были применены для классификации данных в корреляционной кластеризации .
Знак пути — это произведение знаков его ребер. Таким образом, путь положителен только в том случае, если в нем четное число отрицательных ребер (где ноль — четное число). В математической теории баланса Фрэнка Харари знаковый граф сбалансирован , когда каждый цикл положителен. Харари доказывает, что знаковый граф сбалансирован, когда (1) для каждой пары узлов все пути между ними имеют одинаковый знак, или (2) вершины разбиваются на пару подмножеств (возможно, пустых), каждое из которых содержит только положительные ребра, но соединено отрицательными ребрами. [1] Это обобщает теорему о том, что обычный (беззнаковый) граф является двудольным тогда и только тогда, когда каждый цикл имеет четную длину.
Простое доказательство использует метод переключения. Переключение знакового графа означает изменение знаков всех ребер между подмножеством вершин и его дополнением. Чтобы доказать теорему Харари, по индукции показывают, что Σ можно переключить так, чтобы она была полностью положительной, если и только если она сбалансирована.
Более слабая теорема, но с более простым доказательством, заключается в том, что если каждый 3-цикл в знаковом полном графе положителен, то граф сбалансирован. Для доказательства выберите произвольный узел n и поместите его и все те узлы, которые связаны с n положительным ребром в одну группу, называемую A , а все те, которые связаны с n отрицательным ребром, в другую, называемую B. Поскольку это полный граф, каждые два узла в A должны быть друзьями, и каждые два узла в B должны быть друзьями, в противном случае был бы 3-цикл, который был бы несбалансированным. (Поскольку это полный граф, любое отрицательное ребро вызвало бы несбалансированный 3-цикл.) Аналогично, все отрицательные ребра должны проходить между двумя группами. [6]
Индекс фрустрации (ранее называемый индексом баланса линии [7] ) Σ — это наименьшее число ребер, удаление которых или, что эквивалентно, изменение знака (теорема Харари [7] ) делает Σ сбалансированной. Причина эквивалентности заключается в том, что индекс фрустрации равен наименьшему числу ребер, отрицание которых (или, что эквивалентно, удаление) делает Σ сбалансированной.
Второй способ описания индекса фрустрации заключается в том, что это наименьшее число ребер, которые покрывают все отрицательные циклы. Эта величина была названа числом покрытия отрицательного цикла .
Существует еще одно эквивалентное определение (которое можно легко доказать переключением). Дайте каждой вершине значение +1 или −1; мы называем это состоянием Σ. Ребро называется удовлетворенным, если оно положительно и обе конечные точки имеют одинаковое значение, или оно отрицательно и конечные точки имеют противоположные значения. Ребро, которое не удовлетворено, называется фрустрированным . Наименьшее количество фрустрированных ребер по всем состояниям — это индекс фрустрации. Это определение было впервые введено в другой нотации Абельсоном и Розенбергом под (устаревшим) названием difficulty . [8] Дополнением такого множества является сбалансированный подграф Σ с наибольшим количеством возможных ребер.
Нахождение индекса фрустрации является NP-трудной задачей. Ареф и др. предлагают модели бинарного программирования, которые способны вычислять индекс фрустрации графов с числом ребер до 105 за разумное время. [9] [10] [11] Можно увидеть NP-трудную сложность, заметив, что индекс фрустрации полностью отрицательного знакового графа такой же, как и задача максимального разреза в теории графов, которая является NP-трудной.
Индекс фрустрации важен в модели спиновых стекол , смешанной модели Изинга . В этой модели знаковый граф фиксирован. Состояние состоит из придания «спина», либо «вверх», либо «вниз», каждой вершине. Мы думаем о спине вверх как о +1, а о спине вниз как о −1. Таким образом, каждое состояние имеет ряд фрустрированных ребер. Энергия состояния больше, когда оно имеет больше фрустрированных ребер, поэтому основное состояние — это состояние с наименьшей фрустрированной энергией. Таким образом, чтобы найти энергию основного состояния Σ, нужно найти индекс фрустрации.
Аналогичное число вершин — это число фрустрации , определяемое как наименьшее число вершин, удаление которых из Σ приводит к балансу. Эквивалентно, требуется наибольший порядок сбалансированного индуцированного подграфа Σ.
Три основных вопроса о знаковом графе: сбалансирован ли он? Каков наибольший размер сбалансированного набора ребер в нем? Каково наименьшее число вершин , которые необходимо удалить, чтобы сделать его сбалансированным? Первый вопрос легко решить за полиномиальное время. Второй вопрос называется проблемой индекса фрустрации или максимального сбалансированного подграфа . Он является NP-трудным, поскольку его частным случаем (когда все ребра графа отрицательны) является NP-трудная задача Максимальный разрез . Третий вопрос называется проблемой числа фрустрации или максимального сбалансированного индуцированного подграфа , также является NP-трудным ; см., например, [12]
Существует два матроида, связанных со знаковым графом, называемые знаково-графическим матроидом (также называемым каркасным матроидом или иногда матроидом смещения ) и подъемным матроидом , оба из которых обобщают циклический матроид графа. Они являются частными случаями тех же матроидов смещенного графа .
Каркасный матроид (или знаково-графический матроид ) M ( G ) имеет в качестве своего базового множества множество ребер E . [13] Множество ребер является независимым, если каждый компонент не содержит ни одного круга или содержит только один круг, что является отрицательным. (В теории матроидов полуребро действует точно так же, как отрицательная петля.) Контур матроида представляет собой либо положительный круг, либо пару отрицательных кругов вместе с соединяющим простым путем, таким образом, что два круга либо не пересекаются (тогда соединительный путь имеет один общий конец с каждым кругом и в противном случае не пересекается с обоими), либо имеют только одну общую вершину (в этом случае соединительный путь является этой единственной вершиной). Ранг множества ребер S равен n − b , где n — число вершин G , а b — число сбалансированных компонентов S , считая изолированные вершины сбалансированными компонентами. Этот матроид является столбчатым матроидом матрицы инцидентности знакового графа. Вот почему он описывает линейные зависимости корней классической корневой системы.
Расширенный подъемный матроид L 0 ( G ) имеет в качестве своего базового множества множество E 0 , объединение множества ребер E с дополнительной точкой , которую мы обозначим e 0 . Подъемный матроид L ( G ) является расширенным подъемным матроидом, ограниченным E . Дополнительная точка действует точно так же, как отрицательная петля, поэтому мы описываем только подъемный матроид. Множество ребер является независимым, если оно либо не содержит кругов, либо содержит только один круг, что является отрицательным. (Это то же самое правило, которое применяется отдельно к каждому компоненту в знаково-графическом матроиде.) Схема матроида является либо положительным кругом, либо парой отрицательных кругов, которые либо не пересекаются, либо имеют только общую вершину. Ранг множества ребер S равен n − c + ε, где c — число компонентов S , включая изолированные вершины, а ε равно 0, если S сбалансировано, и 1, если нет.
Иногда знаки принимаются равными +1 и −1. Это всего лишь разница в обозначениях, если знаки все еще умножаются по кругу, а знак произведения важен. Однако есть два других способа обработки меток ребер, которые не вписываются в теорию знаковых графов.
Термин знаковый граф иногда применяется к графам, в которых каждое ребро имеет вес, w ( e ) = +1 или −1. Это не тот же самый вид знакового графа; это взвешенные графы с ограниченным набором весов. Разница в том, что веса складываются, а не умножаются. Проблемы и методы совершенно разные.
Название также применяется к графам, в которых знаки выполняют функцию цветов на ребрах. Значение цвета заключается в том, что он определяет различные веса, применяемые к ребру, а не в том, что его знак имеет внутреннее значение. Это имеет место в теории узлов , где единственное значение знаков заключается в том, что они могут быть заменены двухэлементной группой, но нет никакого внутреннего различия между положительным и отрицательным. Матроид графа, раскрашенного знаками, является циклическим матроидом базового графа; он не является каркасом или подъемным матроидом знакового графа. Метки знаков, вместо того чтобы изменять матроид, становятся знаками на элементах матроида.
В этой статье мы обсуждаем только теорию знаковых графов в строгом смысле. Для графов со знаковыми цветами см. цветные матроиды .
Знаковый орграф — это ориентированный граф с дугами со знаком. Знаковые орграфы гораздо сложнее, чем знаковые графы, поскольку значимыми являются только знаки направленных циклов. Например, существует несколько определений баланса, каждое из которых трудно охарактеризовать, в сильном контрасте с ситуацией для знаковых неориентированных графов.
Знаковые орграфы не следует путать с ориентированными знаковыми графами. Последние являются двунаправленными графами , а не направленными графами (за исключением тривиального случая всех положительных знаков).
Граф со знаком вершины , иногда называемый маркированным графом , — это граф, вершинам которого присвоены знаки. Окружность называется согласованной (но это не связано с логической согласованностью) или гармоничной , если произведение знаков ее вершин положительно, и несогласованной или негармоничной , если произведение отрицательно. Не существует простой характеристики гармоничных графов со знаком вершины, аналогичной теореме Харари о балансе; вместо этого характеристика была сложной проблемой, лучше всего решенной (даже в более общем виде) Джоглекаром, Шахом и Диваном (2012). [14]
Часто бывает легко добавить знаки ребер к теории знаков вершин без серьезных изменений; таким образом, многие результаты для графов с вершинным знаком (или «помеченных графов со знаком») естественным образом распространяются на графы с вершинным и ребровым знаком. Это особенно верно для характеристики гармонии Джоглекаром, Шахом и Диваном (2012).
Разница между маркированным знаковым графом и знаковым графом с функцией состояния (как в § Фрустрация ) заключается в том, что знаки вершин в первом случае являются частью существенной структуры, тогда как функция состояния является переменной функцией на знаковом графе.
Обратите внимание, что термин «маркированный граф» широко используется в сетях Петри в совершенно ином значении; см. статью о маркированных графах .
Как и в случае с беззнаковыми графами , существует понятие знаковой раскраски графа. Если раскраска графа — это отображение множества вершин на натуральные числа, то раскраска знакового графа — это отображение множества вершин на целые числа. Ограничения на правильную раскраску исходят от ребер знакового графа. Целые числа, назначенные двум вершинам, должны быть различными, если они соединены положительным ребром. Метки на соседних вершинах не должны быть аддитивными обратными, если вершины соединены отрицательным ребром. Не может быть правильной раскраски знакового графа с положительным циклом.
При ограничении меток вершин множеством целых чисел с величиной не более натурального числа k множество правильных раскрасок знакового графа конечно. Соотношение между числом таких правильных раскрасок и k является полиномом от k ; при выражении через него оно называется хроматическим полиномом знакового графа. Оно аналогично хроматическому полиному беззнакового графа.
В социальной психологии знаковые графы использовались для моделирования социальных ситуаций, где положительные ребра представляли дружбу, а отрицательные ребра — вражду между узлами, которые представляли людей. [3] Тогда, например, положительный 3-цикл — это либо три общих друга, либо два друга с общим врагом; в то время как отрицательный 3-цикл — это либо три общих врага, либо два врага, у которых есть общий друг. Согласно теории баланса , положительные циклы сбалансированы и должны быть стабильными социальными ситуациями, тогда как отрицательные циклы не сбалансированы и должны быть нестабильными. Согласно теории, в случае трех общих врагов это происходит потому, что общий враг, скорее всего, заставит двух врагов стать друзьями . В случае двух врагов, имеющих общего друга, общий друг, скорее всего, выберет одного из них и превратит одну из своих дружеских связей во врага.
Антал, Крапивский и Редер рассматривают социальную динамику как изменение знака на ребре знакового графа. [15] Социальные отношения с предыдущими друзьями разводящейся пары используются для иллюстрации эволюции знакового графа в обществе. Другая иллюстрация описывает изменение международных альянсов между европейскими державами в десятилетия до Первой мировой войны . Они рассматривают локальную динамику триад и динамику ограниченных триад, где в последнем случае изменение отношений происходит только тогда, когда общее количество несбалансированных триад сокращается. Моделирование предполагало полный граф со случайными отношениями, имеющим случайную несбалансированную триаду, выбранную для преобразования. Эволюция знакового графа с N узлами в этом процессе изучается и моделируется для описания стационарной плотности дружественных связей.
Теория баланса была подвергнута серьезному сомнению, особенно в ее применении к большим системам, на теоретическом основании, что дружеские отношения связывают общество воедино, в то время как общество, разделенное на два лагеря врагов, было бы крайне нестабильным. [16] Экспериментальные исследования также предоставили лишь слабое подтверждение предсказаний теории структурного баланса. [17]
В физике знаковые графики являются естественным контекстом для неферромагнитной модели Изинга , которая применяется для изучения спиновых стекол .
Используя аналитический метод, изначально разработанный в популяционной биологии и экологии, но теперь используемый во многих научных дисциплинах, знаковые орграфы нашли применение в рассуждениях о поведении сложных причинных систем. [18] [19] Такой анализ отвечает на вопросы об обратной связи на заданных уровнях системы и о направлении переменных реакций при возмущении системы в одной или нескольких точках, переменных корреляциях при таких возмущениях, распределении дисперсии по системе и чувствительности или нечувствительности конкретных переменных к возмущениям системы.
Корреляционная кластеризация ищет естественную кластеризацию данных по сходству. Точки данных представлены в виде вершин графа, где положительное ребро соединяет похожие элементы, а отрицательное ребро соединяет разнородные элементы.
Мозг можно рассматривать как знаковый граф, где синхронность и антисинхронность между паттернами активности областей мозга определяют положительные и отрицательные края. В этом отношении можно исследовать стабильность и энергию мозговой сети. [20] Также, в последнее время, концепция фрустрации использовалась в анализе мозговых сетей для определения нетривиальной сборки нейронных связей и выделения регулируемых элементов мозга. [21]
Знаковый граф — это особый вид графа усиления, в котором группа усиления имеет порядок 2. Пара ( G , B (Σ)), определяемая знаковым графом Σ, является особым видом смещенного графа . Знаковая группа имеет особое свойство, не разделяемое более крупными группами усиления, а именно, что знаки ребер определяются с точностью до переключения множеством B (Σ) сбалансированных циклов. [22]
