книги из ГПНТБ / Басакер Р. Конечные графы и сети

6Ф6.5

Б27

УД К 62-50

Конечные графы н сети, Б а с а к е р Р., С а а т л Т., перевод с английского, Главная редакция физико-математической литературы нзд-ва «Наука», Москва, 1973, 363 стр.

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

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

Илл. 175. Библ. 233 назв.

FINITE GRAPHS AND NETWORKS:

New York — St. Louis — San Francisco Toronto

London — Sydney

О Г Л А В Л Е Н И Е

От редактора перевода Предисловие

ЧА С Т Ь 1

ОС Н О В Ы Т Е О Р И И

Г л а в а 1. Основные понятия: неориентированные графы

1.1.Введение

1.2.Геометрические графы

1.3.Абстрактные графы

1.4.Изоморфизмы н реализации

1.5.Термины, описывающие локальные свойства

1.6.Маршруты, цепи и циклы

1.7.Связность

1.8.Деревья и леса

1.9.Разделяющие множества и разрезы

1.10.Некоторые специальные классы графов Литература

Г л а в а 2. Основные понятия: ориентированные графы

2.1.Введение

2.2.Ориентированные графы

2.3.Термины для описания локальной структуры

2.4. Ориентированные маршруты, пути и контуры .

2.5.Сильная связность

2.6.Деревья и разрезы

2.7. Ориентированные графы и бинарные отношения

Г л а в а 3. Разбиения и расстояния на графах .

3.1.Введение

3.2.Разбиения ребер

3.3.Разбиения дуг

3.4.Гамнльтоновы цени и циклы

3.5.Разбиения вершин

3.6.Радиус и диаметр

3 7 Задачи о минимальных расстояниях Литература .

ПР Е Д И С Л О В И Е

Теория графов дает простой, доступный и мощный инструмент построения моделей и решения задач

ории сетевого планирования и управления ( С П У ) , такти­ ческие и логические задачи, проблемы построения систем связи и исследования процессов передачи информации, выбор оптимальных маршрутов и потоков в сетях, методы

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

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

8 ПРЕДИСЛОВИЕ

становится полезным инструментом при исследовании са­ мых разнообразных систем. Кроме того, теория графов внесла большой вклад в разработку методов а н а л и з а ши­ рокого круга комбинаторных проблем.

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

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

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

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