Теория графов, Харари Ф., 2003

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




ГРАФЫ.
Большинство специалистов по теории графов употребляют в книгах, статьях и лекциях свою собственную терминологию. На конференциях по теории графов каждый выступающий, чтобы избежать неправильного понимания, считает необходимым определить прежде всего язык, которым он будет пользоваться. Даже само слово «граф» не является священным. Некоторые авторы действительно определяют «граф» как граф), другие же имеют в виду такие понятия, как мультиграф, псевдограф, ориентированный граф или сеть. Нам кажется, что единообразие в терминологии теории графов никогда не будет достигнуто, но, может быть, оно и не к чему.

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

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



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Теория графов, Харари Ф., 2003 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: учебник по математике :: математика :: Харари