Войти
В математике смещенный график - это график со списком выделенных кругов (наборы ребер из простых циклов ), так что если два круга в списке содержатся в тета-графе, то третий круг тета-графа является также в списке. Смещенный граф - это обобщение комбинаторных основ графа усиления и, в частности, знакового графа.
Формально смещенный граф Ω представляет собой пару (G, B ), где B - это линейный класс окружностей; это по определению класс кругов, который удовлетворяет упомянутому выше свойству тета-графа.
A подграф или набор ребер, все окружности которого находятся в B (и который не содержит полуребер ), называется сбалансированным . Например, круг, принадлежащий B, сбалансирован, а круг, который не принадлежит B, неуравновешен.
Смещенные графы интересны в основном из-за их матроидов, но также из-за их связи с многоарными квазигруппами. Увидеть ниже.
Смещенный граф может иметь полуребра (одна конечная точка) и свободные ребра (без конечных точек). Ребра с двумя конечными точками бывают двух типов: ссылка имеет две различные конечные точки, а цикл имеет две совпадающие конечные точки.
Линейные классы окружностей являются частным случаем линейных подклассов цепей в матроиде.
A второстепенные смещенного графика Ω = (G, B ) is результат любой последовательности взятия подграфов и сжимающихся множеств ребер. Для смещенных графов, как и для графов, достаточно взять подграф (который может быть целым графом), а затем сжать набор ребер (который может быть пустым набором).
A подграф графа Ω состоит из подграфа H нижележащего графа G с классом сбалансированной окружности, состоящим из тех уравновешенных окружностей, которые находятся в H. удаление множества ребер S, обозначаемое как Ω - S, это подграф со всеми вершинами и всеми ребрами, кроме ребер S.
Сжатие графа Ω относительно сложно. Чтобы сжать одно ребро e, процедура зависит от типа ребра e. Если e - ссылка, сожмите ее в G. Круг C в сокращении G / e сбалансирован, если C или 
При сжатии Ω / S произвольным множеством ребер S это множество ребер E - S. (Пусть G = (V, E).) Множество вершин - это класс множеств вершин сбалансированного компоненты подграфа (V, S) графа Ω. То есть, если (V, S) имеет сбалансированные компоненты с множествами вершин V 1,..., V k, то Ω / S имеет k вершин V 1,..., 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). Матроид кадра смещенного 2C n (см. Примеры выше), который не имеет сбалансированных двуугольников, называется завихрением . Это важно в теории структуры матроидов.
Матроид с увеличенной подъемной силой L0(Ω) имеет в качестве основания набор E 0, который является объединением E с дополнительной точкой e0. Подъемный матроид 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 графика обозначает обычный графический матроид.
Подъемный матроид 2C n (см. Примеры выше), не имеющий сбалансированных дигонов, называется шипом . Шипы очень важны в теории структуры матроидов.
Подобно тому, как групповое расширение полного графа K n кодирует группу (см. геометрия Даулинга ), ее комбинаторный аналог расширяет простой цикл длины n + 1 кодирует n-арную (множественную) квазигруппу. Можно доказывать теоремы о многомерных квазигруппах с помощью смещенных графов (Заславский, т. Д.)
