Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Есть восемь способов присвоения знаков сторонам треугольника. Согласно теории Фрица Хайдера, нечетное количество отрицательных знаков образует неуравновешенный треугольник .

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

Знаковый граф является сбалансированным, если произведение краевых знаков вокруг каждого цикла положительно. Три основных вопроса о графе со знаком: сбалансирован ли он? Какой самый большой размер установленной в ней сбалансированной кромки? Какое наименьшее количество вершин необходимо удалить, чтобы сделать его сбалансированным? Первый вопрос легко решить быстро; второй и третий вычислительно труднопреодолимы (технически они NP-трудны ) [ цитата необходима ] .

Название «граф со знаком » и понятие баланса впервые появились в математической статье Фрэнка Харари в 1953 году. [1] Денес Кёниг уже изучал эквивалентные понятия в 1936 году под другой терминологией, но не осознавая релевантность группы знаков. [2] В Центре групповой динамики при Мичиганском университете , Dorwin Картрайт и Харари обобщены Фриц Хайдер психологической теории «s из баланса в треугольниках чувств к психологической теории баланса подписанных графов. [3] [4]

Подписанные графики открывались заново много раз, потому что они естественным образом возникают во многих несвязанных областях. [5] Например, они позволяют описывать и анализировать геометрию подмножеств классических корневых систем . Они появляются в топологической теории графов и теории групп . Они являются естественным контекстом для вопросов о нечетных и четных циклах в графах. Они появляются при вычислении энергии основного состояния в неферромагнитной модели Изинга ; для этого нужно найти наибольшее сбалансированное множество ребер в Σ. Они были применены для классификации данных в корреляционной кластеризации .

Примеры [ править ]

  • Полный подписан график на п вершин с петлями, обозначаемый ± К п О , имеет все возможные положительные и отрицательные края , включая отрицательные петли, но никаких положительных циклов. Его ребра соответствуют корням корневой системы C n ; столбец ребра в матрице инцидентности (см. ниже) - это вектор, представляющий корень.
  • Полный подписан график с полуребер, ± K п », составляет ± К п с половинным краем в каждой вершине. Его ребра соответствуют корням корневой системы B n , полуребра соответствуют единичным базисным векторам.
  • Полная подписана ссылка график , ± К п , то же самое , но без петель. Его ребра соответствуют корням корневой системы D n .
  • У полностью положительного графа со знаком есть только положительные ребра. Если базовый граф G , все-положительное заключение написано + G .
  • У полностью отрицательного графа со знаком есть только отрицательные ребра. Он сбалансирован тогда и только тогда, когда он двудольный, потому что окружность положительна тогда и только тогда, когда она имеет четную длину. Все-граф с отрицательным , лежащим в основе графа G написано - G .
  • Подписан полный граф имеет в качестве основного графа G обычного полного графа K н . Могут быть какие-то признаки. Подписанные полные графы эквивалентны двухграфам , которые имеют значение в теории конечных групп. Два-граф может быть определен как класс множеств вершин треугольников (отрицательных , имеющих нечетное число отрицательных ребер) в подписанном полном графе.

Матрица смежности [ править ]

Матрица смежности подписанного графа Е на п вершинах является п × п матрица (Σ). У него есть строка и столбец для каждой вершины. Запись a vw в строке v и столбце w - это количество положительных ребер vw минус количество отрицательных ребер vw . На диагонали a vv = 0, если нет петель или полуребер; правильное определение, когда такие края существуют, зависит от обстоятельств.

Ориентация [ править ]

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

Матрица заболеваемости [ править ]

Матрица инцидентности знакового графа с n вершинами и m ребрами представляет собой матрицу n × m , со строкой для каждой вершины и столбцом для каждого ребра. Он получается любым способом ориентирования подписанного графа. Тогда его вход η ij равен +1, если ребро j ориентировано в вершину i , −1, если ребро j ориентировано вне вершины i , и 0, если вершина i и ребро j не инцидентны.. Это правило применяется к ссылке, столбец которой будет иметь две ненулевые записи с абсолютным значением 1, полуребер, столбец которого имеет единственную ненулевую запись +1 или -1, и свободный край, столбец которого имеет только нули. Однако столбец цикла равен нулю, если цикл положительный, а если цикл отрицательный, у него есть запись ± 2 в строке, соответствующей его инцидентной вершине.

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

