Предисловие редактора перевода

Предлагаемая читателю книга посвящена теории графов, которая приобретает все возрастающий интерес у специалистов самых различных областей науки и техники. Привлекательность теории графов объясняется не только широчайшим разнообразием возможностей ее применения, но и красотой результатов, достигаемых простыми средствами. Сделав свои первые шаги еще в XVIII в., она постоянно набирала темпы и в настоящее время вошла в пору юности, когда открыто много путей и не ясно, какой из них главный. Действительно, в рамках теории графов имеется множество различных направлений; результаты ее формулируются с привлечением понятий теории множеств, топологии, алгебры, но методы теории графов нельзя рассматривать как простую совокупность методов этих разделов математики.

Теория графов и мографов (гиперграфов) является эффективным аппаратом формализации современных инженерных и научных задач, как уже сказано, в различных областях знаний. Так, например, в квантовой теории поля взаимодействие элементарных частиц с внешним полем описывается связными графами (диаграммами Фейнмана) [1, 2]; язык теории графов удобен при проведении системных исследований [3], описании организации генетических систем [4], автоматизированном управлении производством [5, 6]. В последнее время большое применение нашла теория графов в современной вычислительной технике и кибернетике: в теоретическом программировании [7], при проектировании ЭВМ на ЭВМ и сетей ЭВМ [8—12], баз данных [13, 14], систем логического управления [5, 14—18].

Книга написана профессором Университета Конкордии (г. Монреаль, Канада) М. Свами и профессором Индийского технологического института (г. Мадрас, Индия) К. Тхуласираманом. Основу ее составили курсы, читаемые авторами для студентов и аспирантов. Сфера научных интересов авторов лежит в области применения теории графов в электрических цепях. Этим объясняется выбор рассмотренной в части II книги области применения теории графов. В этой части рассматриваются графовые свойства цепей и применение графовых методов для реализации цепей с заданными свойствами. Материал этой части специфичен как по терминологии, так и по способам представления и предполагает хорошее знакомство с теорией графов в пределах, обеспечиваемых содержанием части I. Изложение этой части несколько отличается расстановкой, акцентов по сравнению с другими монографиями по теории графов, что обусловлено учебной направленностью книги. С другой стороны, необходимо отметить, что в ней дано одно из самых широких введений в теорию матроидов, существующих в отечественной и переводной литературе.

Часть III также широко использует материал части I. В ней содержится описание множества алгоритмов, которые ориентированы главным образом на применение в вычислительной технике. Способ изложения алгоритмов, принятый в книге, отражает тенденции проявляющиеся при разработке программного обеспечения. Доказана корректность каждого из алгоритмов, и приведены оценки их сложности, что является несомненным достоинством книги. По-видимому, недостаток места не позволил авторам дать введение в теорию NP-полноты, прекрасно сделанное в работе [19].

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

имеет недостатков. Однако квалифицированный специалист найдет в ней знакомый материал.

В книге часто используется термин «характеризация». Авторы понимают под ним любые необходимые и достаточные условия существования некоторого свойства. Мы оставили этот термин без изменения, хотя в отечественной литературе под характеризацией принято понимать определение для данного свойства множества запрещенных фигур.

Перевод выполнен М. В. Горбатовой (гл. 1—4), В. Л. Торховым (предисловие, гл. 5—10), канд. техн. наук С. А. Фроловым (гл. 11—13), В. Н. Четвериковым (гл. 14—15).

В. А. Горбатов

Библиография

1. Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов. — М.: Высшая школа, 1976.

2. Фам Ф. Особенности процессов многократного рассеяния: Пер. с франц. — М.: Мир, 1972.

3. Горбатов В. А. Теория частично упорядоченных систем. — М.: Сов. радио, 1976.

4. Миркин Б. Г., Родин С. Н. Графы и гены. — М.: Наука, 1977.

5. Горбатов В. А., Кафаров В. В., Павлов П. Г. Логическое управление технологическими процессами. — М.: Энергия, 1978.

6. Брегман В. И. Графы в задачах управления производством. — М.: Статистика, 1974.

7. Ершов А. П. Введение в теоретическое программирование. — М.: Наука, 1977,

8. Горбатов В. А. Схемы управления ЦВМ и графы. — М.: Энергия, 1971.

9. Автоматизация проектирования сложных логических структур/ Под редакцией В. А. Горбатова. — М.: Энергия, 1978.

10. Ландау И. Я. Применение ЦВМ для проектирования ЦВМ. — М.: Энергия, 1974.

11. Сети ЭВМ/ Под редакцией В. М. Глушкова. — М.: Связь, 1977.

12. Вычислительные сети и сетевые протоколы: Пер. с англ.— Дэвис Д., Барбер Д., Прайс У., Соломонидес С. — М.: Мир, 1982.

13. Берзтисс А. Т. Структуры данных. — М.: Статистика, 1974.

14. Горбатов В. А., Павлов П. Г., Четвериков В. Н. Логическое управление информационными процессами. — М.: Энергоатомиздат, 1983.

15. Горбатов В. А. Семантическая теория проектирования автоматов. — М.: Энергия, 1979.

16. Горбатов В. А., Останков Б. Л., Фролов С. А. Регулярные структуры автоматного управления. — М.: Машиностроение, 1980.

17. Богомолов А. М., Грунский И. С., Сперанский Д. В. Контроль и преобразования дискретных автоматов. — Киев: Наукова думка, 1975.

18. Мелихов А. Н. Ориентированные графы и конечные автоматы. — М.: Наука, 1971.

19. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов: Пер. с англ. — М.: Мир, 1979.