Матроиды

Матроидсостоит из конечного множества М элементов и семейства

e = {C1, С2,...} непустых подмножеств множества М, называемых циклами, которые удовлетворяют следующим аксиомам:

1) ни одно собственное подмножество цикла не есть цикл;

2) если х C1С2, то C1 и С2 - {х} содержит цикл.

С каждым графом G можно связать матроид, если в качестве множества М взять множество X ребер графа G, а в качестве циклов матроида — простые циклы графа G. Легко видеть, что обе аксиомы выполняются. Несколько менее очевидно, что граф G определяет и другой матроид, если в качестве циклов матроида взять коциклы графа G. Эти матроиды называются соответственно матроидом циклов и матроидом коцикловграфа G.

Дадим другое определение матроида, эквивалентное первому. Матроидсостоит из конечного множества М элементов и семейства подмножеств множества М, называемыхнезависимыми множествами, которые удовлетворяют следующим аксиомам:

1) пустое множество независимо;

2) каждое подмножество независимого множества независимо;

3) для любого подмножества А множества М все максимальные независимые множества, содержащиеся в А, имеют одинаковое число элементов.

Для графа G получим матроид в указанном смысле, если в качестве множества М возьмем совокупность всех ребер графа G, а в качестве независимых множеств — ациклические подграфы графа G.

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

Графоидсостоит из множества М элементов и двух семейств e иdнепустых подмножеств множества М, называемых соответственноциклами и коциклами, которые удовлетворяют следующим аксиомам:

1) |CD|!=1 для любых Сe и Dd;

2) ни один из циклов не является собственной частью другого цикла, и ни один коцикл не является собственной частью другого коцикла;

3) если раскрасить элементы множества М так, что точно один элемент будет зеленого цвета, а остальные — красного или синего, то найдется либо

а) цикл С, содержащий зеленый элемент и не содержащий ни одного красного, либо

б) коцикл D, содержащий зеленый элемент и не содержащий ни одного

синего.

Простые циклы любого графа образуют матроид, однако, как мы увидим не каждый матроид можно получить из графа. Два достаточно полных обзора по теории матроидов представлены в статьях Уитни и Татта.

Замечание. Гипотеза Улама для произвольных графов остается еще не решенной. Но П. Келли доказал ее справедливость для деревьев. Мы уже знакомы с интерпретацией этой гипотезы, данной в работе Харари: если граф G имеет р>3 вершин и представлен р непомеченными подграфами G,=G - vi, то сам граф G можно единственным образом восстановить по Gi. Результат Келли для деревьев был обобщен в работе Харари, Палмера , где показано, что каждое нетривиальное дерево Т можно восстановить по тем его подграфам Ti = T-vi, которые сами являются деревьями, т. е. когда vi - висячие вершины. В свою очередь этот результат был улучшен Бонди, доказавшим, что дерево Т можно восстановить по его подграфам Т - vi где vi, - периферические вершины, т. е. вершины, эксцентриситет которых равен диаметру дерева Т. Позже Манвел показал, что почти все деревья Т можно восстановить, если использовать только неизоморфные поддеревья Т - vi. Манвел доказал восстанавливаемость еще в одном классе графов - одноциклических графов, т. е. связных графов, имеющих точно один цикл.