Алгоритм Каргера

Алгори́тм Ка́ргера (англ. Karger's algorithm) — в информатике и теории графов является вероятностным алгоритмом, позволяющим найти минимальный разрез связного графа. Алгоритм изобретен Девидом Каргером и опубликован в 1993 году. Идея алгоритма основана на стягивании ребра в неориентированном графе. Во время стягивания ребра происходит объединение двух вершин в одну, что уменьшает количество вершин графа на единицу. Все рёбра стягиваемых вершин соединяются со вновь образованной вершиной, порождая мультиграф. Алгоритм Каргера итеративно выбирает случайные рёбра и выполняет операцию до тех пор, пока не останется две вершины, которые и представляют собой разрез изначального графа. Если повторять алгоритм достаточное количество раз, то с высокой вероятностью может быть найден минимальный разрез.