Смещенный график

В математике смещенный граф — это граф со списком выделенных окружностей (множеств рёбер простых циклов ), такой, что если две окружности в списке содержатся в тета-графе , то третья окружность тета-графа также содержится в списке. Смещенный граф — это обобщение комбинаторных основ графа усиления и, в частности, знакового графа .

Формально смещенный граф Ω — это пара ( G , B ), где B — линейный класс окружностей; по определению это класс окружностей, удовлетворяющий свойству тета-графа, упомянутому выше.

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

Смещенные графы интересны в основном из-за их матроидов , но также из-за их связи с мультиарными квазигруппами . См. ниже.

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

Линейные классы окружностей являются частным случаем линейных подклассов цепей в матроиде .

• Если каждый круг принадлежит B и нет полуребер, Ω сбалансирован. Сбалансированный смещенный граф (для большинства целей) по сути то же самое, что и обычный граф.
• Если B пусто, Ω называется контруравновешенным . Контруравновешенные смещенные графы связаны с бициклическими матроидами .
• Если B состоит из окружностей четной длины, Ω называется антисбалансированным и представляет собой смещенный граф, полученный из полностью отрицательного знакового графа .
• Линейный класс B является аддитивным , то есть замкнутым относительно повторяющейся симметрической разности (когда результатом является окружность), тогда и только тогда, когда B является классом положительных окружностей знакового графа.
• Ω может иметь базовый граф, который является циклом длины n ≥ 3 со всеми удвоенными ребрами. Назовем это смещенным 2 C _n . Такие смещенные графы, в которых ни один двуугольник (окружность длины 2) не сбалансирован, приводят к шипам и завихрениям (см. Матроиды ниже).
• Некоторые виды смещенных графов получаются из графов усиления или являются обобщениями специальных видов графов усиления. К последним относятся смещенные графы расширения , которые обобщают графы группового расширения .

Минор смещенного графа Ω = ( G , B ) является результатом любой последовательности взятия подграфов и сжатия наборов ребер. Для смещенных графов, как и для графов, достаточно взять подграф (который может быть всем графом), а затем сжать набор ребер ( который может быть пустым множеством).

Подграф Ω состоит из подграфа H базового графа G со сбалансированным классом окружностей, состоящим из тех сбалансированных окружностей, которые находятся в H. Удаление множества ребер S , записанное как Ω − S , представляет собой подграф со всеми вершинами и всеми ребрами , за исключением тех , что есть в S.

Стягивание Ω относительно сложно. Чтобы стянуть одно ребро e , процедура зависит от типа ребра e . Если e является связью, стяните его в G . Окружность C в стягивании G / e сбалансирована, если либо C , либо является сбалансированной окружностью G . Если e является сбалансированной петлей или свободным ребром, она просто удаляется. Если это несбалансированная петля или полуребро, она и ее вершина v удаляются; каждое другое ребро с v в качестве конечной точки теряет эту конечную точку, поэтому связь с v в качестве одной конечной точки становится полуребром в своей другой конечной точке, в то время как петля или полуребро в v становятся свободным ребром.${\displaystyle C\чашка e}$

В стягивании Ω/ S произвольным множеством ребер S множество ребер равно E − S . (Мы положим G = ( V , E ).) Множество вершин — это класс множеств вершин сбалансированных компонентов подграфа ( V , S ) графа Ω. То есть, если ( V , S ) имеет сбалансированные компоненты с множествами вершин V ₁ , ..., V _k , то Ω/ S имеет k вершин V ₁ , ..., V _k . Ребро e графа Ω, не входящее в S , становится ребром графа Ω/ S , а каждая конечная точка v _i графа e в графе Ω, принадлежащая некоторому V _{i ,} становится конечной точкой V _i графа e в графе Ω/ S  ; таким образом, конечная точка графа e , не входящая в сбалансированный компонент графа ( V , S ), исчезает. Ребро со всеми конечными точками в несбалансированных компонентах графа ( V , S ) становится свободным ребром в стягивании. Ребро с одной конечной точкой в ​​сбалансированном компоненте ( V , S ) становится полуребром. Ребро с двумя конечными точками, принадлежащими разным сбалансированным компонентам, становится связью, а ребро с двумя конечными точками, принадлежащими одному и тому же сбалансированному компоненту, становится петлей.

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