Отрицание строки матрицы инцидентности соответствует переключению соответствующей вершины.

Переключение [ править ]

Переключение вершины в Σ означает отмену знаков всех ребер, инцидентных этой вершине. Переключение набора вершин означает отрицание всех ребер, которые имеют один конец в этом наборе и один конец в дополнительном наборе. Переключение серии вершин, по одному разу, аналогично переключению всего набора сразу.

Переключение знаковых графов ( переключение со знаком) обобщено из работы Зейдела (1976), где оно было применено к графам ( переключение графов ) способом, который эквивалентен переключению полных графов со знаком.

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

Переключение набора вершин влияет на матрицу смежности, инвертируя строки и столбцы переключенных вершин. Он влияет на матрицу инцидентности, инвертируя строки переключенных вершин.

Основная теорема [ править ]

Знак пути - произведение знаков его ребер. Таким образом, путь является положительным, только если в нем есть четное число отрицательных ребер (где ноль - четное число). В математической теории баланса в Харарях , подписанный график сбалансирован , когда каждый цикл положителен. Он доказывает, что граф со знаком сбалансирован, когда (1) для каждой пары узлов все пути между ними имеют одинаковый знак или (2) граф разбивается на пару подграфов, каждый из которых состоит из положительных ребер, но соединен отрицательными края. [6] Теорема была опубликована Харари в 1953 году. [1] Она обобщает теорему о том, что обычный (беззнаковый) граф является двудольным. тогда и только тогда, когда каждый цикл имеет четную длину.

Простое доказательство использует метод переключения. Чтобы доказать теорему Харари, можно показать по индукции, что Σ можно переключить, чтобы все было положительно, тогда и только тогда, когда оно сбалансировано.

Более слабая теорема, но с более простым доказательством, заключается в том, что если каждый 3-цикл в полном графе со знаком положительный, то граф сбалансирован. Для доказательства, выбрать произвольный узел п и поместить его и все те узлы, которые связаны с п положительным фронтом в одной группе, называемой , и все те , которые связаны с п отрицательным краем в другой, называемой B . Поскольку это полный граф, каждые два узла в A должны быть друзьями, а каждые два узла в Bдолжны быть друзьями, иначе получился бы несбалансированный 3 цикла. (Так как это полный граф, любое отрицательное ребро вызовет несбалансированный 3-цикл.) Аналогично, все отрицательные ребра должны проходить между двумя группами. [7]

Разочарование [ править ]

Присвойте каждой вершине значение +1 или -1; мы называем это состоянием Σ. Ребро называется удовлетворенным, если оно положительное и обе конечные точки имеют одинаковое значение, или оно отрицательное и конечные точки имеют противоположные значения. Неудовлетворенное ребро называется фрустрированным . Наименьшее количество фрустрированных ребер по всем состояниям называется индексом фрустрации (или линейным индексом баланса ) Σ. Найти индекс разочарования - непростая задача. Aref et al. предложить модели бинарного программирования, которые способны вычислить индекс фрустрации графов с количеством ребер до 10 5 за разумное время. [8] [9] [10] Можно увидеть NP-сложную сложность, заметив, что индекс фрустрации полностью отрицательного знакового графа эквивалентен задаче максимального разреза в теории графов, которая является NP-сложной. Причина эквивалентности в том, что индекс фрустрации равен наименьшему количеству ребер, отрицание которых (или, что то же самое, удаление; теорема Харари) уравновешивает Σ. (Это легко проверить переключением.)

Индекс фрустрации важен в модели спиновых стекол , смешанной модели Изинга . В этой модели фиксированный граф со знаком. Состояние состоит из придания каждой вершине вращения вверх или вниз. Мы думаем, что вращение вверх - это +1, а вращение вниз - как -1. Таким образом, у каждого состояния есть несколько фрустрированных краев. Энергия состояния больше, когда у него больше фрустрированных краев, поэтому основное состояние - это состояние с наименьшей фрустрированной энергией. Таким образом, чтобы найти энергию основного состояния Σ, нужно найти индекс фрустрации.

