Бициркулярный матроид

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

Бициркулярный матроид был представлен Симоэнсом-Перейрой (1972) и далее исследован Мэтьюзом (1977) и другими. Это частный случай фреймового матроида графа смещенного .

Схемы

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

Существует три различных типа бициркулярного графа:

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

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

Квартиры

( Замкнутые множества плоские) бициркулярного матроида графа G можно описать как леса F графа G такие, что в подграфе индуцированном V ( G ) − V ( F ) каждый компонент связности имеет цикл. Поскольку плоскости матроида образуют геометрическую решетку , когда они частично упорядочены включением множества, эти леса G также образуют геометрическую решетку. В частичном упорядочении этой решетки F ₁ ⩽ F _2, если

• каждое дерево компонентов F ₁ либо содержится в каждом дереве F ₂ , либо не пересекается по вершинам с ним , и
• каждая вершина F ₂ является вершиной F ₁ .

В качестве наиболее интересного примера пусть G  ^тот быть G с добавлением цикла в каждую вершину. Тогда квартиры B ( G  ^тот ) — все леса G , остовные и не остовные. Таким образом, все леса графа G образуют геометрическую решетку — решетку леса G ( Заславский 1982 ).

Как трансверсальные матроиды

Бициркулярные матроиды можно охарактеризовать как трансверсальные матроиды , возникающие из семейства множеств , в которых каждый элемент множества принадлежит не более чем двум множествам. То есть независимые множества матроида представляют собой подмножества элементов, которые можно использовать для формирования системы различных представителей некоторых или всех множеств.В этом описании элементы соответствуют ребрам графа, и на каждую вершину приходится один набор, набор ребер, имеющий эту вершину в качестве конечной точки.

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

В отличие от трансверсальных матроидов в целом, бициркулярные матроиды образуют минорно-замкнутый класс ; то есть любой субматроид или сжатие бициркулярного матроида также является бициркулярным матроидом, как видно из их описания в терминах смещенных графов ( Заславский 1991 ). Вот описание удаления и сжатия ребра с точки зрения базового графа: Чтобы удалить ребро из матроида, удалите его из графа. Правило сжатия зависит от того, какое это ребро. Чтобы сжать ссылку (нециклическую) в матроиде, сверните ее в графе обычным способом. Чтобы сжать петлю e в вершине v , удалите e и v, но не другие ребра, инцидентные v; скорее, каждое ребро, инцидентное v и другой вершине w, становится петлей в точке w . Любые другие петли графа в точке v становятся петлями матроида — чтобы правильно описать это в терминах графа, нужны полуребра и свободные ребра; см. предвзятые графы миноров .

Характеристический полином

Характеристический полином бициркулярного матроида B ( G  ^тот ) простым способом выражает количество остовных лесов (лесов, содержащих все вершины G ) каждого размера в G . Формула

$p_{B(G)}(\lambda ):=\sum _{k=0}^{n}(-1)^{k}f_{k}(\lambda -1)^{n-k},$

где fk _{реберных остовных лесов} равно числу k в G. - См. Заславский (1982) .

Векторное представление

Бициркулярные матроиды, как и все другие трансверсальные матроиды, могут быть представлены векторами над любым бесконечным полем . Однако, в отличие от графических матроидов , они не являются регулярными : их нельзя представить векторами над произвольным конечным полем . Вопрос о полях, над которыми бициркулярный матроид имеет векторное представление, приводит к в значительной степени нерешенной проблеме поиска полей, над которыми граф имеет мультипликативный выигрыш . См. Заславский (2007) .

Ссылки

• Мэтьюз, Лоуренс Р. (1977), «Бициркульные матроиды», Ежеквартальный журнал математики , вторая серия, 28 (110): 213–227, doi : 10.1093/qmath/28.2.213 , MR   0505702 .
• Симойнс-Перейра, Ж.М.С. (1972), «О подграфах как матроидных клетках», Mathematical Journal , 127 : 315–322, doi : 10.1007/BF01111390 , MR   0317973 .
• Заславский, Томас (1982), «Бициркулярная геометрия и решетка лесов графа», Ежеквартальный журнал математики , вторая серия, 33 (132): 493–511, doi : 10.1093/qmath/33.4.493 , MR   0679818 .
• Заславский, Томас (1991), «Смещенные графы. II. Три матроида», Журнал комбинаторной теории , серия B, 51 (1): 46–72, doi : 10.1016/0095-8956(91)90005-5 , MR   1088626 .
• Заславский, Томас (2007), «Смещенные графики. VII. Контрабаланс и антинапряжения», Журнал комбинаторной теории , серия B, 97 (6): 1019–1040, doi : 10.1016/j.jctb.2007.03.001 , MR   2354716 .