Подписаться

Двукруглый матроид

Последняя правка сделана 2021-05-12 03:56:15 Править

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

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

Содержание

  • 1 Цепи
  • 2 Плоскости
  • 3 Как поперечные матроиды
  • 4 Второстепенные
  • 5 Характеристический полином
  • 6 Векторное представление
  • 7 Ссылки

Цепи

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

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

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

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

Плоскости

замкнутые множества (квартиры) двукруглого матроида графа G могут быть описаны как леса F графа G, такие что в индуцированном подграфе графа V (G) - V (F) каждая компонента связности имеет цикл. Поскольку плоскости матроида образуют геометрическую решетку, когда частично упорядочены включением множества, эти леса G также образуют геометрическую решетку. В частичном порядке для этой решетки, что F 1 ≤ F 2 if

  • каждое дерево компонентов F 1 либо содержится в, либо вершинно-непересекающееся из каждого дерева F 2, и
  • каждая вершина F 2 является вершиной F 1.

. Для наиболее интересного примера пусть 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) (λ): = ∑ k = 0 n (- 1) kfk (λ - 1) n - k, {\ displaystyle p_ {B (G)} (\ lambda): = \ sum _ {k = 0} ^ {n} (- 1) ^ {k} f_ {k} (\ lambda -1) ^ {nk },}p_ {B (G)} (\ lambda): = \ sum _ {k = 0} ^ {n} (- 1) ^ {k} f_ {k} (\ lambda -1) ^ {nk},

где f k равно количеству k-реберных покрывающих лесов в G. См. Заславский (1982).

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

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

Ссылки

Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: mail@alphapedia.ru
Соглашение
О проекте