Архив форумов ЦИТФорума

[sabotage]

Проблема: Дан граф. Нужно найти зависимость количества разрезов в графе от количества вершин в нем, то есть доказать, что количество этих самых разрезов будет равно 2^(n-2).

Хелп плиз...

[GREA]

А граф полный? Если да и n-число вершин, то:

Чтобы было разрезание нужно к каждой вершине приписать номер подграфа (допустим 0 или 1).
Естественно 2^n - это число всех возможный комбинаций.
Но вспомнив, что подграф должен содержать хотя бы одну вершину - убираем варианты, когда в 0-м подграфе нет вершин и в 1-м подграфе их нет тоже. Получаем 2^n-2 варианта.
Кроме того, мы чуть не забыли про симметричные случаи, потому это число нужно еще поделить на два.
Получится 2^(n-1)-1 разрезов.