ТС
Татьяна Семёнова
Сколько максимально минимальных разрезов может быть в графе???
Сколько максимально минимальных разрезов может быть в графе?? ? Во многих источниках пишут N^2. Как выводится именно такая оценка???
Есть множестов из V вершин графа. Минимальный разрез-это такое разделение V вершин на два множества S и T,что количество ребер st,таких что s из S, а t из T минимальное. То есть если провести линию разделяющую граф на две части, то эта линия должна пересекать как можно меньше ребер.