Графы и их применение

Березина Л.Ю.

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

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

Пособие для учителей. – М.: Просвещение, 1979.

ISBN 978-5-397-00275-2

Количество страниц: 143.

Содержание книги «Графы и их применение»:

3 От автора
Глава I. Первое знакомство с графами
- 6 § 1. Задачи, приводящие к графам
- 10 § 2. Некоторые основные понятия теории графов
  - 10 1. Полный граф. Дополнение графа
  - 11 2. Степень вершины
  - 16 3. Путь в графе. Цикл
  - 17 4. Связность графа
  - 19 5. Операция удаления ребра. Мост
- 21 § 3. Деревья. Лес
- 24 § 4. Изображение графа
Глава II. Плоские графы
- 28 § 1. Представление о плоском графе
- 31 § 2. Формула Эйлера
- 33 § 3. Триангулированный граф
- 34 § 4. Изображение ребер плоского графа прямолинейными отрезками
- 37 § 5. Эйлеровы графы
- 42 § 6. Лабиринты
- 44 § 7. Гамильтоновы циклы и пути в графах
Глава III. Графы с цветными ребрами
- 51 § 1. Свойства полных графов с цветными ребрами
- 56 § 2. Графы помогают решать задачи
- 59 § 3. Задача о несцепленных треугольниках с одноцветными сторонами
Глава IV. Ориентированные графы
- 62 § 1. Исходные понятия
- 64 § 2. Полный ориентированный граф
  - 65 1. Круговые бескомпромиссные турниры
  - 67 2. Парадоксы «голосования с предпочтением»
Глава V. Отношения
- 71 § 1. Квадрат множества
- 74 § 2. Свойства отношений
  - 74 1. Рефлексивность
  - 75 2. Антирефлексивность
  - 76 3. Симметричность
  - 77 4. Антисимметричность
  - 78 5. Транзитивность
  - 79 6. Антитранзитивность
  - 80 7. Полное отношение
- 83 § 3. Отношение эквивалентности
- 84 § 4. Отношение порядка
- 88 § 5. Определение графа
Глава VI. Деревья в работе
- 90 § 1. Деревья и подсчет числа изомеров
- 93 § 2. Число деревьев с пронумерованными вершинами
- 94 § 3. Отыскание кратчайшего пути
- 96 § 4. Деревья в комбинаторике
  - 96 1. Деревья и перестановки из n элементов
  - 97 2. Маршруты по местности и число сочетаний С_n^m
  - 98 3. Разбиения и композиции натуральных чисел
- 101 § 5. Деревья, вероятность, генетика
- 103 § 6. Крестики и нолики
Глава VII. Сетевое планирование и управление
- 105 § 1. Сетевой график
- 110 § 2. Построение сетевого графика
- 115 § 3. Критический путь
- 119 § 4. О резервах времени
- 123 § 5. Из истории систем сетевого планирования и управления
Глава VIII. Графы и матрицы
- 125 § 1. Матрицы графа
- 127 § 2. Операции над матрицами
131 Что читать дальше
135 Ответы и указания