Читать онлайн «Теория графов: покрытия, укладки, турниры (сб. переводов)»

ТЕОРИЯ ri'vroit ИЗДАТЕЛЬСТВО-МИ Р- МОСКВА ТЕОРИЯ Г1»\Ч»ОК Покрытия, укладки, турниры Сборник цереводов под редакцией В. В. Алексеева, Г. П. Гаврилова, А. А. Сапоженко ИЗДАТЕЛЬСТВО «МИР» МОСКВА 1974 УДК 519. 1 Идеи и методы теории графов все глубже проникают как в классиче- классические области применения этой теории, например в электротехнику, так и в новые области, например социологию и медицину. Широко используются в приложениях такие понятия теории графов, как «толщина», «число скре- скрещиваний», «род графа», «факторы», «паросочетание». Настоящая книга включает работы самого последнего времени, отно- относящиеся к некоторым важным разделам теории графов. Большинство ста-* тей содержит окончательные результаты, мало известные нашим читате- читателям. Сборник можно рассматривать как существенное дополнение к книге Ф. Харари «Теория графов» («Мир», 1973). Книга заинтересует широкий круг математиков и инженеров, занимаю- занимающихся теорией графов и ее приложениями. Аспиранты и студенты старших курсов технических вузов и университетов могут использовать' ее как учеб- учебное пособие. Редакция литературы по математическим наукам Перевод на русский язык, «Мир», 1974 ПРЕДИСЛОВИЕ РЕДАКТОРОВ ПЕРЕВОДА В предлагаемом вниманию читателя сборнике переводов содержатся работы, относящиеся к наиболее важным разде- разделам теории графов. Один из таких разделов связан с разло- разложением графов и покрытием одних элементов графа другими. Наряду с классической теоремой Татта о существовании у графа 1-фактора1) большой интерес в этом направлении представляют работы Эрдёща и Реньи «О существовании 1-фактора у связного случайного графа», Закса «Об 1-фак- торах n-связных графов» и др. Одна из наиболее знаменитых проблем теории графов — гипотеза четырех красок. Легко формулируемая и потому, в частности, привлекавшая к себе внимание очень многих математиков, она тем не менее до сих пор не решена. По- Попытки решить ее порождали новые интересные проблемы теории графов. К их числу относится гипотеза Хивуда, тесно связанная с гипотезой четырех красок и получившая оконча- окончательное подтверждение лишь в 1968 г. (спустя почти 80 лет после ее формулировки). Несмотря на большую теоретиче- теоретическую и практическую ценность идей, содержащихся в решении этой проблемы, данном Рингелем и Янгсом, существенные детали доказательства теоремы Хивуда пока еще не знакомы широкому кругу советских математиков. Для решения этой проблемы необходимо было осуществить специальную уклад- укладку полных графов на ориентируемых поверхностях данного рода р > О (подробности см. в соответствующих статьях сборника). В сборнике приводятся две работы Рингеля и Янгса, посвященные гипотезе Хивуда. Одна из этих статей — «Решение проблемы Хивуда о раскраске карт» — содержит подробную историю появления и решения проблемы, а также пример, иллюстрирующий технику, используемую авторами при доказательстве теоремы Хивуда. Во второй статье — «Решение проблемы Хивуда о раскраске карт: случай 11» — дается полное доказательство теоремы Хивуда для одного се- семейства значений р.