- •Типы графов
- •Маршруты и связность
- •Степени
- •Задача Рамсея
- •Экстремальные графы
- •Графы пересечений
- •Операции над графами
- •Графы блоков и точек сочленения
- •Точки сочленения, мосты и блоки
- •Деревья
- •Описание деревьев
- •Центры и центроиды
- •Деревья блоков и точек сочленения
- •Независимые циклы и коциклы
- •Матроиды
- •Обходы графов
- •Эйлеровы графы
- •Гамильтоновы графы
- •Реберные графы
- •Некоторые свойства реберных графов
- •Характеризация реберных графов
- •Специальные реберные графы
- •Реберные графы и обходы
- •Тотальные графы
- •Раскраски
- •Хроматическое число
- •Теорема о пяти красках
- •Гипотеза четырех красок
- •Однозначно раскрашиваемые графы
- •Критические графы
- •Гомоморфизмы
- •Хроматический многочлен
- •Матрицы
- •Матрица смежностей
- •Матрица инциденций
- •Матрица циклов
- •Обзор дополнительных свойств матроидов
- •Связность
- •Связность и реберная связность
- •Орграфы
- •Орграфы и соединимость
- •Ориентированная двойственность и бесконтурные орграфы
- •Орграфы и матрицы
- •Турниры
- •Обзор по проблеме востановления турниров
- •Волновой алгоритм
- •Алгоритм Дейкстры
- •Алгоритм Флойда
- •Алгоритм Йена
- •Алгоритм Краскала
Матроиды
Матроидсостоит из конечного множества М элементов и семейства
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) |CD|!=1 для любых Сe и Dd;
2) ни один из циклов не является собственной частью другого цикла, и ни один коцикл не является собственной частью другого коцикла;
3) если раскрасить элементы множества М так, что точно один элемент будет зеленого цвета, а остальные — красного или синего, то найдется либо
а) цикл С, содержащий зеленый элемент и не содержащий ни одного красного, либо
б) коцикл D, содержащий зеленый элемент и не содержащий ни одного
синего.
Простые циклы любого графа образуют матроид, однако, как мы увидим не каждый матроид можно получить из графа. Два достаточно полных обзора по теории матроидов представлены в статьях Уитни и Татта.
Замечание. Гипотеза Улама для произвольных графов остается еще не решенной. Но П. Келли доказал ее справедливость для деревьев. Мы уже знакомы с интерпретацией этой гипотезы, данной в работе Харари: если граф G имеет р>3 вершин и представлен р непомеченными подграфами G,=G - vi, то сам граф G можно единственным образом восстановить по Gi. Результат Келли для деревьев был обобщен в работе Харари, Палмера , где показано, что каждое нетривиальное дерево Т можно восстановить по тем его подграфам Ti = T-vi, которые сами являются деревьями, т. е. когда vi - висячие вершины. В свою очередь этот результат был улучшен Бонди, доказавшим, что дерево Т можно восстановить по его подграфам Т - vi где vi, - периферические вершины, т. е. вершины, эксцентриситет которых равен диаметру дерева Т. Позже Манвел показал, что почти все деревья Т можно восстановить, если использовать только неизоморфные поддеревья Т - vi. Манвел доказал восстанавливаемость еще в одном классе графов - одноциклических графов, т. е. связных графов, имеющих точно один цикл.