Почему граф с n вершинами имеет 2 ^ n -2 разрезов?

Ответ 1

Простым способом его рационализации, а также перечислением разрезов является назначение двоичной цифры для каждого node. A 0 указывает, что он в множестве A и a 1, что он в множестве B. Затем просто увеличивайте, игнорируя случай 0 и 2 ^ n - 1, оставляя 2 ^ n - 2 разреза. Итак, для 4-го вершинного графа с вершинами P, Q, R, S:

PQRS
0000 A : { P,Q,R,S } B : {} // ignore, B is empty
0001 A : { P,Q,R } B : { S }
0010 A : { P,Q,S } B : { R }
0011 A : { P,Q } B : { R,S }
0100 A : { P,R,S } B : { Q }
0101 A : { P,R } B : { Q,S }
0110 A : { P,S } B : { Q,R }
0111 A : { P } B : { Q,R,S }
1000 A : { Q,R,S } B : { P }
1001 A : { Q,R }, B : { P,S } 
1010 A : { Q,S } B : { P,R }
1011 A : { Q } B : { P,R,S }
1100 A : { R,S } B : { P,Q }
1101 A : { R } B : { P,Q,S }
1110 A : { S } B : { P,Q,R }
1111 A : {} B : { P,Q,R,S } // ignore, A empty

Это оставляет вам 14, 2 ^ 4 - 2.

Ответ 2

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

Следовательно, чтобы определить конкретный разрез, вы просто берете некоторое подмножество V и которое определяет A, а также B, его дополнение.

Число подмножеств V, где | V | = n - мощность множества степеней V, 2 ^ n. Однако вы должны вычесть два случая, потому что A не может быть пустым и не может быть равным V, потому что тогда B будет пустым. Следовательно, 2 ^ п - 2.

Ответ 3

Это довольно очевидно, я думаю:

• Каждая вершина может быть либо в множестве A, либо в наборе B
• У нас есть n вершин
• Две возможности для n вершин делают для 2 ^ n перестановок
• Удаление точек, в которых все вершины находятся либо в A, либо в B
• Это дает нам 2 ^ n - 2

Или подумайте об этом как таблицу истинности. a означает, что вершина находится в множестве A, b означает, что она находится в множестве B.

Vertices
1 2 3 4
a a a a
a a a b
a a b a
a a b b
a b a a
a b a b
a b b a
a b b b
b a a a
b a a b
b a b a
b a b b
b b a a
b b a b
b b b a
b b b b

Если мы удалим множества a a a a и b b b b, мы останемся с необходимыми 14...

Ответ 4

Вырез означает, что вершина будет либо в одном наборе A, либо в множестве B.

Поскольку оба набора должны быть непустыми, единственная возможность - это единственная возможность.

1, (n-1) == > Это означает, что 1 вершина в множестве A и (n-1) в множестве B. Нет способов выбора 1 из n = nC1

2, (n-2) == > 2 вершины в наборе A и (n-2) в множестве B. Нет способов выбора 2 из n = nC2

3, (n-3) == > 3 вершины в наборе A и (n-3) в множестве B. Нет способов выбора 3 из n = nC3

(n-1), 1 == > (n-1) вершин в Set A и 1 в множестве B. Нет способов выбора n-1 из n = nCn-1

Следовательно, общее количество разрезов:

nC1 + nC2 + nC3 + ..... nCn-1 = 2^(n)-2

Ответ 5

Сначала я столкнулся с подобной проблемой, сославшись на то, сколько сокращений существует для 4 вершин (квадрат).

Помните, что вы можете вырезать по диагонали квадрата. Это даст вам недостающие 2.