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

◄10 април - 16 април
►24 април - 30 април
  • Теми на лекцията от 19.04
    • Транзитивно затваряне
      • Алгоритъм на Уоршал - преговор, Транзитивна редукция, контрол на компании, допълване ан ациксличен граф до слабо свързан
    • Достижимост и свързаност
      • Свързаност - силна и слаба (преговор), компоненти на силна и слаба свързаност
      • Разделящи точки, двусвързаност
      • k-свързаност
    • Оптимални подмножества и центрове
      • Минимално покриващо дърво - МПД свойство, алгоритъм на Прим, алгоритъм на Крускал
      • Независими множества (клики и антиклики)
      • Доминиращи множества
      • База
      • Център и радиус (външен, вътрешен, вътрешно-външен), p-център
      • Двойкосъчетание, максимално двойкосъчетание
    • Оцветяване и планарност
      • Оцветяване и хроматично число - върхово и реброво
      • Планарност на графи, теорема на Куратовски, теорема за четирите цвята
    Примерни теми за упражнения:
    • Транзитивно затваряне и редукция, контрол на компании. Да се експериментира с размяна на реда на циклите
    • Реализация на алгоритъм за намиране на силно свързани компоненти
    • Реализация на алгоритъм за проверка за двусвързаност
    • Реализация на алгоритмите на Прим и Крускал
    • * Оптимизации на алгоритмите на Прим и Крускал
    • * Реализация на максимално двойкосъчетание в двуделен граф
    • * Някой от алгоритмите с пълно изчерпване по избор от следните: максимално независими множества, доминиращи множества, база, хроматично число, проверка за планарност.

◄10 април - 16 април
►24 април - 30 април