Каркасный матроид (иногда называемый матроидом смещения ) смещенного графа M (Ω) (Заславский, 1989) имеет в качестве своего базового множества множество ребер E. Множество ребер является независимым, если каждый компонент либо не содержит кругов, либо содержит только один круг, что является несбалансированным. (В теории матроидов полуребро действует как несбалансированная петля, а свободное ребро действует как сбалансированная петля.) M (Ω) является каркасным матроидом в абстрактном смысле, то есть это подматроид матроида, в котором, по крайней мере для одного базиса, набор линий, порожденных парами базисных элементов, покрывает весь матроид. И наоборот, каждый абстрактный каркасный матроид является каркасным матроидом некоторого смещенного графа.

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

Ранг множества ребер S равен n − b , где n — число вершин графа G , а b — число сбалансированных компонентов графа S , включая изолированные вершины в качестве сбалансированных компонентов.

Миноры фреймового матроида согласуются с минорами смещенного графа; то есть M (Ω− S ) = M (Ω)− S и M (Ω/ S ) = M (Ω)/ S .

Каркасные матроиды обобщают геометрии Даулинга , связанные с группой (Даулинг, 1973). Каркасный матроид смещенного 2 C _n (см. Примеры выше), который не имеет сбалансированных двуугольников, называется вихрем . Он важен в теории структуры матроида.

Расширенный подъемный матроид L ₀ (Ω) имеет в качестве своего базового множества множество E ₀ , которое является объединением E с дополнительной точкой e ₀ . Подъемный матроид L (Ω) является расширенным подъемным матроидом, ограниченным E . Дополнительная точка действует точно так же, как несбалансированная петля или полуребро, поэтому мы описываем только подъемный матроид.

Множество ребер является независимым, если оно либо не содержит ни одного круга, либо содержит только один круг, что является несбалансированным.

Контур — это сбалансированная окружность, пара несбалансированных окружностей, которые либо не пересекаются, либо имеют только общую вершину, или тета-граф, все окружности которого несбалансированы.

Ранг множества ребер S равен n − c + ε, где c — число компонентов S , включая изолированные вершины, а ε равно 0, если S сбалансировано, и 1, если нет.

Миноры подъемных и расширенно-подъемных матроидов частично согласуются с минорами смещенного графа. Удаления согласуются: L (Ω− S ) = L (Ω)− S . Сокращения согласуются только для сбалансированных наборов ребер: M (Ω/ S ) = M (Ω)/ S , если S сбалансирован, но не если он несбалансирован. Если S несбалансирован, M (Ω/ S ) = M ( G )/ S = M ( G / S ), где M графа обозначает обычный графический матроид .

Подъемный матроид 2 C _n (см. Примеры выше), не имеющий сбалансированных двуугольников, называется шипом . Шипы играют важную роль в теории структуры матроида.

Подобно тому, как групповое расширение полного графа K _n кодирует группу (см. геометрию Доулинга ), его комбинаторный аналог, расширяющий простой цикл длины n + 1, кодирует n -арную (многоарную) квазигруппу . Можно доказать теоремы о многоарных квазигруппах с помощью смещенных графов (Заславский, ta)

• TA Dowling (1973), Класс геометрических решеток, основанных на конечных группах. Журнал комбинаторной теории, Серия B , Том 14, стр. 61–86.
• Томас Заславский (1989), Смещенные графы. I. Смещение, баланс и выигрыши. Журнал комбинаторной теории, Серия B , том 47, стр. 32–52.
• Томас Заславский (1991), Смещенные графы. II. Три матроида. Журнал комбинаторной теории, Серия B , Том 51, стр. 46–72.
• Томас Заславский (1999). Математическая библиография знаковых и выигрышных графов и смежных областей. Издание 1999 года: Electronic Journal of Combinatorics, Dynamic Surveys in Combinatorics, #DS8, архивное. Текущее издание: Electronic Journal of Combinatorics, Dynamic Surveys in Combinatorics, #DS8.
• Томас Заславский (2012), Ассоциативность в мультиарных квазигруппах: путь смещенных расширений. Aequationes Mathematicae , Vol. 83, стр. 1–66.