English

Конспект

  1. Алгоритми за генериране на пермутации в лексикографски и антилексикографски ред;
    1. Алгоритъм за генериране на пермутации с една транспозиция (на произволни елементи) при преминаване към следваща пермутация;
    2. Алгоритъм за генериране на пермутации с една транспозиция на съседни елементи при преминаване към следваща пермутация;
  3. Алгоритми за генериране на комбинации в лексикографски ред;
  4. Алгоритми за генериране на всички подмножества на дадено множество;
  5. Алгоритми за генериране на подмножества с повторения;
  6. Алгоритми за генериране на всички разбивания на множество;
  7. Граф – основни понятия, видове, значение, представяне (външно и вътрешно). Алгоритъм за обхождане на граф в дълбочина (процедура, фундаментални цикли, определяне на свързани компоненти). Алгоритъм за обхождане на граф в ширина;
  8. Класиращ алгоритъм на възлите на граф (векторен, с подграф, с базов клас);
  9. Понятие за изоморфизъм и автоморфизъм на граф, примери;
  10. Група. Група автоморфизми на граф (образуващи, орбити, ред на групата), пример;
  11. Подгрупа, теорема на Лагранж. Стабилизатор, лема на Бърнсайд. Задаване на група по алгоритъма на Шрайер-Симс;
  12. Алгоритъм за определяне автоморфизмите на граф;
  13. Инварианти и сертификати на дърво и граф;
  14. Алгоритъм за определяне на изоморфизмите на графи;
  15. Алгоритъм за определяне на изоморфното влагане на граф в граф;
  16. Алгоритъм за определяне на максималното изоморфно пресичане на графи;
  17. Алгоритъм на Дейкстра за определяне на най-къс път в граф;
  18. Алгоритъм на Флойд за определяне на всички разстояния в граф;
  19. Алгоритъм за определяне на транзитивното затваряне на граф;
  20. Топологическа сортировка;
  21. Алгоритъм за определяне на Ойлеров цикъл и път в граф;
  22. Алгоритъм на Роберт и Флорес и многоучастъков алгоритъм за определяне на хамилтонов цикъл в граф;
  23. Алгоритъм за максималния поток в тегловен граф.


Основна литература

  • Липский В. Комбинаторика для программистовр "Мир", М., 1988.
  • Кристофидес Н. Теория графов (алгоритмический подход), "Мир", М., 1978.
  • Нечепуренко М.И.(под ред.). Алгоритмы и программы решения задач на графах и сетях, Новосибирск, 1990.
  • Майника. Алгоритмы оптимизации на сетях и графах, "Мир", М., 1981.
  • Ахо А. В., Дж. ". Хопкрофт, Дж. Д. Ульман. Построение и анализ вычислительных алгоритмов., "Мир", Москва, 1979.
    (Aho, A.V., J.E. Hopcroft and J.D. Ullman. The Design and analysis of computer algorithms. Addison - Wesley, Reading, MA, 1976.)
  • Kreher D. L. and Stinson D. R. Combinatorial Algorithms, CRS Press, 1999.

Допълнителна литература

  • Рейнголд Е., Нивергельт Ю., Део Н. Комбинаторные алгоритмы, ‘Мир’, М. 1980.
  • Наков Преслав. Основи на комбинаторните алгоритми, том I, II, София.
  • Смит Т. М. Програмиране с Паскал, София, ‘Техника’, 1996.4. Гроссман Н., Магнус В. Группы и их графы. 'Мир', М., 1971.
  • Кофман А. Введение в прикладную комбинаторику, ‘Наука’, М. 1975.
  • McHugh J. A. Algorithmic graph theory, Prentice - Hall International, London, 1990.
  • Tucker A. Applied combinatorics, John Wiley & Sons, N.Y., 1980.