Теория матроидов [ править ]

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

Матроид кадра (или знаково-графический матроид ) М ( G ) имеет свое заземление установить множество ребер E . [11] Набор ребер является независимым, если каждый компонент не содержит кругов или только один круг, что отрицательно. (В теории матроидов полуребро действует точно так же, как отрицательная петля.) Контур матроида представляет собой либо положительную окружность, либо пару отрицательных окружностей вместе с соединяющим простым путем, так что две окружности либо не пересекаются (тогда соединительный путь имеет один конец, общий с каждым кругом, и в противном случае не пересекается с обоими) или имеет только одну общую вершину (в этом случае соединительный путь - это эта единственная вершина). Ранг множества ребер Sравно n - b , где n - количество вершин графа G, а b - количество сбалансированных компонентов S , при этом изолированные вершины считаются сбалансированными компонентами. Этот матроид является матроидом столбцов матрицы инцидентности графа со знаком. Поэтому он описывает линейные зависимости корней классической корневой системы.

Расширенный лифт матроид L 0 ( G ) имеют для его заземления установлено множество Й 0 Союза множества ребер Е с дополнительной точкой , которую мы обозначим е 0 . Подъемник матроид L ( G ) является расширенной лифт матроиды ограничивается E. Дополнительная точка действует точно так же, как отрицательный цикл, поэтому мы описываем только матроид подъема. Набор ребер является независимым, если он не содержит окружностей или только один круг, что отрицательно. (Это то же самое правило, которое применяется отдельно к каждому компоненту матроида со знаковой графикой.) Схема матроида - это либо положительный круг, либо пара отрицательных кругов, которые либо не пересекаются, либо имеют только общую вершину. Ранг множества ребер S равен n - c + ε, где c - количество компонентов S , считая изолированные вершины, и ε равно 0, если S сбалансировано, и 1, если нет.

Другие виды «подписанного графа» [ править ]

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

Термин « граф со знаком» иногда применяется к графам, в которых каждое ребро имеет вес, w ( e ) = +1 или -1. Это не тот же тип графа со знаком; это взвешенные графы с ограниченным набором весов. Разница в том, что веса складываются, а не умножаются. Проблемы и методы совершенно разные.

Это имя также применяется к графам, в которых знаки функционируют как цвета на краях. Значение цвета заключается в том, что он определяет различные веса, применяемые к краю, а не в том, что его знак имеет существенное значение. Так обстоит дело в теории узлов , где единственное значение знаков состоит в том, что они могут быть заменены двухэлементной группой, но нет никакой внутренней разницы между положительным и отрицательным. Матроид знакового графа - это матроид цикла нижележащего графа; это не матроид фрейма или подъема графа со знаком. Знаковые метки вместо изменения матроида становятся знаками на элементах матроида.

В этой статье мы обсуждаем только теорию знаковых графов в строгом смысле слова. Для диаграмм со знаками см. Цветные матроиды .

Подписанный орграф [ править ]

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

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

Знаки вершин [ править ]

Вершина подписанного график , который иногда называют Заметный графом , является графом, вершины которого приведены признаки. Круг называется непротиворечивым (но это не связано с логической непротиворечивостью) или гармоничным, если произведение знаков его вершины положительное, и несовместимым или негармоничным, если произведение отрицательное. Не существует простой характеристики гармоничных графов со знаком вершин, аналогичной теореме Харари о балансе; вместо этого характеристика была сложной проблемой, лучше всего решенной (даже в более общем плане) Джоглекаром, Шахом и Диваном (2012). [12]

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

Разница между отмеченным графом со знаком и графом со знаком с функцией состояния (как в § Фрустрация ) состоит в том, что знаки вершины в первом случае являются частью существенной структуры, а функция состояния - это функция переменной на графе со знаком.

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

Раскраска [ править ]

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

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

Приложения [ править ]

Социальная психология [ править ]

