Съдържание
0. Въведение в предмета чрез една по-сложна задача
1. Основни понятия
2.1. Оптимизационни задачи. Най-къс път. Част 1 - алгоритъм на Дейкстра.
2.2. Оптимизационни задачи. Част 2.
3. Дървета.
4.1 Увод към потоци. Дефиниции и основни твърдения. Алгоритъм за Max-Flow.
4.2 Интересни теореми и задачи върху потоци.
4.3 Потоци в мрежи с минимални стойности. Min Cost Max Flow.
5. Намиране на максимално двойкосъчетание. Blossom trees.
6. Ойлерови цикли и задача за Китайския пощальон.
Конспект:
- Основни понятия и определения в теория на графите и структури от данни за графи.
- Дърво в граф. Определения, свойства, примери. Алгоритъм за построяване на обхващащо дърво.
- Алгоритми на Крускал и Прим за построяване на минимално обхващащо дърво. Задача на Щайнер.
- Пътища и вериги в графи. Алгоритъм на Дийкстра за намиране на най-кратък път. Модификация на Форд.
- Алгоритъм за намиране на всички най-кратки пътища в граф.
- Потокови алгоритми. Алгоритъм за намиране на нарастваща верига.
- Алгоритъм за намиране на максимален поток.
- Теореми на Кьоних-Хол, Кьоних и Кьоних-Егервари (следствия от теоремата на Форд-Фулкерсън).
- Алгоритъм за намиране на поток с минимална стойност. Задачи, родствени на потоковите.
- Задачи за сдвояване (matching). Алгоритъм за намиране на максимално сдвояване.
- Ойлерови цикли в граф.
- Задача на китайския пощальон.
- Задача на търговския пътник.
Литература
[1]. Nicos Christofides. Graph Theory an algorithmic approach. Academic Press, New York, London, San Francisco, 1975. (Превод на руски: Н. Кристофидес. Теория графов алгоритмический подход, Москва, Мир, 1978)
[2]. James R. Evans, Edward Minieka. Optimization Algorithms for Networks and Graphs, 2nd Edition. New York, 1992.
доц. Н. Янев
