В области теории графов в математике знаковый граф — это граф, в котором каждое ребро имеет положительный или отрицательный знак.
Знаковый граф сбалансирован , если произведение знаков ребер каждого цикла положительно. Название «график со знаком» и понятие баланса впервые появились в математической статье Фрэнка Харари в 1953 году. [1] Денес Кениг уже изучал эквивалентные понятия в 1936 году, используя другую терминологию, но не признавая значимости группы знаков. [2] В Центре групповой динамики Мичиганского университета Дорвин Картрайт и Харари обобщили психологическую теорию баланса Фрица Хейдера в треугольниках настроений до психологической теории баланса в знаковых графиках. [3] [4]
Знаковые графы открывались заново много раз, поскольку они естественным образом возникают во многих несвязанных между собой областях. [5] Например, они позволяют описывать и анализировать геометрию подмножеств классических корневых систем . Они появляются в топологической теории графов и теории групп . Они являются естественным контекстом для вопросов о нечетных и четных циклах в графах. Они появляются при вычислении энергии основного состояния в неферромагнитной модели Изинга ; для этого нужно найти наибольшее сбалансированное множество ребер в Σ. Они применялись для классификации данных при корреляционной кластеризации .
Знак пути есть произведение знаков его ребер. Таким образом, путь положителен только в том случае, если в нем есть четное число отрицательных ребер (где ноль четен). В теории математического баланса Фрэнка Харари знаковый граф сбалансирован , когда каждый цикл положителен. Харари доказывает, что знаковый граф сбалансирован, когда (1) для каждой пары узлов все пути между ними имеют одинаковый знак или (2) вершины разбиваются на пару подмножеств (возможно, пустых), каждое из которых содержит только положительные ребра, но соединены отрицательными краями. [1] Он обобщает теорему о том, что обычный (беззнаковый) граф является двудольным тогда и только тогда, когда каждый цикл имеет четную длину.
Простое доказательство использует метод переключения. Переключение знакового графа означает изменение знаков всех ребер между подмножеством вершин и его дополнением. Чтобы доказать теорему Харари, по индукции показывают, что Σ можно сделать полностью положительной тогда и только тогда, когда она сбалансирована.
Более слабая теорема, но с более простым доказательством, состоит в том, что если каждый 3-цикл в полном графе со знаком положителен, то граф сбалансирован. Для доказательства выберите произвольный узел n и поместите его и все те узлы, которые связаны с n положительным ребром, в одну группу, называемую A , и все те узлы, которые связаны с n отрицательным ребром, в другую, называемую B. Поскольку это полный граф, каждые два узла в A должны быть друзьями, а каждые два узла в B должны быть друзьями, иначе получится несбалансированный трехцикл. (Поскольку это полный граф, любое отрицательное ребро приведет к несбалансированному трехциклу.) Аналогично, все отрицательные ребра должны проходить между двумя группами. [6]
Индекс фрустрации ( ранее называемый линейным индексом баланса [7] ) Σ — это наименьшее число ребер, удаление которых или, что эквивалентно, смена знака (теорема Харари [7] ) делает Σ сбалансированным. Причина эквивалентности заключается в том, что индекс фрустрации равен наименьшему числу ребер, отрицание которых (или, что то же самое, удаление; делает Σ сбалансированным.
Второй способ описания индекса фрустрации состоит в том, что это наименьшее количество ребер, охватывающих все отрицательные циклы. Эту величину назвали числом покрытия отрицательного цикла .
Существует еще одно эквивалентное определение (которое легко доказать переключением). Присвойте каждой вершине значение +1 или −1; мы называем это состоянием Σ. Ребро называется удовлетворенным , если оно положительное и обе конечные точки имеют одинаковое значение, или оно отрицательное и конечные точки имеют противоположные значения. Ребро, которое не удовлетворено, называется неудовлетворенным . Наименьшее количество фрустрированных ребер среди всех состояний — это индекс фрустрации. Это определение было впервые введено в другой записи Абельсоном и Розенбергом под (устаревшим) названием сложность . [8] Дополнением такого множества является сбалансированный подграф Σ с наибольшим количеством возможных ребер.
Нахождение индекса разочарования является NP-сложной задачей. Ареф и др. предложить модели бинарного программирования, которые способны вычислять индекс фрустрации графов с числом ребер до 10 5 за разумное время. [9] [10] [11] В NP-сложности можно убедиться, заметив, что индекс фрустрации графа со всеми отрицательными знаками такой же, как и задача максимального разреза в теории графов, которая является NP-сложной.
Индекс фрустрации важен в модели спиновых стекол , смешанной модели Изинга . В этой модели подписанный граф фиксирован. Состояние состоит из вращения каждой вершины либо «вверх», либо «вниз». Мы думаем, что вращение вверх равно +1, а вращение вниз – как −1. Таким образом, каждое состояние имеет ряд неудовлетворенных ребер. Энергия состояния тем больше, чем больше у него неудовлетворенных ребер, поэтому основное состояние — это состояние с наименьшим количеством неудовлетворенной энергии. Таким образом, чтобы найти энергию основного состояния Σ, необходимо найти индекс фрустрации.
Аналогичным числом вершин является число фрустрации , определяемое как наименьшее количество вершин, удаление которых из Σ приводит к балансу. Эквивалентно, нужен наибольший порядок сбалансированного индуцированного подграфа Σ.
Три фундаментальных вопроса о знаковом графе: сбалансирован ли он? Каков наибольший размер установленной в нем сбалансированной кромки? Какое наименьшее количество вершин необходимо удалить, чтобы сделать его сбалансированным? Первый вопрос легко решить за полиномиальное время. Второй вопрос называется проблемой индекса разочарования или максимального сбалансированного подграфа . Это NP-трудная задача , поскольку ее частным случаем (когда все ребра графа отрицательны) является NP-трудная задача Maximum Cut . Третий вопрос называется « Число разочарования» или «Проблема максимального сбалансированного индуцированного подграфа» , он также является NP-сложным ; см., например, [12]
Есть два матроида , связанные со знаковым графом, называемые матроидом знаковой графики (также называемым матроидом кадра или иногда матроидом смещения ) и матроидом подъема , оба из которых обобщают матроид цикла графа. Они являются частными случаями одних и тех же матроидов смещенного графа .
Матроид кадра (или матроид знаковой графики ) M ( G ) имеет в качестве основы множество ребер E. [13] Множество ребер является независимым, если каждый компонент не содержит окружностей или содержит только одну окружность, что является отрицательным. (В теории матроида полуребро действует точно так же, как отрицательная петля.) Контур матроида представляет собой либо положительный круг, либо пару отрицательных кругов вместе с соединяющим простым путем, так что два круга либо не пересекаются (тогда соединительный путь имеет один общий конец с каждым кругом и в противном случае не пересекается с обоими) или имеет только одну общую вершину (в этом случае соединительный путь представляет собой эту единственную вершину). Ранг множества ребер S равен n − b , где n — количество вершин G , а b — количество сбалансированных компонентов S , считая изолированные вершины сбалансированными компонентами. Этот матроид является матроидом столбца матрицы инцидентности графа со знаком. Поэтому он описывает линейные зависимости корней классической корневой системы.
Расширенный матроид подъема L0 ( G ) имеет в качестве основного множества множество E0 , объединение множества ребер E с дополнительной точкой , которую мы обозначим e0 . Лифт -матроид 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]
