В.А. Носов - Основы теории алгоритмов и анализа их сложности (курс лекций), страница 25

Матроид называетсяматричным, если он изоморфен матроиду некоторой матрицы. (Два матроида137(E,J) и (E’,J’) называются изоморфными, если существует биекция f : E → E ′ сусловием A ∈ J ⇔ f ( A) ∈ J ′ ).4. Пусть G =(V,E)- неориентированный граф. Определим M(G)=(E,J), гдеJ={A ⊆ E и граф (V,A) не имеет циклов. Нетрудно показать, что M(G) являетсяматроидом, называемым матроидом графа G.

Матроид называется графовым,если он изоморфен матроиду некоторого графа.Изучение графовых матроидов может быть сведено к матричнымматроидам. Можно показать, что каждый графовый матроид можно трактоватькак матричный матроид, соответствующий матрице инцидентности графа,рассматриваемой как матрица над F2 = { 0 , 1 } .5. Пусть A = ( A1 ,..., An ) - семейство подмножеств конечного множества Е.Напомним, что множество S ⊆ E является частичной трансверсалью семейства А,если существует инъективное отображение f : S → {1,2,..., n} , такое, чтоe ∈ A f ( e ) для каждого e∈S. Пусть J - семейство всех частичных трансверсалеймножества Е. Можно доказать (этот факт есть теорема Эдмонса-Фалкерсона), чтопара (E,J) есть матроид, называемый трансверсальным матроидом.В данном разделе лишь кратко затронута теория матроидов.

На русскомязыке с данной теорией можно ознакомиться в работе [13], где рассмотренытакже и другие алгоритмические вопросы, касающиеся матроидов.138Литература1. Агафонов В.Н. Сложность алгоритмов и вычислений: спецкурс для студентовНГУ, ч.2, Новосибирск, 1975.2. Ахо А., Хопкрофт Дж., Ульман Дж.

Построение и анализ вычислительныхалгоритмов. М., 1979.3. Глухов М.М. Математическая логика. М., в/ч 33965, 1982.4. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.,1982.5. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М., 1983.6. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера.М., 1988.7. Мальцев А.И. Алгоритмы и рекурсивные функции.

М., 1965.8. Марков А.А., Нагорный Н.М. Теория алгоритмов. М., 1984.9. Мятисевич Ю.В. Диофантовы множества. УМН., т.27, вып. 5(167), с.185-222,1972.10. Носов В.А. Специальные главы дискретной математики. М., в/ч 33965, 1990.11. Носов В.А. Основы комбинаторной теории для инженеров. М., в/ч 33965,1990.12. Носов В.А., Сачков В.Н., Тараканов В.Е. Комбинаторный анализ(Неотрицательные матрицы, алгоритмические проблемы) Итоги науки и техники.ВИНИТИ. Сер.

Теория вероятн., Мат.статист. Теорет. киберн., 1983, 21, 120178.13. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. М., 1985.14. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. М.,1972.15. Трахтенброт Б.А. Сложность алгоритмов и вычислений: спецкурс длястудентов НГУ, Новосибирск, 1967.16. Трахтенброт Б.А. Алгоритмы и вычислительные автоматы. М., 1974.17. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия иприложения. М., 1987.18. Шоломов Л.А.

Основы теории дискретных логических и вычислительныхустройств. М., 1980.19. Мендельсон Э. Введение в математическую логику. М., 1971.Задачники.1. Глухов М.М., Шапошников В.А. Задачи и упражнения по математическойлогике. М., в/ч 33965, 1984.2. Лавров И.А., Максимова Л.А. Задачи по теории множеств, математическойлогике и теории алгоритмов. М., 1975.3. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. М.,1977.139.