Найти набор вырезок на графике

Question

рассмотрим треугольный граф G с V = {a, b, c} и E = {ab, bc, ca}.Если подмножество ребер S = {ab, bc} удалено, то мы получаем ребро ac влево.Мой вопрос является ли S допустимым набором сечений (он разбивает G на два подмножества вершин {b} и {a, c})

Примечание: разрез - это разбиение вершинграф на двух непересекающихся подмножеств.Набор разрезов - это набор ребер, конечные точки которых находятся в разных подмножествах разбиения.

Answer 1

Да.

{ab, bc} - это набор срезов, поскольку он вызывает срез.Сокращение, вызванное {ab, bc} , составляет ({a, c}, {b}) .

Я уточню определения:

• Разрез - это разбиение вершин графа.Например, ({a, c}, {b}) является разрезом, поскольку каждая вершина графа принадлежит ровно одному из двух наборов.
• Вырезание набораcut (S, T) - это следующий набор ребер: {uv |U в S и V в T} .Например, набор сечений ({a, c}, {b}) равен {ab, bc} .
• Набор E ребермножество разрезов тогда и только тогда, когда существует разрез, для которого Е является его разрезом.В вашем примере набор {ab} не является набором вырезов, потому что вы не можете определить, принадлежит ли вершина c к S или T. Набор {ab, bc, ca} не является набором срезов, потому что вы легко можете доказать противоречие, что нет среза, для которого {ab, bc, ca} является его набором.