URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Оре О. Теория графов. Пер. с англ.
Id: 77112
 
426 руб.

Теория графов. Пер. с англ. Изд.2, стереот.

URSS. 2009. 352 с. Мягкая обложкаISBN 978-5-397-00044-4.

 Аннотация

Настоящая книга, написанная известным норвежским математиком Ойстином Оре, является одним из классических трудов по теории графов, имеющихся в мировой литературе. По сравнению со многими другими аналогичными работами в ней дается более общий и широкий подход к собственно теории графов и значительно более развернутое ее изложение.

Первые пять глав посвящены наглядному материалу и содержат основные понятия и свойства графов. В главе 6 даются основы теории вполне упорядоченных множеств, которая используется в дальнейшем для строгого абстрактного рассмотрения бесконечных графов. В главе 7 особенно подробно излагается вопрос о паросочетаниях; естественным ее продолжением является глава 12. В главах 8--11 рассматриваются ориентированные графы, и затем на языке ориентированных графов изучаются частично упорядоченные множества. Последние три главы (13--15), представляющие немалый интерес, снова имеют дело с более наглядным материалом.

Книга дает достаточно полное представление о направлениях исследований в теории графов. В ней приводятся упражнения и нерешенные задачи; сделана попытка ввести систематическую терминологию. Написана книга ясным и достаточно доступным математическим языком. Она будет полезна специалистам-математикам, инженерам, занимающимся прикладными задачами, и студентам старших курсов университетов и технических вузов.


 Оглавление

От редактора русского перевода
Предисловие
Глава 1. Основные понятия
 1.1. Определения
 1.2. Локальные степени
 1.3. Части и подграфы
 1.4. Бинарные отношения
 1.5. Матрицы смежности и инцидентности
Глава 2. Связность
 2.1. Маршруты, цепи и простые цепи
 2.2. Связные компоненты
 2.3. Взаимно однозначные отображения
 2.4. Расстояния
 2.5. Протяженность
 2.6. Матрицы и цепи. Произведение графов
 2.7. Головоломки
Глава 3. Задачи о цепях
 3.1. Эйлеровы цепи
 3.2. Эйлеровы цепи в бесконечных графах
 3.3. О лабиринтах
 3.4. Гамильтоновы циклы
Глава 4. Деревья
 4.1. Свойства деревьев
 4.2. Центры в деревьях
 4.3. Циклический ранг (цикломатическое число)
 4.4. Однозначные отображения
 4.5. Произвольно вычерчиваемые графы
Глава 5. Листы и блоки
 5.1. Соединяющие ребра и вершины
 5.2. Листы
 5.3. Гомоморфные образы графа
 5.4. Блоки
 5.5. Максимальные простые циклы
Глава 6. Аксиома выбора
 6.1. Полная упорядоченность
 6.2. Принципы максимальности
 6.3. Суммируемые по цепи свойства
 6.4. Максимальные графы исключения
 6.5. Максимальные деревья
 6.6. Соотношения между максимальными графами
Глава 7. Теоремы о паросочетаниях
 7.1. Двудольные графы
 7.2. Дефициты
 7.3. Теоремы о паросочетаниях
 7.4. Взаимные паросочетания
 7.5. Паросочетания в графах частного вида
 7.6. Двудольные графы с положительными дефицитами
 7.7. Применения к матрицам
 7.8. Чередующиеся цепи и максимальные паросочетания
 7.9. Разделяющие множества
 7.10. Совместные паросочетания
Глава 8. Ориентированные графы
 8.1. Отношение включения и достижимые множества
 8.2. Теорема о гомоморфизме
 8.3. Транзитивные графы и погружения в отношения упорядочения
 8.4. Базисные графы
 8.5. Чередующиеся цепи
 8.6. Суграфы первой степени в графе
Глава 9. Ациклические графы
 9.1. Базисные графы
 9.2. Деформации цепей
 9.3. Графы воспроизведения
Глава 10. Частичная упорядоченность
 10.1. Графы частичных упорядочений
 10.2. Представления в виде сумм упорядоченных множесте
 10.3. Структуры и структурные операции Отношения замыкания
 10.4. Размерность в частичном упорядочении
Глава 11. Бинарные отношения и соответствия Галуа
 11.1. Соответствия Галуа
 11.2. Связи Галуа для бинарных отношений
 11.3. Отношения чередующегося произведения
 11.4. Отношения Феррерса
Глава 12. Связывающие цепи
 12.1. Теорема о секущих цепях
 12.2. Вершинное разделение
 12.3. Реберное разделение
 12.4. Дефицит