В социальной психологии графы со знаком используются для моделирования социальных ситуаций, где положительные грани представляют дружбу, а отрицательные грани - вражду между узлами, которые представляют людей. [3] Тогда, например, положительный 3-цикл - это либо три общих друга, либо два друга с общим врагом; в то время как отрицательный 3-цикл - это либо три общих врага, либо два врага, у которых есть общий друг. Согласно теории баланса , положительные циклы сбалансированы и считаются стабильными социальными ситуациями, тогда как отрицательные циклы несбалансированы и считаются нестабильными. Согласно теории, в случае трех общих врагов это происходит потому, что наличие общего врага может привести к тому, что два врага станут друзьями.. В случае двух врагов, разделяющих друга, общий друг, вероятно, выберет одного из них и превратит одного из своих друзей во врага.

Антал, Крапивский и Редер рассматривают социальную динамику как изменение знака на краю графа со знаком. [13] Социальные отношения с предыдущими друзьями разводящейся пары используются, чтобы проиллюстрировать эволюцию подписанного графа в обществе. Другая иллюстрация описывает меняющиеся международные союзы между европейскими державами за десятилетия до Первой мировой войны . Они рассматривают локальную динамику триад и ограниченную динамику триад, где в последнем случае изменение отношения происходит только тогда, когда общее количество несбалансированных триад уменьшается. Моделирование предполагало полный граф со случайными отношениями, имеющий случайную несбалансированную триаду, выбранную для преобразования. Эволюция знакового графа с N узлы в рамках этого процесса изучаются и моделируются для описания стационарной плотности дружественных ссылок.

Теория баланса подверглась серьезным испытаниям, особенно в ее применении к большим системам, на том теоретическом основании, что дружеские отношения связывают общество вместе, в то время как общество, разделенное на два лагеря врагов, будет крайне нестабильным. [14] Экспериментальные исследования также предоставили лишь слабое подтверждение предсказаний теории структурного баланса. [15]

Спиновые очки [ править ]

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

Сложные системы [ править ]

Знаковый орграф с тремя переменными, представляющий простую трофическую систему

Используя аналитический метод, первоначально разработанный в популяционной биологии и экологии, но теперь используемый во многих научных дисциплинах, знаковые орграфы нашли применение в рассуждениях о поведении сложных причинных систем. [16] [17] Такой анализ отвечает на вопросы об обратной связи на заданных уровнях системы и о направлении переменных реакций при возмущении системы в одной или нескольких точках, переменных корреляциях при таких возмущениях, распределении дисперсии по система, а также чувствительность или нечувствительность отдельных переменных к системным возмущениям.

Кластеризация данных [ править ]

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

Неврология [ править ]

Мозг можно рассматривать как граф со знаком, где синхронность и антисинхронность между паттернами активности областей мозга определяют положительные и отрицательные грани. В связи с этим можно исследовать стабильность и энергию сети мозга. [18]

Обобщения [ править ]

Знаковый граф - это особый вид графа усиления , где группа усиления имеет порядок 2. Пара ( G , B ( Σ )), определяемая графом со знаком Σ, представляет собой особый вид смещенного графа .

