Решение задачи: Какие графы сбалансированы?

Задача 5. Какие графы на рисунке сбалансированы? Указать для них разбиение на два множества. Для решения этой задачи нам нужно понять, что такое сбалансированный граф. Определение: Взвешенный граф называется сбалансированным, если для любого цикла произведение весов его рёбер равно \(+1\). В данном случае веса рёбер представлены знаками \(+\) и \(-\). Произведение \(+\) на \(+\) равно \(+\), \(-\) на \(-\) равно \(+\), а \(+\) на \(-\) равно \(-\). Другое определение сбалансированного графа: Граф является сбалансированным тогда и только тогда, когда его вершины можно разбить на два непересекающихся множества \(V_1\) и \(V_2\) таким образом, что все рёбра внутри \(V_1\) и внутри \(V_2\) имеют вес \(+\), а все рёбра между \(V_1\) и \(V_2\) имеют вес \(-\). Давайте рассмотрим каждый граф по очереди. Граф а) Вершины: \(a, b, c, d, e\). Рёбра и их веса: \(ab: +\) \(ac: +\) \(ad: -\) \(bc: +\) \(bd: +\) \(cd: -\) \(ce: +\) \(de: -\) Проверим циклы: 1. Цикл \(a-b-d-c-a\): \(ab \cdot bd \cdot dc \cdot ca = (+) \cdot (+) \cdot (-) \cdot (+) = (-)\). Так как произведение весов рёбер в этом цикле равно \(-\), граф а) не является сбалансированным. Граф б) Вершины: \(a, b, c, d\). Рёбра и их веса: \(ab: +\) \(ac: +\) \(ad: -\) \(bc: -\) \(bd: +\) \(cd: -\) Проверим циклы: 1. Цикл \(a-b-c-a\): \(ab \cdot bc \cdot ca = (+) \cdot (-) \cdot (+) = (-)\). Так как произведение весов рёбер в этом цикле равно \(-\), граф б) не является сбалансированным. Граф в) Вершины: \(a, b, c, d, e, f, g, h, i, j\). Рёбра и их веса: \(ac: -\) \(ab: +\) \(bc: -\) \(cd: +\) \(ci: -\) \(di: +\) \(df: +\) \(ej: -\) \(ef: +\) \(eh: +\) \(fg: -\) \(gh: -\) \(ij: +\) \(be: +\) Проверим циклы. Попробуем разбить вершины на два множества \(V_1\) и \(V_2\). Начнем с вершины \(a\). Пусть \(a \in V_1\). Тогда: - \(ab: +\) \(\Rightarrow\) \(b \in V_1\) - \(ac: -\) \(\Rightarrow\) \(c \in V_2\) - \(bc: -\) (проверяем: \(b \in V_1, c \in V_2\), ребро \(bc\) имеет вес \(-\). Это согласуется с правилом разбиения). Продолжаем: - \(c \in V_2\): - \(cd: +\) \(\Rightarrow\) \(d \in V_2\) - \(ci: -\) \(\Rightarrow\) \(i \in V_1\) - \(b \in V_1\): - \(be: +\) \(\Rightarrow\) \(e \in V_1\) Продолжаем: - \(d \in V_2\): - \(df: +\) \(\Rightarrow\) \(f \in V_2\) - \(i \in V_1\): - \(di: +\) (проверяем: \(d \in V_2, i \in V_1\), ребро \(di\) имеет вес \(+\). Это не согласуется с правилом разбиения, так как ребро между \(V_1\) и \(V_2\) должно быть \(-\)). Значит, граф в) не является сбалансированным. Давайте перепроверим граф в) через циклы. Рассмотрим цикл \(a-c-i-d-c-a\). \(ac \cdot ci \cdot id \cdot dc = (-) \cdot (-) \cdot (+) \cdot (+) = (+)\). Этот цикл сбалансирован. Рассмотрим цикл \(a-b-e-j-i-c-a\). \(ab \cdot be \cdot ej \cdot ji \cdot ic \cdot ca = (+) \cdot (+) \cdot (-) \cdot (+) \cdot (+) \cdot (-) = (+)\). Этот цикл сбалансирован. Рассмотрим цикл \(c-d-f-g-h-e-b-c\). \(cd \cdot df \cdot fg \cdot gh \cdot he \cdot eb \cdot bc = (+) \cdot (+) \cdot (-) \cdot (-) \cdot (+) \cdot (+) \cdot (-) = (-)\). Так как произведение весов рёбер в этом цикле равно \(-\), граф в) не является сбалансированным. Граф г) Вершины: \(a, b, c, d, e, f, g\). Рёбра и их веса: \(ab: -\) \(ac: -\) \(ag: +\) \(bc: +\) \(cd: -\) \(ce: +\) \(cf: +\) \(de: -\) \(ef: +\) \(fg: +\) \(ge: +\) Попробуем разбить вершины на два множества \(V_1\) и \(V_2\). Начнем с вершины \(a\). Пусть \(a \in V_1\). Тогда: - \(ab: -\) \(\Rightarrow\) \(b \in V_2\) - \(ac: -\) \(\Rightarrow\) \(c \in V_2\) - \(ag: +\) \(\Rightarrow\) \(g \in V_1\) Продолжаем: - \(b \in V_2\): - \(bc: +\) (проверяем: \(b \in V_2, c \in V_2\), ребро \(bc\) имеет вес \(+\). Это согласуется с правилом разбиения). Продолжаем: - \(c \in V_2\): - \(cd: -\) \(\Rightarrow\) \(d \in V_1\) - \(ce: +\) \(\Rightarrow\) \(e \in V_2\) - \(cf: +\) \(\Rightarrow\) \(f \in V_2\) Продолжаем: - \(d \in V_1\): - \(de: -\) (проверяем: \(d \in V_1, e \in V_2\), ребро \(de\) имеет вес \(-\). Это согласуется с правилом разбиения). - \(e \in V_2\): - \(ef: +\) (проверяем: \(e \in V_2, f \in V_2\), ребро \(ef\) имеет вес \(+\). Это согласуется с правилом разбиения). - \(f \in V_2\): - \(fg: +\) (проверяем: \(f \in V_2, g \in V_1\), ребро \(fg\) имеет вес \(+\). Это не согласуется с правилом разбиения, так как ребро между \(V_1\) и \(V_2\) должно быть \(-\)). Значит, граф г) не является сбалансированным. Давайте перепроверим граф г) через циклы. Рассмотрим цикл \(a-g-f-c-a\). \(ag \cdot gf \cdot fc \cdot ca = (+) \cdot (+) \cdot (+) \cdot (-) = (-)\). Так как произведение весов рёбер в этом цикле равно \(-\), граф г) не является сбалансированным. Вывод: Ни один из представленных графов не является сбалансированным. Если бы граф был сбалансированным, то для него можно было бы указать разбиение на два множества. Поскольку ни один из графов не является сбалансированным, разбиение для них указать невозможно. Окончательный ответ: Ни один из графов на рисунке не является сбалансированным.