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

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

Формально смещенный граф Ω — это пара ( 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 , либо $C\cup e$ является сбалансированным кругом G . Если e — сбалансированный цикл или свободный край, его просто удаляют. Если это несбалансированный контур или полуребро, то он и его вершина v удаляются; каждое другое ребро с v в качестве конечной точки теряет эту конечную точку, поэтому соединение с v в качестве одной конечной точки становится полуребром в другой конечной точке, а петля или полуребро в v становится свободным ребром.

При сжатии Ω/ S произвольным множеством ребер S множество ребер равно E − S . (Пусть G = ( V , E ).) Множество вершин — это класс множеств вершин сбалансированных компонент подграфа ( V , S ) графа Ω. То есть, если ( , S ) имеет сбалансированные компоненты с множествами вершин , _V1 ..., , _то Ω/ S имеет k вершин V1 _Vk ,..., Vk _. V Ребро e области Ω, не входящее в S , становится ребром Ω/ S , и каждая конечная точка области _в e Ω , принадлежащая некоторому V _i, становится конечной точкой Vi _{области} e vi в Ω/ 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 .

Матроиды рамок обобщают геометрии Даулинга , связанные с группой (Dowling, 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 -арную (многомерную) квазигруппу . Теоремы о мультиарных квазигруппах можно доказать с помощью смещенных графов (Заславский, та).

Ссылки

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