КОНСПЕКТ по ТЕОРИЯ НА ГРАФИТЕ

1. Основни понятия и определения в теория на графите и структури от данни за графи.
2. Дърво в граф. Определения, свойства, примери. Алгоритъм за построяване на обхващащо дърво.
3. Алгоритми на Крускал и Прим за построяване на минимално обхващащо дърво. Задача на Щайнер.
4. Пътища и вериги в графи. Алгоритъм на Дийкстра за намиране на най-кратък път. Модификация на Форд.
5. Алгоритъм за намиране на всички най-кратки пътища в граф.
6. Потокови алгоритми. Алгоритъм за намиране на нарастваща верига.
7. Алгоритъм за намиране на максимален поток.
8. Теореми на Кьоних-Хол, Кьоних и Кьоних-Егервари (следствия от теоремата на Форд-Фулкерсън).
9. Алгоритъм за намиране на поток с минимална стойност. Задачи, родствени на потоковите.
10. Задачи за сдвояване (matching). Алгоритъм за намиране на максимално сдвояване.
11. Ойлерови цикли в граф.
12. Задача на китайския пощальон.
13. Задача на търговския пътник.

Литература

[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.

доц. Н. Янев
Януари 2002 г.