Чтобы определить матроид, определим сначала бинарную группу цепей. Бинарную группу можно наглядно определить так
Бинарная группа цепей --- множество, состоящее из N-значных двоичных чисел (не обязательно всех) и замкнутое относительно групповой операции --- побитного исключающего или. Единицей группы является $\underbrace{0\ldots 0}_{N\text{ нулей}}$ и каждый элемент является себе обратным.В теоретико-множественном определении нужно заменить N-значные двоичные числа на подмножества N-элементного множества, а исключающее или --- на исключающее объединение $(\#1\backslash\#2)\cup(\#2\backslash\#1)$. Почему интересна такая конструкция, потому что эта группа играет важную роль в теории графов.
Пусть у нас есть граф с N ребрами. Возьмем часть его вершин в левую руку (множество этих вершин назовем $A$), а остальные --- в правую ($B$), растянем и порежем все ребра, идущие из одной руки в другую. Множество ребер, которые оказались разрезанными назовем разрезом. Все разрезы данного графа, как нетрудно сообразить, образуют некоторую бинарную группу цепей, которую мы будем обозначать $C$. Действительно, разрез, соответствующий исключающему объединению двух разрезов получается разбиением множества вершин на \[A^{\prime\prime}=(A\cap A^{\prime})\cup (B\cap B^{\prime})\quad\text{ и }\quad B^{\prime\prime}=(A\cap B^{\prime})\cup (B\cap A^{\prime}).\] Кстати, множество ребер, имеющих общую вершину тоже, очевидно, является разрезом (защипнем эту общую вершину и отрежем все ребра, соединяющие ее с остальным графом).
Есть другая бинарная группа цепей, связанная с множеством ребер графа. Рассмотрим все подграфы графа, для которых в каждой вершине сходится четное число ребер. Ясно, что множества ребер таких подграфов (собственно, цепи) образуют бинарную группу цепей $L$.
Заметим, что задание бинарной группы цепей (и, в частности, групп $C$ и $L$) полным перечислением ее элементов представляется довольно избыточным. Вообще, наиболее экономичный способ описания --- это задать мультипликативный базис группы. Понятие матроида бинарной группы цепей лежит где-то на полдороги между полным множеством элементов группы и ее мультипликативным базисом.
Перед тем, как давать формальное определение, поясним суть дела на примере наших групп $C$ и $L$. Рассмотрим сначала некоторый разрез. Может так оказаться, что после разреза в одной или обоих руках окажется несвязный граф (см. картинку). Такой разрез может быть выполнен в два приема и поэтому уж точно бесполезен для построения базиса. Можно сказать, что такой разрез неэлементарный.
Аналогично, многие цепи являются неэлементарными. Это так, если подграф, им соответствующий, несвязен или содержит вершины со степенью 4 или выше (см. пример справа). Вот если мы исключим из $C$ и $L$ (как множеств) неэлементарные элементы, а заодно и единицу группы --- пустое множество, оставшаяся часть и будет называться матроидом. Итак, на теоретико-групповом языке матроид бинарной группы цепей--- подмножество всех элементарных элементов группового множества, т.е., всех непустых элементов, которые не включают в себя никакого другого элемента в качестве подмножества. Для нашего чайниковского определения бинарной группы
Матроид бинарной группы цепей --- подмножество всех таких ненулевых чисел из группового множества, которые обязательно меняются при побитном ИЛИ с любым элементом группы.Все, хватит пока. Про алгоритм Татта напишу как-нибудь в другой раз.
P.S. Кстати, картинки рисованы в SVG-edit, не выходя из браузера, а затем скопипасчены прямо в пост.
