График усиления

Граф усиления — это граф , ребра которого помечены «обратимо» или «ориентируемо» элементами группы G . Это означает, что если ребро e в одном направлении имеет метку g (элемент группы), то в другом направлении оно имеет метку g. ⁻¹. Таким образом, функция метки φ обладает тем свойством, что она определяется по-разному, но не независимо, в двух разных ориентациях или направлениях ребра e . Группа G называется группой усиления , φ — функцией усиления значение φ ( e ) — усилением e , а (в некотором указанном направлении). Граф усиления — это обобщение знакового графа , где группа усиления G имеет только два элемента. См. Заславский (1989, 1991).

Прирост не следует путать с весом на ребре, значение которого не зависит от ориентации ребра.

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

Некоторыми причинами интереса к графам выигрыша являются их связи с теорией сетевых потоков в комбинаторной оптимизации , с геометрией и физикой .

Математика сети с коэффициентами усиления , или обобщенной сети , связана с фреймовым матроидом графа коэффициентов усиления.
Предположим, у нас есть гиперплоскости в R ^н задается уравнениями вида x _j знак равно g x _i . Геометрию гиперплоскостей можно рассматривать с помощью следующего графа усиления: Множество вершин равно {1,2,..., n }. существует ребро ij с коэффициентом усиления g (в направлении от i до j Для каждой гиперплоскости с уравнением x _j = gx _i ) . Эти гиперплоскости рассматриваются через матроид фрейма графа усиления (Заславский, 2003).
Или предположим, что у нас есть гиперплоскости, заданные уравнениями вида x _j = x _i + g . Геометрию этих гиперплоскостей можно рассматривать, используя граф усиления с тем же набором вершин и ребром ij с усилением g (в направлении от i до j ) для каждой гиперплоскости с уравнением x _j = x _i + g . Эти гиперплоскости изучаются с помощью подъемного матроида графа усиления (Заславский, 2003).
что группа усиления имеет действие на множестве Q. Предположим , Присвоение элемента s _i из Q каждой вершине дает состояние графа усиления. Ребро считается удовлетворенным , если для каждого ребра ij с коэффициентом усиления g (в направлении от i до j уравнение s _j = s _i g ) удовлетворяется ; в противном случае он расстроен . Состояние считается удовлетворенным , если удовлетворяются все ребра. В физике это соответствует основному состоянию (состоянию с наименьшей энергией), если такое состояние существует. Важной проблемой физики, особенно теории спиновых стекол , является определение состояния с наименьшим количеством фрустрированных краев.

Связанные понятия [ править ]

Графы усиления, используемые в топологической теории графов как средство построения вложений графов в поверхности, известны как « графы напряжения » (Gross 1974; Gross and Tucker 1977). Термин «график усиления» более распространен в других контекстах, например, в теории смещенных графов и теории матроидов . термин « граф с метками групп» Также использовался , но он неоднозначен, поскольку «метки групп» могут рассматриваться — и рассматривались — как веса.

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

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

Джонатан Л. Гросс (1974), Графики напряжения. Дискретная математика , Vol. 9, стр. 239–246.
Дж. Л. Гросс и Т. В. Такер (1977), Создание всех покрытий графа путем перестановочного назначения напряжения. Дискретная математика , Vol. 18, стр. 273–283.
Томас Заславский (1989), Смещенные графики. I. Предвзятость, баланс и выгоды. Журнал комбинаторной теории, серия B , Vol. 47, 32–52.
Томас Заславский (1991), Смещенные графики. II. Три матроида. Журнал комбинаторной теории, серия B , Vol. 51, 46–72.
Томас Заславский (1999). Математическая библиография графов знаков и коэффициентов усиления и смежных областей. Электронный журнал комбинаторики , Динамические обзоры по комбинаторике, #DS8 .
Томас Заславский (2003), Смещенные графы IV: Геометрические реализации. Журнал комбинаторной теории, серия B , Vol. 89, нет. 2, стр. 231–297.