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