Главная > Методы обработки данных > Графы, сети и алгоритмы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

10.10. Замечания, касающиеся литературы

Прекрасными работами, содержащими богатую информацию по теории матроидов, являются работы [10.4, 10.12]. В работе [10.13] имеется глава по матроидам. Уилсон [10.14] дает элегантное введение в теорию матроидов. Он раскрывает силу общности матроидов,

включая простые доказательства двух теорем по реберно непересекающимся остовам графа. Кроме первоначальной статьи Уитни [10.1] мы очень рекомендуем для дальнейшего изучения работы [10.15-10.27].

Татт [10.3, 10.17, 10.18] разработал теорию цепных групп и матроидов. Он определил матроид регулярным, если тот изоморфен матроиду регулярной цепной группы. Можно показать, что матроид регулярен тогда и только тогда, когда он представим над всяким полем. В другой характеризации матроид регулярен тогда и только тогда, когда он ориентируем [10.2]. Татт также предложил необходимые и достаточные условия того, что матроид графический. Бинарный матроид является графическим тогда и только тогда, когда он не содержит в качестве минора матроид Фано или двойственный ему, или или Дальнейшее обсуждение этого вопроса можно найти в работах [10.4, 10.19]. (Определение матроида Фано дано в упражнении 10.22.)

Теория связности матроидов дана в работе [10.20]. Теория ориентируемости в применении к матроидам общего вида дается в работах [10.28, 10.29].

Леман [10.16] дал решение игры переключений Шеннона, используя понятие матроида. См. также работы [10.4, 10.30, 10.31].

Красота теории матроидов заключается в ее универсальной природе, приводящей к простым доказательствам результатов теории трансверсалей и теории графов. См. также работы [10.14, 10.24, 10.30].

Работа [10.27] интересна рассмотрением алгоритмов, связанных с матроидами. См. также работы [10.4, 10.32, 10.33].

Теория матроидов находит в настоящее время все возрастающее применение в теории электрических схем. См. работы Бруно и Вейнберг [10.37] дают хорошее введение в теорию матроидов.

<< Предыдущий параграф Следующий параграф >>
Оглавление