Автор: alex19921992 (13.01.2008 в 09:22)
возможно, разделить на 2 равные части....
а вообще, это боян, есть задача про компьютерную сеть где надо завалить какойто канал так
чтобы сеть разбилась на части.
Неэффективный алгоритм:
перебираем все ребра графов
для каждого ребра:
выбираем случайную вершину и отмечаем ее.
из вершины смотрим все соседние, отмечаем их, для соседних то же самое, и т. д....
в итоге, если останутся неотмеченные вершины,то даное ребро - искомое.