Задание: Разработать набор подпрограмм для преобразования одного метода машинного представления графа в другой.

Тестовые данные:

1. Понятие множества, подмножества, способы задания множеств, операции над множествами.

1) Определение множества, подмножества, мощности конечного множества.

2) Понятие равенства двух множеств.

3) Понятие строгого подмножества.

4) Теорема о числе подмножеств конечного множества.

5) Способы задания множеств:

а) перечислением элементов,

б) порождающей процедурой (не рекурсивные и рекурсивные процедуры, выражение множества через другие множества с помощью операций над множествами),

в) описанием свойств его элементов.

6) Операции над множествами:

а) объединение,

б) пересечение,

в) разность,

БЕЛГОРОДСКАЯ ГОСУДАРСТВЕННАЯ ТЕХНОЛОГИЧЕСКАЯ АКАДЕМИЯ СТРОИТЕЛЬНЫХ МАТЕРИАЛОВ

В.В.МУРОМЦЕВ

АЛГОРИТМЫ НА ГРАФАХ

УЧЕБНОЕ ПОСОБИЕ

Даны основные понятия теории графов. Рассмотрены вопросы представления графов в памяти ЭВМ и ряд существующих алгоритмов на графах. Изложение иллюстрируется примерами сведения прикладных задач к графовым задачам. Затрагиваются общие вопросы построения эффективных алгоритмов. Приведено большое число упражнений, в которых требуется рассматривать вопросы программной реализации графовых алгоритмов и их модификации для решения прикладных задач.

Учебное пособие предназначено для студентов технических и экономических вузов, изучающих программирование.

ВВЕДЕНИЕ

1. ОПРЕДЕЛЕНИЕ ГРАФА

2. ПРЕДСТАВЛЕНИЕ ГРАФОВ В ПАМЯТИ ЭВМ

3. НЕКОТОРЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

ТЕОРИИ ГРАФОВ

4. ОПЕРАЦИИ НАД ГРАФАМИ

5. СВЯЗНОСТЬ

5.1. Построение покрывающих деревьев

5.2. Поиск на графах

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

5.4. Транзитивное замыкание орграфа

6. РАССТОЯНИЕ

6.1. Поиск кратчайших путей между отдельными

вершинами графа

6.2. Поиск кратчайших путей между каждой парой

вершин графа

7. ПОТОКИ

7.1. Условия существования потока

7.2. Поиск увеличивающей цепи

7.3. Поиск максимального потока

7.4. Поиск потока минимальной стоимости

7.5. Задача почтальона для орграфа

СПИСОК ЛИТЕРАТУРЫ

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

Учебное пособие предназначено для студентов технических и экономических вузов, изучающих программирование.

1. ЭЛЕМЕНТАРНЫЕ КОМБИНАТОРНЫЕ ОБЪЕКТЫ И

АЛГОРИТМЫ ИХ ПОРОЖДЕНИЯ

1.1. Основные понятия и определения

1.2. Общие подходы к порождению комбинаторных

объектов

1.3. Алгоритмы порождения подмножеств

1.4. Алгоритмы порождения сочетаний

1.5. Алгоритмы порождения перестановок

1.6. Алгоритм порождения размещений

1.7. Алгоритмы порождения композиций

1.8. Алгоритм порождения разбиений

2. ПРОЕКТИРОВАНИЕ АЛГОРИТМОВ, ОСНОВАННЫХ

НА ПОЛНОМ ПЕРЕБОРЕ ТРАЕКТОРИЙ ЗАДАЧИ

ВЫБОРА

2.1. Понятие задачи выбора

2.2. Комбинаторный поиск

2.3. Использование алгоритмов порождения элементарных

комбинаторных объектов при проектировании

полнопереборных алгоритмов решения задач выбора

3. НЕКОТОРЫЕ ВОПРОСЫ ТЕОРИИ СЛОЖНОСТИ

4. ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

4.1. Порождение подмножеств

4.2. Порождение перестановок

4.3. Порождение сочетаний и размещений

4.4. Порождение композиций и разбиений

4.5. Решение комбинаторных задач

4.6. Проектирование полно переборных алгоритмов