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


 
Вернуться в: Каталог  
Обложка Харари Ф. Теория графов. Пер. с англ.
Id: 190642
 
525 руб. Бестселлер!

Теория графов. Пер. с англ. Изд.стереотип.
Frank Harary, "Graph Theory". (In Russian)

URSS. 2015. 304 с. Твердый переплетISBN 978-5-9710-1443-0.
Мелованная бумага.

 Аннотация

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

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


 Оглавление

Я не люблю цитат. Скажи, что знаешь сам.
Р.Эмерсон (1803--1882) -- американский писатель и философ.
Предисловие
Введение
Глава 1. Открытие!
 Задача о кенигсбергских мостах
 Электрические цепи
 Химические изомеры
 "Вокруг света"
 Гипотеза четырех красок
 Теория графов в двадцатом веке
Глава 2. Графы
 Типы графов
 Маршруты и связность
 Степени
 Задача Рамсея
 Экстремальные графы
 Графы пересечений
 Операции над графами
 Упражнения
Глава 3. Блоки
 Точки сочленения, мосты и блоки
 Графы блоков и графы точек сочленения
 Упражнения
Глава 4. Деревья
 Описание деревьев
 Центры и центроиды
 Деревья блоков и точек сочленения
 Независимые циклы и коциклы
 Матроиды
 Упражнения
Глава 5. Связность
 Связность и реберная связность
 Графические варианты теоремы Менгера
 Другие варианты теоремы Менгера
 Упражнения
Глава 6. Разбиения
 Упражнения
Глава 7. Обходы графов
 Эйлеровы графы
 Гамильтоновы графы
 Упражнения
Глава 8. Реберные графы
 Некоторые свойства реберных графов
 Характеризация реберных графов
 Специальные реберные графы
 Реберные графы и обходы
 Тотальные графы
 Упражнения
Глава 9. Факторизация
 1-факторизация
 2-факторизация
 Древесность
 Упражнения
Глава 10. Покрытия
 Покрытия и независимость
 Критические вершины и ребра
 Реберное ядро
 Упражнения
Глава 11. Планарность
 Плоские и планарные графы
 Внешнепланарные графы
 Теорема Понтрягина - Куратовского
 Другие характеризации планарных графов
 Род, толщина, крупность, число скрещиваний
 Упражнения
Глава 12. Раскраски
 Хроматическое число
 Теорема о пяти красках
 Гипотеза четырех красок
 Теорема Хивуда о раскраске карт
 Однозначно раскрашиваемые графы
 Критические графы
 Гомоморфизмы
 Хроматический многочлен
 Упражнения
Глава 13. Матрицы
 Матрица смежностей
 Матрица инциденций
 Матрица циклов
 Обзор дополнительных свойств матроидов
 Упражнения
Глава 14. Группы
 Группа автоморфизмов графа
 Операции на группах подстановок
 Группа графа-композиции
 Графы с данной группой
 Симметрические графы
 Графы с более сильной симметрией
 Упражнения
Глава 15. Перечисления
 Помеченные графы
 Теорема перечисления Пойа
 Перечисление графов
 Перечисление деревьев
 Теорема перечисления степенной группы
 Решенные и нерешенные задачи перечисления графов
 Упражнения
Глава 16. Орграфы
 Орграфы и соединимость
 Ориентированная двойственность и бесконтурные орграфы
 Орграфы и матрицы
 Обзор по проблеме восстановления турниров
 Упражнения
Приложение I. Диаграммы графов
Приложение II. Диаграммы орграфов.
Приложение III. Диаграммы деревьев
Список литературы и именной указатель
Указатель обозначений
Предметный указатель

 Предисловие

Прошло 30 лет после выпуска монографии Ф.Харари "Теория графов", но ее привлекательные качества нисколько не потускнели. Унификация терминологии, проведенной автором и широко распространенной благодаря этой книге, стала общепринятой. Преподавание теории графов с использованием книги Ф.Харари ведется во многих вузах нашей страны. За прошедшее время значительно расширилась сфера применения теории графов -- при построении больших вычислительных систем и в программировании, в экономике и на транспорте, в генетике и биологии и т.д. Продолжается значительный рост публикаций, вышел в свет ряд учебных пособий и монографий, среди которых можно отметить книги А.А.Зыкова "Элементы теории графов" (М.: Наука, 1987) и В.А.Емеличева и др. "Лекции по теории графов" (М.: Наука, 1990).

