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

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

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

Приложения

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

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

Понятия, связанные с данным

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

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

Ссылки

• Джонатан Л. Гросс (1974), графики напряжения. Дискретная математика. 9, pp. 239–246.
• J.L. Гросс и Т. Tucker (1977), Создание всех покрытий графов путем перестановки назначений напряжения. Дискретная математика. 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, pp. 231–297.