Введение

Граф со списком выделенных циклов
В математике, предвзятый граф — это граф со списком выделенных циклов (множеств рёбер простых циклов), таких что если два цикла из списка содержатся в тета-графе, то и третий цикл тета-графа также содержится в списке. Предвзятый граф является обобщением комбинаторных основ графа с усилением и, в частности, знакового графа. Формально, предвзятый граф Ω — это пара (G, B), где B — линейный класс циклов; это, по определению, класс циклов, удовлетворяющий упомянутому выше свойству тета-графа. Подграф или множество рёбер, все циклы которого находятся в B (и не содержит полурёбер), называется сбалансированным. Например, цикл, принадлежащий B, является сбалансированным, а цикл, не принадлежащий B, — несбалансированным. Предвзятые графы представляют интерес главным образом из-за их матроидов, но также и из-за их связи с многоарными квазигруппами. См. ниже.

Технические примечания

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

Примеры

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

Несовершеннолетние

Минор предвзятого графа Ω = (G, B) является результатом любой последовательности операций взятия подграфов и стягивания множеств рёбер. Для предвзятых графов, как и для обычных графов, достаточно взять подграф (который может совпадать с самим графом), а затем стянуть множество рёбер (которое может быть пустым). Подграф Ω состоит из подграфа H базового графа G, с классом сбалансированных циклов, состоящим из тех сбалансированных циклов, которые содержатся в H. Удаление множества рёбер S, обозначаемое Ω − S, – это подграф, содержащий все вершины и все рёбра графа Ω, за исключением рёбер из S.

Стягивание графа Ω – относительно сложная операция. Для стягивания одного ребра e процедура зависит от типа этого ребра. Если e является связью, его стягивают в G. Цикл C в стянутом графе G/e является сбалансированным, если либо C, либо его дополнение является сбалансированным циклом в G. Если e – сбалансированная петля или свободное ребро, оно просто удаляется. Если e – несбалансированная петля или полуребро, оно и его вершина v удаляются; каждое другое ребро, имеющее v в качестве одной из конечных точек, теряет эту конечную точку, так что связь с v в качестве одной конечной точки становится полуребром в другой конечной точке, а петля или полуребро, инцидентное v, становится свободным ребром. При стягивании Ω/S произвольным множеством рёбер S множество рёбер становится E − S. (Пусть G = (V, E).) Множество вершин является классом множеств вершин сбалансированных компонент подграфа (V, S) графа Ω. То есть, если (V, S) имеет сбалансированные компоненты с множествами вершин V1, …, Vk, то Ω/S имеет k вершин V1, …, Vk. Ребро e графа Ω, не входящее в S, становится ребром Ω/S, и каждая конечная точка vi ребра e в Ω, принадлежащая некоторому Vi, становится конечной точкой Vi ребра 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. Матроиды рамы обобщают геометрии Даулинга, связанные с группой (Dowling, 1973). Матроид рамы смещенного 2Cn (см. Примеры выше), не имеющий сбалансированных дигонов, называется вихрем. Он важен в теории структуры матроидов.

Матрой подъемника

Расширенный матроид подъема L0(Ω) имеет в качестве основного множества множество E0, являющееся объединением E и дополнительной точки e0. Матроид подъема L(Ω) — это расширенный матроид подъема, ограниченный E. Дополнительная точка ведёт себя точно как несбалансированная петля или полуребро, поэтому мы описываем только матроид подъема. Множество ребер независимо, если оно не содержит кругов или содержит ровно один несбалансированный круг. Круг — это сбалансированный круг, пара непересекающихся или имеющих только общую вершину несбалансированных кругов, либо тета-граф, все круги которого несбалансированы. Ранг множества ребер S равен n − c + ε, где c — число компонент связности S, включая изолированные вершины, а ε равно 0, если S сбалансирован, и 1, если нет. Миноры матроидов подъема и расширенного подъема частично совпадают с минорами предвзятого графа. Операции удаления совпадают: L(Ω−S) = L(Ω)−S. Операции стягивания совпадают только для сбалансированных множеств ребер: M(Ω/S) = M(Ω)/S, если S сбалансирован, но не совпадают, если S несбалансирован. Если S несбалансирован, то M(Ω/S) = M(G)/S = M(G/S), где M графа обозначает обычный графический матроид. Матроид подъема для 2Cn (см. Примеры выше), не имеющий сбалансированных дигонов, называется шипом. Шипы играют важную роль в теории структуры матроидов.

Многочисленные квазигруппы

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