Умножение цепочки матриц (21 апреля 2025)

1. Графы
   1. Рандомизированная 3-связность
   2. Ориентированный граф: вероятностная достижимость
   3. Ориентированный граф: full-for-DAG
   
   
2. Лилия про матрицы:
   1. Сведение к триангуляции
   2. Горизонтальные рёбра, решение задачи, если известно, какие горизонтальные берём
   3. Случай 1-го min: цепочка; как понять брать или не брать? Можно DP за n²; можно жадно: фиктивная вершина, критический вес
   4. Псевдокод для случая 1-го min
   5. Случай леса