Минимальный разрез в графе (Каргер-Штейн)

• Алгоритм Каргера-Штейна был опубликован в 1993 году и предназначен для нахождения минимального разреза в графе.  

• Разрез в графе - это разделение множества вершин на два множества.  

• Минимальный разрез - это разделение графа на две компоненты связности с минимальным количеством перевязанных ребер.  

• На примере графа показано, как найти минимальный разрез.  

• Вершины графа разделены на два множества, и минимальный разрез - это удаление двух ребер, чтобы разделить граф на две несвязанные компоненты.  

• Задача поиска минимального разреза используется в различных областях, включая телекоммуникационные сети, анализ изображений и картографические сервисы.  

• Алгоритм поиска минимального разреза может быть использован для определения количества ребер, которые нужно разрезать для разделения графа на две части.  

• Алгоритм используется для сегментации изображений, где он помогает найти независимые множества объектов на картинке.  

• Это позволяет создать пирамиду сегментированных изображений, где каждый уровень иерархии содержит более мелкие объекты.  

• Алгоритм является вероятностным и может выдать минимальный разрез с заданной вероятностью, но также может выдать и не минимальный разрез.  

• Алгоритм основан на стягивании вершин и ребер графа, что позволяет найти минимальный разрез.  

• В ходе стягивания ребер, вершины графа преобразуются в мета-вершины.  

• Если граф связан и не ориентирован, то в итоге останется две вершины, между которыми будет некоторое количество ребер.  

• Эти ребра составляют минимальный разрез графа.  

• Вероятность того, что на первом шаге стягивания ребер не повезло, равна количеству ребер в разрезе, деленному на размер всех ребер.  

• Если на первом шаге стягивания ребер не повезло, то вероятность везения на последующих шагах будет равна 1 минус вероятность везения на первом шаге.  

• Вероятность везения на первом шаге равна 2/n, где n - количество вершин графа.  

• Вероятность везения на последующих шагах больше или равна 1 - 2/n.  

• Автор объясняет, что вероятность успеха в алгоритме поиска минимального разреза равна произведению вероятностей от единицы до размера вершин, минус два, минус два.  

• Это произведение равно двойке, так как последний член сокращается.  

• Вероятность успеха в этом алгоритме очень мала, так как она равна двум-три на квадрат с небольшим.  

• Автор предлагает повторить алгоритм несколько раз, чтобы повысить вероятность успеха.  

• Если повторить алгоритм n раз, вероятность успеха будет приблизительно равна единице минус единица на e в степени n.  

• Если повторить алгоритм два раза, вероятность успеха будет приблизительно две трети больше.  

• Автор оценивает сложность алгоритма как минимум квадратичную, так как алгоритм требует линейного времени для каждого стягивания вершины.  

• Общая сложность алгоритма Крюгера квадратичная, а сложность алгоритма, основанного на вероятностях, равна четвертой степени.  

• Рассматривается классический алгоритм Картера и его оптимизация, которая позволяет значительно уменьшить сложность.  

• После оптимизации алгоритм становится алгоритмом Крюгера-Ойгера-Камеры-Штейнера.  

• Обсуждается идея сохранения данных и использования классической схемы алгоритма для безопасного выкидывания ребер.  

• Упоминается, что на практике подобные алгоритмы работают значительно лучше, чем ожидается в худшем случае.  

• Рассматривается вероятность успеха до определенного предела, который составляет приблизительно 50%.  

• Если вероятность успеха достигает этого предела, то алгоритм продолжает работать с оставшимся количеством вершин.  

• Автор объясняет сложность алгоритма, используя термин "тэ-тайм".  

• Он объясняет, что временная сложность алгоритма выражается как n^2 * log^3(n), где n - количество вершин.  

• Автор объясняет, что оценка сложности алгоритма - это n^2 * log^3(n).  

• Он также упоминает, что оценка может быть квадратной или кубической, но в данном случае она квадратичная.  

• Автор обсуждает применение алгоритма для анализа изображений и геологоразведки.  

• Он также упоминает, что алгоритм может быть использован для сведения к неожиданным задачам.  

• Автор объясняет, что зачет будет проходить параллельно с выставлением оценок.  

• Он также упоминает, что оценка округляется в большую сторону в пользу студентов.