Глава 13. Доминирующие множества, покрывающие множества и независимые множества
 13.1. Доминирующие множества
 13.2. Покрывающие множества и покрывающие суграфы
 13.3. Независимые множества
 13.4. Теорема Турана
 13.5. Теорема Рамсея
 13.6. Одна задача из теории информации
Глава 14. Хроматические графы
 14.1. Хроматическое число
 14.2. Суммы хроматических графов
 14.3. Критические графы
 14.4. Полиномы раскрашиваний
Глава 15. Группы и графы
 15.1. Группы автоморфизмов
 15.2. Цветные графы Кэли для групп
 15.3. Графы с заданными группами
 15.4. Реберные отображения
Литература
Именной указатель
Предметный указатель

 От редактора русского перевода

Предлагаемая вниманию советского читателя книга О.Оре является второй крупной монографией по теории графов, изданной на русском языке. В 1962 г. вышел перевод книги К.Бержа "Теория графов и ее применения", написанной весьма сжато и абстрактно. Все изложение в ней ведется в сильно алгебраизированной форме. В книге Оре, напротив, графы в большей степени сохраняют свое наглядное, геометрическое содержание, как системы точек, соединенных линиями. Таким образом, обе эти книги хотя и посвящены, в общем, одному кругу вопросов, удачно дополняют друг друга. При этом систематическое изучение теории графов предпочтительнее начинать именно с книги Оре.

Переводчик и редактор благодарны автору книги, любезно предоставившему в наше распоряжение те исправления, которые он вносит в готовящееся второе издание монографии. Существенную помощь в деле упорядочения русской терминологии теории графов оказали советы А.А.Зыкова. Мы весьма признательны ему за это

Н.Н.Воробьев

 Предисловие

Эта книга выросла из курсов лекций по теории графов, которые читались эпизодически в Иельском университете. Первый цикл лекций о бинарных отношениях и графах был прочитан Американскому математическому обществу на летней сессии в Чикаго в 1942 году. В то время рукопись этих лекций не была подготовлена к печати изНза более срочной работы, и соответствующая книга издается теперь в коллоквиум-серии Общества.

Начало теории графов как математической дисциплине было положено Эйлером в его знаменитом рассуждении о Кенигсбергских мостах. Однако эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины прошлого столетия и был сосредоточен главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это благодаря исследованиям электрических сетей, моделей кристаллов и структур молекул. Развитие формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок поддавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за рамки конкретного вопроса. Наиболее знаменитая среди этих задач -- проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 года. Никакая другая проблема не вызывала столь многочисленных и остроумных работ в области теории графов. Благодаря своей простой формулировке и раздражающей неуловимости она до сих пор остается мощным стимулом исследований различных свойств графов.

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

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

По теории графов имеется очень мало книг; основной была книга Д.Кенига (1936), которая для своего времени давала превосходнейшее введение в предмет. Довольно странно, что таких книг на английском языке до сих пор не было, несмотря на то, что многие важнейшие результаты были получены американскими и английскими авторами. В настоящей книге сделана попытка изложить содержание теории графов возможно более просто. Почти все доказательства пересмотрены; включено также значительное число новых результатов. Вводится систематическая терминология, и хочется надеяться, что она окажется удобной).

Для читателя приведено значительное число задач. Многие из них совсем просты; другие носят характер предлагаемых для исследования проблем, они отмечены звездочками.

Второй том будет посвящен более частным вопросам: плоским графам, гипотезе четырех красок, теории потоков, играм, электрическим сетям, а также приложениям к ряду других областей, в которых теория графов является основным инструментом.

Ойстин Оре,
Йельский университет,
Апрель 1960

 Об авторе

Оре Ойстин
Известный норвежский математик, специалист в области алгебры, теории чисел и теории графов. Родился в Христиании (ныне Осло). В 1922 г. окончил университет Христиании, некоторое время учился в Геттингенском университете. С 1926 г. профессор университета Осло (город был переименован в 1925 г.). Через год переехал в США и начал работать в Йельском университете. В 1945 г. вернулся в Норвегию. Был действительным членом Норвежской академии наук, Американского математического общества и Американской академии искусств и наук.

Ойстин Оре — автор более сотни статей и около десятка книг в различных областях математики. Его исследования по алгебре и математическому анализу способствовали развитию многих отраслей знания, в том числе теории информации и кибернетики. Широкую известность получили написанные им биографии выдающихся математиков Абеля и Кардано, научно-популярная книга «Приглашение в теорию чисел», а также работы в области теории графов, к которым относится и книга «Графы и их применение», многократно переиздававшаяся на многих языках мира, в том числе и на русском.

 
© URSS 2016.

Информация о Продавце