dfs (6 ноября 2013)

  1. Циклы
    1. Цикл в неорграфе за O(E)
    2. Цикл в орграфе за O(E)
    3. Цикл через данное ребро за O(E)
    4. Цикл через данную вершину за O(E)
    5. Поиск цикла в неориентированом графе за O(V)
  2. Эйлеров цикл и эйлеров путь
    1. Критерий существования цикла, доказательство
    2. Критерий существования пути, доказательство, сведение к циклу
    3. Критерий для ориентированного графа, доказательство
    4. Разбиение графа на циклы, склейка циклов
    5. Нормальный алгоритм поиска цикла
    6. Разбиение ребер графа на минимальное количество путей (два способа, рекомендуемый: добавление ребер и сведение к циклу)
  3. Реализация Эйлерова цикла
    1. vector [код]
    2. мультисписок [код]
    3. тестируем руками [тест]
    4. генератор для тестирования [код]
  4. Рекурсия
    1. Stack: замеряем память [код]
    2. Изучаем настройки компилятора/операционной системе (python, java, c++) [опции]