Заметки [ править ]

  1. ^ a b Харари, Фрэнк (1955), «О понятии баланса подписанного графа» , Michigan Mathematical Journal , 2 : 143–146, MR  0067468 , заархивировано из оригинала 15 апреля 2013 г.
  2. ^ Konig, Dénes (1936), Akademische Verlagsgesellschaft (ред.), Теорье дер endlichen унд unendlichen графена
  3. ^ a b Картрайт, D .; Харари, Фрэнк (1956). «Структурный баланс: обобщение теории Хайдера» (PDF) . Психологический обзор . 63 (5): 277–293. DOI : 10.1037 / h0046049 .
  4. ^ Стивен Строгац (2010), враг моего врага , The New York Times , 14 февраля 2010
  5. ↑ Заславский, Томас (1998), «Математическая библиография подписанных графиков, графиков усиления и смежных областей» , Электронный журнал комбинаторики , 5 , Dynamic Surveys 8, 124 стр., MR 1744869 .
  6. ^ Дорвин Картрайт и Фрэнк Харари (1979) «Баланс и кластеризация: обзор», страницы с 25 по 50 в « Перспективы исследования социальных сетей» , редакторы: Пол У. Холланд и Сэмюэл Лейнхард, Academic Press ISBN 0-12-352550-0 
  7. ^ Луис фон Ан Лекция по науке в Интернете 3 стр. 28 год
  8. ^ Ареф, Самин; Мейсон, Эндрю Дж .; Уилсон, Марк К. (2019). «Моделирование и вычислительное исследование индекса разочарования в подписанных сетях». arXiv : 1611.09030 [ cs.SI ].
  9. ^ Ареф, Самин; Мейсон, Эндрю Дж .; Уилсон, Марк К. (2018), Голденгорин, Борис (редактор), «Вычисление линейного индекса баланса с использованием оптимизации целочисленного программирования», Задачи оптимизации в теории графов: к 60-летию со дня рождения Грегори З. Гутина , Springer Optimization and its Приложения, Springer International Publishing, стр. 65–84, arXiv : 1710.09876 , doi : 10.1007 / 978-3-319-94830-0_3 , ISBN 9783319948300
  10. ^ Ареф, Самин; Уилсон, Марк С. (2019-04-01). Эстрада, Эрнесто (ред.). «Баланс и разочарование в подписанных сетях». Журнал сложных сетей . 7 (2): 163–189. arXiv : 1712.04628 . DOI : 10,1093 / КОМНЕТ / cny015 . ISSN 2051-1329 . 
  11. ^ Заславский, Томас (1982), "Подписанные графики", дискретное Прикладная математика , 4 (1): 47-74, DOI : 10.1016 / 0166-218X (82) 90033-6 , ЛВП : 10338.dmlcz / 127957 , MR 0676405 . Опечатка. Дискретная прикладная математика , 5 (1983), 248
  12. ^ Манас Джоглекар, Нисарг Шах и Аджит А. Диван (2012), «Сбалансированные групповые помеченные графы», Дискретная математика , т. 312, нет. 9. С. 1542–1549.
  13. ^ Т. Антал, П.Л. Крапивский и С. Реднер (2006) Социальный баланс в сетях: динамика дружбы и вражды
  14. ^ Б. Андерсон, Перспективы исследований социальных сетей , изд. PW Holland и S. Leinhardt. Нью-Йорк: Academic Press, 1979.
  15. ^ Морриссетт, Джулиан О .; Янке, Джон К. (1967). «Никаких отношений и отношений нулевой силы в теории структурного баланса». Человеческие отношения . 20 (2): 189–195. DOI : 10.1177 / 001872676702000207 .
  16. ^ Пуччиа, Чарльз Дж. И Левинс, Ричард (1986). Качественное моделирование сложных систем: введение в анализ петель и усреднение по времени . Издательство Гарвардского университета, Кембридж, Массачусетс.
  17. ^ Дамбахер, Джеффри М .; Ли, Хирам В .; Россиньоль, Филипп А. (2002). «Актуальность структуры сообщества при оценке неопределенности экологических прогнозов». Экология . 83 (5): 1372–1385. DOI : 10,1890 / 0012-9658 (2002) 083 [1372: rocsia] 2.0.co; 2 . JSTOR 3071950 . 
  18. ^ Сабери М, Khosrowabadi R, Хатиби А, Мисич В, С Джафари (январь 2021 года). «Топологическое влияние отрицательных звеньев на стабильность сети мозга в состоянии покоя» . Научные отчеты . DOI : 10.1038 / s41598-021-81767-7 . PMC 7838299 . PMID 33500525 .  

Ссылки [ править ]

  • Картрайт, Д .; Харари, F. (1956), "Структурный баланс: обобщение теории Хайдера", Psychological Review , 63 (5): 277-293, DOI : 10,1037 / h0046049 , PMID  13359597.
  • Зайдель, Дж. Дж. (1976), «Обзор двух графов», Colloquio Internazionale sulle Teorie Combinatorie (Рим, 1973), Tomo I , Atti dei Convegni Lincei, 17 , Рим: Accademia Nazionale dei Lincei , стр. 481–511, Руководство по ремонту  0550136.
  • Заславский, Томас (1998), "Математическая библиография знаковых графиков, графиков усиления и смежных областей" , Электронный журнал комбинаторики , 5 , Dynamic Surveys 8, 124 стр., MR  1744869