Большое число задач, указанных в книге как нерешенные, нашли свое решение, и часть из них была решена многочисленными учениками Ф.Харари. Сам Ф.Харари, которому сейчас более 80 лет, плодотворно работает и публикуется до сих пор. Особенно значительные успехи за прошедшее время были получены по построению эффективных алгоритмов решения задач теории графов, среди которых нужно отметить алгоритмы построения максимального потока (см.: Адельсон-Вельский Г.М., Диниц Е.А., Карзанов А.В. Потоковые алгоритмы. М.: Наука, 1975). И это несмотря на то, что многие задачи теории графов -- нахождение минимальных раскрасок, покрытий, максимальных полных подграфов, гамильтоновых циклов и др., -- являются NP-полными, т.е. алгоритмически сложными (см.: Гэри М., Джонсон Д. Вычислительные машины и трудноразрешимые задачи. М.: Мир, 1982). Недостаточную оснащенность книги Ф.Харари алгоритмами частично компенсирует книга Н.Кристофидеса "Теория графов. Алгоритмический подход" (М.: Мир, 1978). Обзор результатов по теории графов можно найти в работах: Козырев В.П. Теория графов // Итоги науки и техники. ВИНИТИ, сер. теор. вероятн., мат. стат. и теор. киберн. 1972. Т. 10. С.25--74; Козырев В.П., Юшманов С.В. Теория графов (алгоритмические, алгебраические и метрические проблемы) // Итоги науки и техники. ВИНИТИ, сер. теор. вероятн., мат. стат. и теор. киберн. 1985. Т. 23. С.68--117; Козырев В.П., Юшманов С.В. Представление графов и сетей (кодирование, размещения и укладки) // Итоги науки и техники. ВИНИТИ, сер. теор. вероятн., мат. стат. и теор. киберн. 1990. Т. 27. С.129--196.

11 ноября 2002 г.

В.П.Козырев

 Введение

Когда мне было 14 лет, мой отец был так глуп, что я едва выносил его. Когда же мне стукнуло 21, я поразился, увидев, как поумнел старик за эти 7 лет.
Марк Твен

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

Ранние варианты этой книги появились в 1956 г., когда на кафедре математики Мичиганского университета началось регулярное чтение курсов по теории графов и комбинаторному анализу. Было замечено, что с методической точки зрения нецелесообразно приводить доказательства всех формулируемых утверждений. Это позволило включить в курс значительно больше известных результатов, чем было бы возможно в ином случае. Таким образом, книгу можно использовать как пособие, написанное в традиционной манере "метода Мора", когда студент умножает свои познания в математике, стремясь доказать все теоремы, сформулированные без доказательств. Заметим, однако, что некоторые из опущенных доказательств и трудны и длинны. Тот, кто овладеет содержанием этой книги, сможет продолжать изучение специальных тем и применять теорию графов в других областях.

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

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

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

Считаю своим долгом выразить благодарность многим моим знакомым за их неоценимую помощь и советы в подготовке этой книги. Ловелл Байнеке и Гари Чартрэнд оказывали наибольшую помощь на протяжении многих лет!

В течение последнего года мои ученики Деннис Геллер, Беннет Манвел и Поль Штокмейер с особым энтузиазмом делились своими замечаниями и предложениями. Большая помощь была также оказана мне Стефаном Хедетниеми, Эдгаром Палмером и Майклом Пламмером. В самое последнее время Бранко Грюнбаум и Доминик Уэлш оказали любезность, тщательно прочитав всю книгу. Я лично отвечаю за все ошибки и за большинство сомнительных мест в изложении.

За последние более чем двадцать лет, посвященных исследованиям в теории графов, я получал поддержку при публикации со стороны Научно-исследовательского управления Военно-воздушных сил США, Национальных институтов здоровья, Национального научного фонда, Управления научных разработок Военно-морского флота и фонда Рокфеллера. В течение этого времени я был рад воспользоваться гостеприимством не только Мичиганского университета, но также и других учебных заведений, которые я имел возможность посетить. Среди них -- Институт повышения квалификации, Принстонский университет, Тавистокский институт социологии в Лондоне, Университетский колледж в Лондоне и Лондонская экономическая школа. Квалифицированно и быстро перепечатали рукопись Алиса Миллер и Анна Дженн из Научно-исследовательского центра групповой динамики. Наконец, я особенно благодарен издательству Аддисон-Уэсли за проявленное терпение в ожидании этой рукописи в течение всех десяти лет с момента заключения контракта, а также за всестороннюю помощь в издании книги.

Фрэнк Харари

 Об авторе

Харари Фрэнк (Frank Harary)
Выдающийся американский математик, специалист в области дискретной математики. Родился в Нью-Йорке, в семье еврейских эмигрантов с Ближнего Востока. Окончил Бруклинский колледж, получив степень бакалавра в 1941 г. и магистра в 1945 г. В 1948 г. получил степень доктора философии Калифорнийского университета в Беркли. С 1948 по 1985 гг. занимал должность профессора Мичиганского университета. С 1987 г. — экстраординарный (впоследствии почетный) профессор университета в Лас-Крусес (штат Нью-Мексико).

Фрэнк Харари — автор многочисленных научных работ, книг и статей по теории графов и ее применениям в различных областях знания, особенно в области социальных наук, в том числе лингвистики, социологии, политологии, психологии и др. С лекциями по теории графов он выступал более чем на тысяче научных конференций в 87 странах. Многие его ученики, среди которых 16 докторов наук, стали выдающимися учеными. Он был основателем и членом редакционных коллегий нескольких научных журналов, посвященных дискретной математике, был удостоен почетных ученых степеней в американских и европейских университетах. Его классическая работа «Теория графов» (1969) стала настольной книгой для всех специалистов этого раздела математики.

 
© URSS 2016.

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