Нажав на кнопку "Скачать архив", вы скачаете нужный вам файл совершенно бесплатно.
Перед скачиванием данного файла вспомните о тех хороших рефератах, контрольных, курсовых, дипломных работах, статьях и других документах, которые лежат невостребованными в вашем компьютере. Это ваш труд, он должен участвовать в развитии общества и приносить пользу людям. Найдите эти работы и отправьте в базу знаний.
Мы и все студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будем вам очень благодарны.
Чтобы скачать архив с документом, в поле, расположенное ниже, впишите пятизначное число и нажмите кнопку "Скачать архив"
История возникновения, основные понятия графа и их пояснение на примере. Графический или геометрический способ задания графов, понятие смежности и инцидентности. Элементы графа: висячая и изолированная вершины. Применение графов в повседневной жизни.
курсовая работа , добавлен 20.12.2015
Основные понятия теории графов. Маршруты и связность. Задача о кёнигсбергских мостах. Эйлеровы графы. Оценка числа эйлеровых графов. Алгоритм построения эйлеровой цепи в данном эйлеровом графе. Практическое применение теории графов в науке.
курсовая работа , добавлен 23.12.2007
Спектральная теория графов. Теоремы теории матриц и их применение к исследованию спектров графов. Определение и спектр предфрактального фрактального графов с затравкой регулярной степени. Связи между спектральными и структурными свойствами графов.
дипломная работа , добавлен 05.06.2014
Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".
курсовая работа , добавлен 08.10.2014
Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
курсовая работа , добавлен 30.09.2014
Основные понятия теории графов. Расстояния в графах, диаметр, радиус и центр. Применение графов в практической деятельности человека. Определение кратчайших маршрутов. Эйлеровы и гамильтоновы графы. Элементы теории графов на факультативных занятиях.
дипломная работа , добавлен 19.07.2011
Основные понятия теории графов. Степень вершины. Маршруты, цепи, циклы. Связность и свойства ориентированных и плоских графов, алгоритм их распознавания, изоморфизм. Операции над ними. Обзор способов задания графов. Эйлеровый и гамильтоновый циклы.
презентация , добавлен 19.11.2013
2012-07-26 в 10:21
Алексеев В.В., Гаврилов Г.П., Сапоженко А.А. (ред.) Теория графов. Покрытия, укладки, турниры. Сборник переводов - М. : Мир, 1974.- 224 с.
|
2012-07-26 в 10:35
Донец Г.А., Шор Н.3. Алгебраический подход к проблеме раскраски плоских графов - К.: Наукова думка, 1982. - 144 с.
|
2012-07-26 в 10:44
Содержание
От автора 4
Введение 5
ГЛАВА 1. ИДЕНТИФИКАЦИЯ 12
§1.1. Обыкновенные графы 12
§ 1.2. Изоморфизм 15
§ 1.3. Инварианты 21
§ 1.4. Вычисление инвариантов 31
§ 1.5. Проблема изоморфизма 41
§ 1.6. Некоторые применения плотности и неплотности 47
§ 1.7. Алгоритмы для плотности, неплотности и изоморфизма 56
§ 1.8. Оценки плотности и неплотности. Граф Турана 65
§ 1.9. Оптимальные и критические графы 73
§ 1.10. Проблемы восстановления 80
ГЛАВА 2. СВЯЗНОСТЬ 96
§ 2.1. Маршруты 96
§2.2. Блоки 108
§2.3. Деревья 118
§ 2.4. Паросочетания и двудольные графы 125
§ 2.5.1-связные графы 137
§ 2.6. Взвешенные графы и метрика 149
§ 2.7. Мультиграфы 162
§ 2.8. Эйлеровы цепи и циклы 171
§ 2.9. Раскраски ребер 176
ГЛАВА 3. ЦИКЛОМАТИКА 188
§ 3.1. Каркасы и разрезы 188
§ 3.2. Пространство суграфов 197
§ 3.3. Матрицы инциденций, разрезов и циклов 202
§ 3.4. Графы с заданными разрезами и циклами 211
§ 3.5. Топологические графы 225
§ 3.6. Планарность 234
§ 3.7. Борьба с пересечениями 252
§ 3.8. Гипотеза Хадвигера 262
§ 3.9. Раскраски плоских триангуляции 275
§ 3.10. Совершенные графы 291
ГЛАВА 4. ОРИЕНТАЦИЯ 305
§ 4.1. Конечные графы общего вида 305
§ 4.2. Достижимость 314
§4.3. Ядра 332
§ 4.4. Ориентируемость 342
§ 4.5. Транзитируемость 350
Добавление. Булевы методы в теории графов 363
Заключение 379
2012-07-26 в 10:55
Калмыков Г. И. Древесная классификация помеченных графов. - М.: ФИЗМАТЛИТ, 2003. - 192 с. - ISBN 5-9221-0333-4.
|
2012-07-26 в 11:48
Камерон П., ван Линт Дж. Теория графов, теория кодирования и блок-схемы - М.:Наука, 1980, 140 стр.
|
2012-07-26 в 11:59
Кристофидес Н. Теория графов. Алгоритмический подход. Пер. с анг. - М.:Мир, 1978, 432 с.
|
2012-07-26 в 12:25
Майника Э. Алгоритмы оптимизации на сетях и графах. Пер. с англ. - М.:Мир,1981, 328 с.
|
2012-07-26 в 12:49
Мелихов А.Н., Берштейн Л.С., Курейчик В.М. Применение графов для проектирования дискретных устройств - М.:Наука, 1974, 304 с.
|
2012-07-26 в 12:53
Мельников О.И. Теория графов в занимательных задачах. Изд.3, испр. и доп. 2009. 232 с.
|
2012-07-26 в 12:57
Оре О. Графы и их применение: Пер. с англ. 1965. 176 с.
|
2012-07-26 в 12:58
Оре О. Теория графов.- 2-е изд.- М.: Наука, Главная редакция физико-математической литературы, 1980, 336 с.
|
2012-07-26 в 12:58
Содержание
Предисловие редактора перевода
Предисловие
Часть I. Теория графов
1. Основные понятия
1.1. Основные определения
1.2. Подграфы и дополнения
1.3. Маршруты, цепи, пути и циклы
1.4. Связность и компоненты графа
1.5. Операций над графами
1.6. Специальные графы.
1.7. Точки сочленения и разделимые графы
1.8. Изоморфизм и 2-изоморфизм
1.9 Замечания, касающиеся литературы
Упражнения
2. Деревья, разрезающие множества и циклы
2.1. Деревья, остовы и кодеревья
2.2. k-деревья, остовные k-деревья, леса
2.3. Ранг и цикломатическое число
2.4. Базисные циклы
2.5. Разрезающие множества
2.6. Разрез
2.7. Базисные разрезающие множества
2.8. Остовы, циклы и разрезающие множества
2.9. Замечания, касающиеся литературы
Упражнения
3. Эйлеровы и гамильтоновы графы
3.1. Эйлеровы графы
3.2. Гамильтоновы графы
3.3. Замечания, касающиеся литературы
Упражнения
4. Графы и векторные пространства
4.1. Группы и поля
4.2. Векторные пространства
4.3. Векторное пространство графа
4.4. Размерность подпространств циклов и разрезов
4.5. Связь между подпространствами циклов и разрезов
4.6. Ортогональность подпространств циклов и разрезов
4.7. Замечания, касающиеся литературы
Упражнения
5. Ориентированные графы
5.1. Основные определения и понятия
5.2. Графы и отношения
5.3. Ориентированные и корневые деревья
5.4. Ориентированные эйлеровы графы
5.5. Ориентированные остовы и ориентированные эйлеровы цепи
5.6. Ориентированные гамильтоновы графы
5.7. Ациклические ориентированные графы
5.8. Турниры
5.9. Замечания, касающиеся литературы
Упражнения
6. Матрицы графов
6.1. Матрица инциденций
6.2. Матрица разрезов
6.3. Цикломатическая матрица
6.4. Соотношение ортогональности
6.5. Подматрицы матриц разрезов, инциденций и циклов
6.6. Унимодулярные матрицы
6.7. Число остовов
6.8. Число остовных 2-деревьев
6.9. Число ориентированных остовов в ориентированном графе
6.10 Матрица смежности
6.11. Графы Коутса и Мэзона
6.12. Замечания, касающиеся литературы
Упражнения
7. Планарность и двойственность
7.1. Пленарные графы
7.2. Формула Эйлера
7.3. Теорема Куратовского и другие характеризации планарности
7.4. Двойственные графы
7.5. Планарность и двойственность
7.6. Замечания, касающиеся литературы
Упражнения
8. Связность и паросочетания
8.1. Связность или вершинная связность
8.2. Реберная связность
8.3. Графы с заданными степенями
8.4. Теорема Менгера
8.5. Паросочетания
8.6. Паросочетания в двудольных графах
8.7. Паросочетания графов общего вида
8.8. Замечания, касающиеся литературы
Упражнения
9. Покрытия и раскраски
9.1. Независимые множества и вершинные покрытия
9.2. Реберные покрытия
9.3. Реберная раскраска и хроматический индекс
9.4. Вершинная раскраска,и хроматическое число
9.5. Хроматические полиномы
9.6. Проблема четырех красок
9.7. Замечания, касающиеся литературы
Упражнения
10. Матроиды
10.1. Основные определения
10.2. Фундаментальные свойства
10.3. Эквивалентные системы аксиом
10.4. Двойственность матроидов и графоиды
10.5. Ограничение, сужение и миноры матроида
10.6. Представимость матроидов
10.7. Бинарные матроиды
10.8. Ориентируемые матроиды
10.9. Матроиды и «жадный» алгоритм
10.10. Замечания, касающиеся литературы
Упражнения
Часть II. Теория электрических цепей
11. Графы и электрические цепи
11.1. Преобразование контуров и сечений
11.2. Системы контурных уравнений и уравнений сечений
11.3. Метод смешанных переменных
11.4. Главное разбиение графа
11.5. Уравнения состояния
11.6. Свойство неусиления в резистивных цепях
11.7. Замечания, касающиеся литературы
Упражнения
12. Резистивные n-полюсные цепи
12.1. Введение
12.2. Y-матрицы резистивной n-полюсной цепи ранга п
12.3. Реализация (n+1)-узловых резистивных n-полюсных цепей (подход Седербаума)
12.4. Реализация цикломатической матрицы и матрицы сечений
12.5. Реализация (n+1)-узловых резистивных n-полюсных цепей (подход Гуиллемина)
12.6. Замечания, касающиеся литературы
Упражнения
13. Функция цепи и чувствительность цепи
13.1. Топологические формулы для.RLC-цепей без взаимных индуктивностеq
13.2. Топологические формулы для общих линейных цепей
13.3. Сопряженная цепь и вычисление чувствительности цепи
13.4. Замечания, касающиеся литературы
Упражнения
Часть III. Теория электрических цепей
14. Алгоритмы анализа графов
14.1. Транзитивное замыкание
14.2. Транзитивная ориентация
14.3. Поиск в глубину
14.4. Двусвязность и сильная связность
14.5. Сводимость графа программы
14.6. Доминаторы в графе программы
14.7. Замечания, касающиеся литературы
Упражнения
15. Оптимизационные алгоритмы
15.1. Кратчайшие пути
15.2. Деревья с минимальной длиной взвешенных путей
15.3. Оптимальные деревья бинарного поиска
15.4. Максимальные паросочетания в графе
15.5. Максимальные паросочетания в двудольном графе
15.6. Совершенное паросочетание, оптимальное назначение и составление расписаний
15.7. Потоки в транспортной сети
15.8. Оптимальное ветвление
15.9. Замечания, касающиеся литературы
Упражнения
Литература
Предметный указатель
2012-07-26 в 12:59
Татт У. Теория графов. Пер. с англ. - М.:Мир, 1988, 424 с.
|
2012-07-26 в 12:59
Содержание
Предисловие редактора перевода
Предисловие
1. Введение
§ 1. Что такое граф?
2. Определения и примеры
§ 2. Определения
§ 3. Примеры графов
§ 4. Укладки графов
3. Цепи и циклы
§ 5. Новые определения
§ 6. Эйлеровы графы
§ 7. Гамильтоновы графы
§ 8. Бесконечные графы
4. Деревья
§ 9. Элементарные свойства деревьев
§ 10. Перечисление деревьев
§ 11. Некоторые приложения теории графов
5. Планарность и двойственность
§ 12. Пленарные графы
§ 13. Теорема Эйлера о плоских графах
§ 14. Графы на других поверхностях
§ 15. Двойственные графы
§ 16. Двойственность по Уитни
6. Раскрашивание графов
§ 17. Хроматическое число
§ 18. Два доказательства
§ 19. Раскрашивание карт
§ 20. Реберная раскраска
§ 21. Хроматические многочлены
7. Орграфы
§ 22. Определения
§ 23. Эйлеровы орграфы и турниры
§ 24. Цепи Маркова
8. Паросочетания, свадьбы и теорема Менгера
§ 25. Теорема Холла о свадьбах
§ 26 Теория трансверсалей
§ 27. Приложения теоремы Холла
§ 28. Теорема Менгера
§ 29. Потоки в сетях
9. Теория матроидов
§ 30. Введение в теорию матроидов
§ 31. Примеры матроидов
§ 32. Матроиды и теория графов
§ 33. Матроиды и теория трансверсалей
Послесловие
Приложение
Список литературы
Предметный указатель
Скачать (djvu, 4 Мб) libgen.info
2012-07-26 в 13:02
Глава 4. Графы.
Глава 5. Орграфы.
Глава 6. Перечисление степенной группы.
Глава 7. Суперпозиция.
Глава 8. Блоки.
Глава 9. Асимптотика.
Глава 10. Нерешенные задачи.
Приложение I.
Приложение II.
Приложение III.
Список литературы.
Именной указатели.
Предметный указатель.
Указатель обозначений.
2012-07-26 в 13:03
Diestel R. Graph Theory - Springer, 2005 - 410 pages.
|
Я не люблю цитат. Скажи, что знаешь сам.
Р.Эмерсон (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.
В.П.Козырев
Когда мне было 14 лет, мой отец
был так глуп, что я едва выносил его.
Когда же мне стукнуло 21, я поразился,
увидев, как поумнел старик
за эти 7 лет.
Марк Твен
Существует несколько причин нарастания интереса к теории графов. Неоспорим тот факт, что теория графов применяется в таких областях, как физика, химия, теория связи, проектирование вычислительных машин, электротехника, машиностроение, архитектура, исследование операций, генетика, психология, социология, экономика, антропология и лингвистика. Эта теория тесно связана также со многими разделами математики, среди которых -- теория групп, теория матриц, численный анализ, теория вероятностей, топология и комбинаторный анализ. Достоверно и то, что теория графов служит математической моделью для всякой системы, содержащей бинарное отношение. Графы действуют притягательно и обладают эстетической привлекательностью благодаря их представлению в виде диаграмм. Хотя в теории графов много результатов, элементарных по своей природе, в ней также громадное изобилие весьма тонких комбинаторных проблем, достойных внимания самых искушенных математиков.
Ранние варианты этой книги появились в 1956 г., когда на кафедре математики Мичиганского университета началось регулярное чтение курсов по теории графов и комбинаторному анализу. Было замечено, что с методической точки зрения нецелесообразно приводить доказательства всех формулируемых утверждений. Это позволило включить в курс значительно больше известных результатов, чем было бы возможно в ином случае. Таким образом, книгу можно использовать как пособие, написанное в традиционной манере "метода Мора", когда студент умножает свои познания в математике, стремясь доказать все теоремы, сформулированные без доказательств. Заметим, однако, что некоторые из опущенных доказательств и трудны и длинны. Тот, кто овладеет содержанием этой книги, сможет продолжать изучение специальных тем и применять теорию графов в других областях.
В предлагаемой читателю книге предпринята попытка представить различные направления исследований в теории графов в их логической последовательности, дать исторический экскурс и пояснить изложение при помощи рисунков, иллюстрирующих понятия и результаты. Кроме того, приводятся три приложения с диаграммами графов, ориентированных графов и деревьев. Основное внимание в книге уделяется теоремам, хотя иногда упоминаются и алгоритмы, и приложения.
Предлагаемые в конце каждой главы (кроме первой) упражнения существенно отличаются друг от друга по своей трудности. Номера тех упражнений, которые не являются простыми и не следуют непосредственно из приводимых ранее результатов, набраны жирным шрифтом. Особенно трудные упражнения кроме того помечены звездочкой. Для усвоения излагаемого в книге материала читателю рекомендуется ознакомиться с каждым упражнением. Многие из "более легких" упражнений могут показаться читателю очень трудными, если он не изучил материал соответствующих глав.
Советуем читателю не увязать в гл.2 и ее многочисленных упражнениях, которая сама по себе может быть использована как сокращенный курс по теории графов для студентов первого курса или старшеклассников. Преподаватель найдет в этой книге материал для односеместрового курса по теории графов. В то же время вся книга может служить основой для годового курса. Некоторые из последних глав можно рекомендовать как темы для семинаров повышенного типа. Так как единственным условием для чтения этой книги в действительности является неуловимое свойство, называемое "математической зрелостью", то ее можно использовать в качестве пособия для дипломников и аспирантов. Для понимания последних четырех глав полезно знакомство с элементарной теорией групп и теорией матриц.
Считаю своим долгом выразить благодарность многим моим знакомым за их неоценимую помощь и советы в подготовке этой книги. Ловелл Байнеке и Гари Чартрэнд оказывали наибольшую помощь на протяжении многих лет!
В течение последнего года мои ученики Деннис Геллер, Беннет Манвел и Поль Штокмейер с особым энтузиазмом делились своими замечаниями и предложениями. Большая помощь была также оказана мне Стефаном Хедетниеми, Эдгаром Палмером и Майклом Пламмером. В самое последнее время Бранко Грюнбаум и Доминик Уэлш оказали любезность, тщательно прочитав всю книгу. Я лично отвечаю за все ошибки и за большинство сомнительных мест в изложении.
За последние более чем двадцать лет, посвященных исследованиям в теории графов, я получал поддержку при публикации со стороны Научно-исследовательского управления Военно-воздушных сил США, Национальных институтов здоровья, Национального научного фонда, Управления научных разработок Военно-морского флота и фонда Рокфеллера. В течение этого времени я был рад воспользоваться гостеприимством не только Мичиганского университета, но также и других учебных заведений, которые я имел возможность посетить. Среди них -- Институт повышения квалификации, Принстонский университет, Тавистокский институт социологии в Лондоне, Университетский колледж в Лондоне и Лондонская экономическая школа. Квалифицированно и быстро перепечатали рукопись Алиса Миллер и Анна Дженн из Научно-исследовательского центра групповой динамики. Наконец, я особенно благодарен издательству Аддисон-Уэсли за проявленное терпение в ожидании этой рукописи в течение всех десяти лет с момента заключения контракта, а также за всестороннюю помощь в издании книги.
Фрэнк Харари
Харари Фрэнк (Frank Harary)
Выдающийся американский математик, специалист в области дискретной математики. Родился в Нью-Йорке, в семье еврейских эмигрантов с Ближнего Востока. Окончил Бруклинский колледж, получив степень бакалавра в 1941 г. и магистра в 1945 г. В 1948 г. получил степень доктора философии Калифорнийского университета в Беркли. С 1948 по 1985 гг. занимал должность профессора Мичиганского университета. С 1987 г. - экстраординарный (впоследствии почетный) профессор университета в Лас-Крусес (штат Нью-Мексико).
Фрэнк Харари - автор многочисленных научных работ, книг и статей по теории графов и ее применениям в различных областях знания, особенно в области социальных наук, в том числе лингвистики, социологии, политологии, психологии и др. С лекциями по теории графов он выступал более чем на тысяче научных конференций в 87 странах. Многие его ученики, среди которых 16 докторов наук, стали выдающимися учеными. Он был основателем и членом редакционных коллегий нескольких научных журналов, посвященных дискретной математике, был удостоен почетных ученых степеней в американских и европейских университетах. Его классическая работа «Теория графов» (1969) стала настольной книгой для всех специалистов этого раздела математики.
Пер.с англ. и предисл. В. П. Козырева. Под ред. Г. П. Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6.В последнее время теория графов привлекает всё более пристальное внимание специалистов различных областей знания. Наряду с традиционными применениями ее в таких науках, как физика, электротехника, химия, она проникла и в науки, считавшиеся раньше далекими от неё, - экономику, социологию, лингвистику и др. Давно известны тесные контакты теории графов с топологией, теорией групп и теорией вероятностей. Особенно важная взаимосвязь существует между теорией графов и теоретической кибернетикой (особенно теорией автоматов, исследованием операций, теорией кодирования, теорией игр). Широко используется теория графов при решении различных задач на вычислительных машинах. За последние годы тематика теории графов стала значительно разнообразней; резко увеличилось количество публикаций. Предлагаемая книга написана одним из видных специалистов по дискретной математике. Несмотря на небольшой объём и конспективный характер изложения, книга достаточно полно освещает современное состояние теории графов. Она, безусловно, будет полезна студентам университетов и технических вузов и, несомненно, заинтересует широкие круги научных работников, занимающихся приложениями дискретной математики.Предисловие
Введение Открытие!
Задача о кёнигсбергских мостах
Электрические цепи
Химические изомеры
"Вокруг света"
Гипотеза четырех красок
Теория графов в двадцатом веке Графы
Типы графов
Маршруты и связность
Степени
Задача Рамсея
Экстремальные графы
Графы пересечений
Операции над графами
Упражнения Блоки
Точки сочленения, мосты и блоки
Графы блоков и графы точек сочленения
Упражнения Деревья
Описание деревьев
Центры и центроиды
Деревья блоков и точек сочленения
Независимые циклы и коциклы
Матроиды
Упражнения Связность
Связность и реберная связность
Графические варианты теоремы Менгера
Другие варианты теоремы Менгера
Упражнения Разбиения
Упражнения Обходы графов
Эйлеровы графы
Гамильтоновы графы
Упражнения Реберные графы
Некоторые свойства реберных графов
Характеризация реберных графов
Специальные реберные графы
Реберные графы и обходы
Тотальные графы
Упражнения Факторизация
1-факторизация
2-факторизация
Древесность
Упражнения Покрытия
Покрытия и независимость
Критические вершины и ребра
Ребёрное ядро
Упражнения Планарность
Плоские и планарные графы
Внешнепланарные графы
Теорема Понтрягина - Куратовского
Другие характеризации планарных графов
Род, толщина, крупность, число скрещиваний
УпражненияРаскраски
Хроматическое число
Теорема о пяти красках
Гипотеза четырех красок
Теорема Хивуда о раскраске карт
Однозначно раскрашиваемые графы
Критические графы
Гомоморфизмы
Хроматический многочлен
Упражнения Матрицы
Матрица смежностей
Матрица инциденций
Матрица циклов
Обзор дополнительных свойств матроидов
Упражнения Группы
Группа автоморфизмов графа
Операции на группах подстановок
Группа графа композиции
Графы с данной группой
Симметрические графы
Графы с более сильной симметрией
Упражнения Перечисления
Помеченные графы
Теорема перечислений Пойа
Перечисление графов
Перечисление деревьев
Теорема перечисления степенной группы
Решенные и нерешенные задачи перечисления графов
УпражненияОрграфы
Орграфы и соединимость
Ориентированная двойственность и бесконтурные орграфы
Орграфы и матрицы
Обзор по проблеме восстановления турниров
УпражненияПриложение
Диаграммы графов
Диаграммы орграфов
Диаграммы деревьевСписок литературы и именной указатель
Указатель обозначений
Предметный указатель
ТЕОРИЯ ГРАФОВ
М.: Мир, 1973, 300 стр.
В последнее время теория графов привлекает все более пристальное внимание специалистов различных областей знания. Наряду с традиционными применениями ее в таких пауках, как физика, электротехника, химия, она проникла и в науки, считавшиеся раньше далекими от нее, - экономику, социологию, лингвистику и др. Давно известии тесные контакты теории графов с топологией, теорией групп и теорией вероятностей. Особенно важная взаимосвязь существует между теорией графов и теоретической кибернетикой (особенно теорией автоматов, исследованием операций, теорией кодирования, теорией игр). Широко используется теория графов при решении различных задач на вычислительных машинах.
За последние годы тематика теории графов стала значительно разнообразней; резко увеличилось количество публикаций.
Предлагаемая книга написана одним из видных специалистов по дискретной математике. Несмотря на небольшой объем и конспективный характер изложения, книга достаточно полно освещает современное состояние теории графов. Она, безусловно, будет полезна студентам университетов и технических вузов и, несомненно, заинтересует широкие круги научных работников, занимающихся приложениями дискретной математики.
Предисловие редактора перевода |
|
Введение |
|
Глава 1. Открытие! |
|
Задача о кёнигсбергских мостах |
|
Электрические цепи |
|
Химические изомеры |
|
«Вокруг света» |
|
Гипотеза четырех красок |
|
Теория графов в двадцатом веке |
|
Глава 2. Графы |
|
Типы графов |
|
Маршруты и связность |
|
Задача Рамсея |
|
Экстремальные графы |
|
Графы пересечений |
|
Операции над графами |
|
Упражнения |
|
Глава 3. Блоки |
|
Точки сочленения, мосты и блоки |
|
Графы блоков и графы точек сочленения |
|
Упражнения |
Глава 4. Деревья |
|
Описание деревьев |
|
Центры и центроиды |
|
Деревья блоков и точек сочленения |
|
Независимые циклы и коциклы |
|
Матроиды |
|
Упражнения |
|
Глава 5. Связность |
|
Связность и реберная связность |
|
Графические варианты теоремы Менгера |
|
Другие варианты теоремы Менгера |
|
Упражнения |
|
Глава 6. Разбиения |
|
Упражнения |
|
Глава 7. Обходы графов |
|
Эйлеровы графы |
|
Гамильтоновы графы |
|
Упражнения |
|
Глава 8. Реберные графы |
|
Некоторые свойства реберных графов |
|
Характеризация реберных графов |
|
Специальные реберные графы |
|
Реберные графы и обходы |
|
Тотальные графы |
|
Упражнения |
|
Глава 9. Факторизация |
|
1-факторизация |
|
2-факторизация |
|
Древесность |
|
Упражнения |
|
Глава 10. Покрытия |
|
Покрытия и независимость |
|
Критические вершины и ребра |
|
Реберное ядро |
|
Упражнения |
|
Глава 11. Планарность |
|
Плоские и планарные графы |
|
Внешнепланарные графы |
|
Теорема Понтрягина - Куратовского |
|
Другие характеризации пленарных графов |
|
Род, толщина, крупность, число скрещиваний |
|
Упражнения |
|
Глава 12. Раскраски |
|
Хроматическое число |
Теорема о пяти красках |
||
Гипотеза четырех красок |
||
Теорема Хивуда о раскраске карт |
||
Однозначно раскрашиваемые графы |
||
Критические графы |
||
Гомоморфизмы |
||
Хроматический многочлен |
||
Упражнения |
||
Глава 13. Матрицы |
||
Матрица смежностей |
||
Матрица инциденций |
||
Матрица циклов |
||
Обзор дополнительных свойств матроидов |
||
Упражнения |
||
Глава 14. Группы |
||
Группа автоморфизмов графа |
||
Операции на группах подстановок |
||
Группа графа-композиции |
||
Графы с данной группой |
||
Симметрические графы |
||
Графы с более сильной симметрией |
||
Упражнения |
||
Глава 15. Перечисления |
||
Помеченные графы |
||
Теорема перечисления Пойа |
||
Перечисление графов |
||
Перечисление деревьев |
||
Теорема перечисления степенной группы |
||
Решенные и нерешенные задачи перечисления графов |
||
Упражнения |
||
Глава 16. Орграфы |
||
Орграфы и соединимость |
||
Ориентированная двойственность и бесконтурные орграфы |
||
Орграфы и матрицы |
||
Обзор по проблеме восстановления турниров |
||
Упражнения |
||
Приложение I. Диаграммы графов |
||
Приложение II. Диаграммы орграфов |
||
Приложение III. Диаграммы деревьев |
||
Список литературы и именной указатель |
||
Указатель обозначений |
||
Предметный указатель |
||
Предметный указатель |
||
автоморфизм графа 190 |
базис коциклов 55 |
Циклов 55 |
Внешнепланарный 131 |
Максимальный 131 |
|
валентность вершины 27 |
Вполне несвязный 28 |
вершина графа 22, 126 |
Гамильтонов 85 |
Изолированная 28 |
Геометрически двойственный 138 |
Инцидентная ребру 22 |
Давида 29 |
Концевая 28 |
Двудольный 31 |
Критическая 121 |
Дополнительный 29 |
Неподвижная 201 |
Интервалов 35 |
Орграфа 232 |
|
Периферическая 51 |
Комбинаторно двойственный 139 |
Центральная 51 |
Критический 167 |
Центроидная 52 |
Кубический 28 |
вершинная база 237 |
Леви 205, 206 |
вершины подобные 201 |
Мак-Джи 205 |
Смежные 22, 213 |
Направленный 23 |
вес вершины 52 |
Неразделимый 41 |
вес функции 213 |
Несводимый 123 |
Однозначно раскрашиваемый 164 |
|
К вершине 52 |
Одноциклический 58 |
Пересечений 33 |
|
внешность цикла 134 |
Петерсена 113 |
выпуклый полиэдр 130 |
Планарный 127 |
гипотеза Улама 25, 26, 48, 58, 202, |
Максимальный 128 |
Плоский 127 |
|
Хадвигера 161, 162 |
Подразбиений 101 |
Четырех красок 151, 156-162, 164, |
Полный 29 |
граф полный двудольный 32 |
|
гомоморфизм графа 169 |
N-дольный 37 |
Полный порядка л 169 |
Полунесводимый 123 |
Элементарный 169 |
Помеченный 23 |
гомоморфный образ графа 196 |
Произвольно гамильтонов 89 |
граничный оператор 54 |
Проходимый 89 |
Простой 197 |
|
Внешняя 127 |
Реберно-критический 121 |
Внутренняя 127 |
Реберно-регулярный 202 |
граф асимметрический 190 |
Реберно-симметрический 201 |
Ациклический 48 |
Реберный 91, 94 |
Базисный 132 |
Итерированный 91 |
Бесконечный 36 |
Регулярный 28 |
Блоков 45 |
Самодополнительный 29 |
И точек сочленения 53 |
Сводимый 123 |
Вершинно-критический 121 |
Симметрический 201 |
Вершинно-симметрический 201 |
Составной 197 |
Тороидальный 142
Тотальный 103
- точек сочленения 45
Тривиальный 22
Хивуда 204
Эйлеров 83
- n-раскрашиваемый 152
N-транзитивный 204
- n-унитранзитивный 204
N-хроматический 152
- \alpha-перестановочный 206 граф-композиция 196 графоид 58 графы гомеоморфные 132
Изоморфные 24, 190
- коспектральные 188 группа 189
Графа 190
Вершинная 190
Диэдральная 195
- знакопеременная 195
Конфигураций 213
Парная 217
- - редуцированная 218
Подстановок 190
Реберная 191
- симметрическая 195
Степенная 194
- тождественная 195
Циклическая 195
группы идентичные 190
- изоморфные 190 дерево 48
- блоков и точек сочленения 54
Корневое 219
- с висячим корнем 220
Входящее 235
Выходящее 235
диагональ блока 47 «диаграмма Хассе» 73 диаметр 27 длина маршрута 27
добавление вершины 25 - ребра 25
дополнение графа 29 достижимость 133 древесность графа 113
дуга 23, 232
животное 227 замощение решетки, 2, 227 звезда (лапа, гроздь) 32 изоморфизм 24 инвариант 24
инцидентность ребра и вершины 22 искаженность графа 149 источник 235 карта плоская 127
- - с корневым ребром 227 квадрат графа 27 квадратный корень графа 38 клетка 204 количество очков 243 клика графа 34 кограница 55
кограничный оператор 54 кодерево 56 колесо 63 комплекс 20
композиция графов 37, 196
Групп 194
компонента 27
Нечетная 108
- односторонняя 233
Сильная 233
- слабая 233 конденсация 234 контур 233
- эйлеров 240 конфигурация 213 конъюнкция 40, 243 корона графов 198 коцикл 55 крупность (зернистость,
шероховатость) 146 лемма Бернсайда 212, 214 лес 48 линия матрицы 71
линейный подграф графа 180
- - орграфа 179 Маршрут 26
Замкнутый 26
- несовершенный 119
Открытый 26
Совершенный 119
Y-сводимый 120
матрица достижимостей 238
Инциденций ISO
Коциклов 184
Обходов 238
- полустепеней захода 239
Исхода 239
Разреженная 241
- смежностей графа 179
Орграфа 237
Циклов 183
матричная теорема о деревьях 178, 181, 239
матроид 57
Бинарный 188
Графический 180
- кографический 180
- коциклов графа 57
Циклов графа 57
Эйлеров 188
многочлен деревьев графа 187 множество вершин 22
- внешне устойчивое 118
- внутренне устойчивое 118
- независимое 57, 108, 118
Разделяющее 64
Ребер 22
мост 41 мультиграф 23
наследственное свойство 119 надграф 24 независимые единицы матрицы 71 обхват 27 объединение графов 36 одноцветный класс 152
ожерелье 212-215, 224, 225
окрестность вершины 197 - замкнутая 197
окружение 27 орбита 211 орграф 232
Бесконтурный 235
- контрафункциональный 236 орграф несвязный 233
Обратный 234
- односторонний 233
Примитивный 246
Реберный 245
Сильный 233
Слабый 233
- строго односторонний 244
Слабый 244
- функциональный 236
Эйлеров 240
ориентация графа 246 остов 55 пара связностей 62
паросочетание 119
- наибольшее 119 перечисляющий ряд для
конфигураций 213
Фигур 213
петля 23 подграф 24
ранг коциклический 56
- циклический 55 размерность симплекса 20 расстояние в графе 27
Орграфе 233
раскраска графа 152
Плоской карты 156
Полная 170
Ребер 159
- t цветами 172 ребра кратные 23
Независимые 108
Подобные 01, 2
- смежные 22 ребро графа 22
- инцидентное вершине 22
Критическое 121
Подразбитое 101
Симметричное 221
род графа 142
- полиэдра 142 сеть 70
система различных представителей
стабилизатор 211 степень вершины 27
Графа 27
Группы 190
Ребра 202
сток 235 стягивание 137
- элементарное 137 сумма графов 37
Групп 193
теорема Вине-Коши 181
- об интерполяции гомоморфизмов
- о пяти красках 151, 155, 156
- перечисления Пойа 211-215, 217, 218
- - степенной группы 224
- Хивуда о раскраске Карт 162-164
BEST 240
толщина графа 145 точка сочленения 41 транзитивная тройка 241 треугольник 26
Нечетный 95
- четный 95 турнир 241
турнир состязаний 245 тэта-граф 85 удаление вершины 25
Ребра 25
укладка графа 126 уравнение характеристики неподобия
для деревьев 221
Эйлера-Пуанкаре 57 фактор графа 106 факторизация графа 106 фигура 213 формула Оттера 222
- Эйлера для полиэдров 127 функция связности 62 связность 60
Локальная 66
- односторонняя 233
Реберная 60
Сильная 233
Слабая 233
хорда 55 хроматический класс 159 - многочлен 173
цветной граф группы 199 центр графа 51
центроид дерева 52 |
Хроматическое 152 |
цепи непересекающиеся 64 |
N-хроматическое 177 |
Реберно-непересекающиеся 64 |
экспоненцирование 208 |
эксцентриситет 51 |
|
Альтернирующая 109 |
элемент графа 103 |
Геодезическая 27 |
элементы соседние 103 |
Простая 26 |
эндоморфизм графа 208 |
ядро вершинное 125 |
|
Гамильтонов 85 |
Реберное 122 |
Графой да 58 |
|
Матроида 57 |
база, 1, 237 |
Простой 26 |
скелет, 1, 127 |
Эйлеров 83 |
|
циклическая тройка 241 |
решетка, 2, 227 |
циклический вектор графа 54 |
решетка, 3, 227 |
цикловой индекс группы 212 |