Схема на раздела

◄3 април - 9 април
►17 април - 23 април
  • Екстремален път в граф. Цикли. Потоци. Транзитивност. Топологично сортиране.

    1. Екстремален път в граф
    - Алгоритъм на Форд-Белман.
    - Алгоритъм на Флойд. Неравенство на триъгълника. Обобщен алгоритъм на Флойд.
    - Алгоритъм на Дейкстра.

    2. Потоци
    - Максимален поток. Алгоритъм на Форд-Фулкерсон. Неефективност на алгоритъма при избиране на произволен подобряващ път.
    - Минимален поток.

    3. Цикли
    - Фундаментално множество цикли. Минимален цикъл през връх.
    - Хамилтонови цикли и задачата за търговския пътник.
    - Ойлерови цикли.

    4. Транзитивност
    - Транзитивно затваряне на граф. Връзка с повдигането на матрицата на съседство на степен.

    5. Топологично сортиране
    - Топологично сортиране
    - Пълно топологично сортиране

    Теми за упражненията:
    - Дейкстра (реализация с масив)
    - Флойд
    - *Фундаментално множество цикли
    - *Ойлеров цикъл
    - *Хамилтонов цикъл
◄3 април - 9 април
►17 април - 23 април