Теория на Графите

Съдържание

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. Ойлерови цикли и задача за Китайския пощальон.

Конспект:

  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.

доц. Н. Янев

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License