Решение логических задач при помощи графов с цветными вершинами

15

В «Кванте» № 8 за 1973 год была помещена статья Л. Ю. Березиной «О графах с цветными ребрами», посвященная решению логических задач. Не менее интересен метод решения логических задач с помощью графов с цветными вершинами, позволяющий найти решать задачи, которые часто называют «логических задачи на Джонсона и Смита» *). Этот метод состоит в изображении структуры задачи с помощью некоторого графа. Вершины такого графа будут обозначать базисные высказывания задачи; а ребра графа—импликации или коньонки между базисными высказывами. Цвет вершины обозначет истинность или ложность изображаемого его высказывания. В определении цвета вершин графа и заключается описываемый метод. Всюду в дальнейшем процесс определения цвета вершин мы будем называть раскрашивание графа. Цвет вершины не всегда будет определяться однозначно; возможно варнаты будем называть варнатами раскрашивание.

Для изображения структуры задачи с помощью графа условится о символьке, позволяющей переодить с языка логики на язык графов:

Таблица 1

Логическое понятие Элемент графа

Высказывание Вершина графа
Истининое высказывание Вершина красного цвета
Ложное высказывание Вершина черного цвета
Импликация $X \Rightarrow Y$ Орентированное ребро $\overrightarrow{XY}$ графа

Раскрашивание графов производится по правилам алгебры логики, которые переодятся на язык графов с помощью следующей символьки:

Таблица 2

Правило алгебры логики Правиле раскрашивания графа

1. Каждее высказывание имеет одно и только одно из двух значений истинности: «ложно», «истинно».

2. Если импликация $X \Rightarrow Y$ истинна и посылака $X$ истинна, то и заключение $Y$ истинно.

3. Если импликация $X \Rightarrow Y$ истинна, а заключение $Y$ ложно, то и посылака $X$ ложна.

4. Каждая вершина графа является либо черной, либо красной.

5. Если ребро $\overrightarrow{XY}$ ориентированно от вершины $X$ к вершине $Y$ и вершина $X$—красная, то и вершина $Y$—красная.

6. Если ребро $\overrightarrow{XY}$ ориентированно от вершины $X$ к вершине $Y$ и $Y$—черная, то и $X$—черная.

*) Можно, конечно, говорить и о «задачах про Воробьева и Грачева» — пародия на них всем памятна по «Золотому теленку».

16

Кроме этих правил 1—3 для каждой конкретной задачи можно ввести дополнительные правила (в зависимости от структуры используемого графа).

Продемонстрируем метод на примерах решения конкретных задач.

Задача 1

Для поляной экспедиции из всмы претензийтов $A, B, C, D, E, F, G$ и $H^*$ надо отобразить шесть специализмов: биология, гидроLOGа, сиоптика, врача, механика и радистика. Обязанности биология могут выполнять $E$ и $G$, гидроLOGа — $B$ и $F$, сиоптика — $F$ и $G$, врача — $A$ и $D$, радистика — $C$ и $D$, механика — $C$ и $H$. Хотя некоторые из претензийсов совместимые две специализми, в экспедиции каждой помощи выполнять только одну обязательность.

Коэто и кем следует взять в экспедицию, если $F$ не хочеем.Exать без $B$, $D$ — без $H$ и без $C$, $C$ не хочеем.Exать вместе с $G$, а $A$ не хочеем.Exать вместе с $B$?

Базисное множество высказываний задачи состоит из всмы высказываний вида «$A, B, C, \dots$» зачислен в состав экспедиции» (будем обозначать их соответственно буквами $A, B, C, \dots$).

Для облегчения воспрятия условия задачи изобразим специализцию претензентов с помощью так называемого двудольного графа, то есть графа, вершины которого распадаются на два класса (две «долли») так, что вершины из одного и того же класса не связаны между собой (не соединены ребрами). Двудольные графы удобно чертить, располагая вершины одной «долли» в строку, а вершины другой — в строку, параллельную первой (рис.1).

На рисунке 1 мы изобразили претензентов вершинами $A, B, \dots, H^*$ первой доли, а специализности — вершинами $6, 8, \dots, c$ («б») — биолог, «в» врач и т. д.) второй доли. Вершину первой доли связем с вершинами второй доли, если соответствующий претензент владеет соответствующей специализностью. По такому графу легко определить, какие два претензента владеют соответствующую.

Из двух претензентов $X$ и $Y$, владеющих одной специализностью, над взяты хотя бы одного, то есть верна дизьонкция вида $X \lor Y$, равносильная импликации $\bar{X} \Rightarrow Y^{**}$). На основании этого можно записать

$(\bar{E} \Rightarrow G) \wedge (\bar{B} \Rightarrow F) \wedge (\bar{F} \Rightarrow G) \wedge (\bar{A} \Rightarrow D) \wedge (\bar{C} \Rightarrow D) \wedge (\bar{C} \Rightarrow H)$.

Кроме того, если $X$ не хочеет.Exать без $Y$, то верна импликация $\bar{Y} \Rightarrow \bar{X}$, а если $X$ не хочеет.Exать вместе с $Y$, — импликация $Y \Rightarrow \bar{X}$. На основании этого имеем

$(\bar{B} \Rightarrow \bar{F}) \wedge (\bar{H} \Rightarrow \bar{D}) \wedge (\bar{C} \Rightarrow \bar{D}) \wedge$
$(\bar{G} \Rightarrow \bar{C}) \wedge (\bar{B} \Rightarrow \bar{A})$.

Итак, условия задачи можно представить в виде коньонкции импликации:

*) Разумеется, это как раз их фамилии: Джонсон, Смит, Браун, … (Воробьев, Грачев, Дроздов и т. д.).
**) Или $\bar{Y} \Rightarrow X$ — безразлично.

17

Рис. 2.

Представим структуру задачи в виде графа. При этом вершины, изображенные не отрицательные высказывания вида $X$, расположим на одной прямой, а вершины вида $\bar{X}$ — на параллельной ей прямой так, чтобы $A$ и $\bar{A}$, $B$ и $\bar{B}$ и т. д. были расположены в вертикальных столбцах. Содержание в условии 11 импликции (1) изображаем ориентированными ребрами графа (согласно данным таблицы 1,— см. рис. 2).

Раскрашивание графа мы всегда будем начинать с допущения о цвете одной из вершин $X$ графа. Эту вершину $X$ мы будем выбирать так, чтобы сумма ее связности $r(X)$ со связностью $r(\bar{X})$ вершины $\bar{X}$ была наиболее такой как в этом случае цвет вершины $X$ дает максимум информации о цвете других вершин. В некоторых случаях одно допущение позволяет полностью и однозначно раскрашить граф или приводит к противоречию, в других необходимо делать новые допущения. После нее следует тогда, когда исчерпывается информация, предоставляемая вершным допущением (прерывается цепочка расчужdenей).

Полное раскрашивание графа дает решение задачи, противоречие указывает на неверность допущения. О цвете вершины $X$ можно сделать два допущения: «$X$ — красная», «$X$ — черная». Необходимо использовать оба допущения; лишь тогда удостраняется исчерпать все варианты раскрашивания.

Введем теперь дополнительные правила раскрашивания 4–6:

Правило 4
Если высказывание истинно, то отрицание ложно, и наоборот.

Правило 5
Если шестерых претензентов включали в состав экспедиции, то остальные исключили.

Правило 6
Если двух претензентов истинно из состав экспедиции, то остальные включали.

Теперь, руководствуясь правилми 1—6, мы можем раскрашить граф, изображенный на рисунке 2:

1. Предположим, что вершина $C$ — красная. Тогда:

1. $\bar{C}$ — черная (4) *); 2) $G$ — черная (3); 3) $\bar{E}$, $\bar{F}$ — черные (3); 4) $\bar{B}$ — черная (3); 5) $E$, $F$ и $B$ — красные (4); 6) $\bar{G}$ — красная (4); 7) $\bar{A}$ — крас-

*) Здесь и в дальнейшем цифры в скобках обозначают номер правила, на основании которого делается вывод о цвете вершины.

18

Рис. 3.
ная (2); 8) $A$ — черная (4); 9) $D$ — красная (2); 10) $\bar{D}$ — черная (4);
11) $\bar{H}$ — черная (3); 12) $H$ — красная (4).

Полученный результат согласуется с правилами 5 и 6. Следовательно, если $C$ включает в состав экпедициции, то надо еще включить $B, D, E, F$ и $H$ и исключить $A$ и $G$.

II. Предположим, что вершина $C$ — черная (рис. 3):

1. $\bar{C}$ — красная (4); 2) $\bar{D}$ — красная (2); 3) $D$ — черная (4); 4) $D$ — красная (2).

Поскольку $D$ не может быть одновременного красной и черной (1), предположение «$C$ — черная» приводит к противоречию; значит, $C$ — красная, и задача имеет единственное решение:

$B, C, D, E, F, H (\bar{A}, \bar{G})$.

Остается определить, какую должность будет занимать в экпедициции каждой из шестерых, включенных в ее состав. Для этого нам придется воспользоваться графом с цветными ребрами.

Перечертим граф, изображенный на рисунке 1, исключив вершины $A$ и $G$ и связанные с ними ребра (рис. 4). Ребра графа чащеим сним цветом, чтобы удобно было потом «наводить» (закрашивать) их другими цветами. Условимся, что ребро, связывающее вершину $X$ первой доли с вершиной $a$ второй доли, будет красным, если $X$ занимает должность $a$, и черным, если $X$ не занимает этой должности (например, «$Fc$ — красное», если $F$ занимает должность синоптика, а «$Dp$ — черное» означает, что $D$ не занимает должность радиста).

При определении цвета ребер мы будем руководствовать следующими правилами:

Правило 7
Если только один из значений в состав экпедициции может занять должность $a$, то ему и придется ее занять.

Правило 8
Если неокоторому $X$, значение в состав экпедициции, приходит занять ввиду условия 7 должность $a$, то он не может занять никакую другую.

Руководствуясь правилами 7—8, раскрасием граф на рисунке 4:

1. $E\delta$ — красное (7); 2) $Fc$ — красное (7); 3) $F\epsilon$ — черное (8); 4) $B\epsilon$ —

20

Основно научим пять вершин, изображющие коньонки: $(D \wedge E), (F \wedge \bar{A}), (\bar{F} \wedge E), (\bar{D} \wedge \bar{H})$ и $(E \wedge \bar{A})$.

Вершины, изображющие коньонки вида $X \wedge Y$, будем назвать результатирующими вершинами, а вершины $X$ и $Y$ их составляющими (скажем, вершина $F \wedge \bar{A}$ является результатирующей составляющих $F$ и $\bar{A}$).

Какую результатирующую связь с двумя ее составляющими неориентированными ребрами красного цвета. Импликации, содержащие в условиях задачи, изображим как в задаче 1 (рис. 5).

Правила раскрашивания 1—4 будем использовать и при раскрашивании графа на рисунке 5. Кроме того, мы ведем дополнительные правила 9—13:

Правило 9
Если $X$ — истинно и $Y$ — истинно, то и $X \wedge Y$ — истинно.

Правило 10
Если $X \wedge Y$ — истинно, то $X$ и $Y$ — истинны.

Правило 11
Если $X$ или $Y$ ложно, то и $X \wedge Y$ ложно.

Правило 12
Если $X \wedge Y$ ложно, а $X$ истинно, то $Y$ ложно.

Правило 13
Если некоторое допущение исключает возможность пригласить несколько гостей, а всех остальных можно пригласить, не получая противерений, то так и следует поступить (для максимализации приглашенных).

Пользование правил 1—4 и 9—13, раскрашим граф на рисунке 5:
I. Допустим, что $G$ — красная:

21

1. $\bar{G}$ — черная (4); 2) $B$ — черная (3); 3) $C$ — черная (3); 4) $E \wedge \bar{A}$ — черная (3); 5) $\bar{D} \wedge \bar{H}$ — черная (3); 6) $\bar{B}$ и $\bar{C}$ — красные (4).
   Допустим теперь (руководствуясь правилам 13), что $D$ красная:
2. $E$ — красная (2); 8) $D \wedge E$ — красная (9); 9) $\bar{A}$ — красная (2); 10) $E \wedge \bar{A}$ — красная (9).

Но по правилам 1 $E \wedge \bar{A}$ не может быть одновременно черной (шаг 4) и красной (шаг 10), значит, если $G$ — красная, то $D$ — черная.

Построим новый граф (рис. 6) и воспользуемся на нем результатами первых шести шагов. Раскрасием граф на рисунке 6, считая, что $D$ — черная:
11) $\bar{D}$ — красная (4); 12) $D \wedge E$ — черная (11); 13) $\bar{H}$ — черная (12);
14) $H$ — красная (4); 15) $F \wedge \bar{A}$ — черная (3); 16) $\bar{F} \wedge E$ — черная (3).
Допустим, что $E$ — красная (13):
17) $\bar{E}$ — черная (4); 18) $\bar{F}$ — черная (12); 19) $F$ — красная (4); 20) $\bar{A}$ — красная (12); 21) $A$ — красная (4).

Следуя правилам 13, мы сделали красными все три оставшиеся вершины: $E, F$ и $A$. Тогда из графа рисунка 6 следует, что если пригласить $G$, то, кроме того, можно пригласить $A, E, F$ и $H$ (всего 5 гостей).

В рассмотренном варианте (при допущении «$G$ — красная») черными оказались три вершины $B, C$ и $D$. Проверим, можно ли в случае «$G$ — черная» получить не менее пяты красных вершин, то есть не более трех черных.

II. Допустим, что $G$ — черная (рис. 7). Тогда:

1. $\bar{G}$ — красная (4); 2) $F$ — черная (3); 3) $\bar{F}$ — красная (4);
2. $F \wedge \bar{A}$ — черная (11).
   Пусть теперь $D$ — красная (13):
3. $E$ — красная (12); 6) $\bar{E}$ — черная (4); 7) $B$ — черная (3);
4. $D \wedge E$ — красная (9); 9) $\bar{A}$ — красная (2); 10) $A$ — красная (4).

Таким образом, уже четые вершины оказались черными ($A, B, F, G$).

Перечертим граф рисунка 7 (рис. 8) — воспользуемся результатами первых четырех шагов и допустим, что $D$ — черная. Тогда уже три вершины — черные ($D, F$ и $G$), и значит, чтобы получилось не менее пяты красных вершин, необходимо сделать красными все остальные вершины вида $X$.

Но это невозможно, так как если $A$ — красная, то

22

11. $\bar{A}$ — черная (4); 12) $B$ — черная (3).

Таким образом, допущение «$G$ — черная» не дает более четырех красных вершин вида $X$. Найбольшее число таких вершин (пять) дает допущение «$G$ — красная».

Ответ следует из графа рисунка 6:
$N$ мог пригласить максимум пять гостей: $A, E, F, G$ и $H$.

Затем и е. При рассмотрении всех четырех вариантов раскрашивания (рис. 5—8) можно было ограничиться лишь одним графом. Для этого его вершины нужно было выполнить в виде кружочков достаточно большого диаметра, разделенных на четыре квадрата, и при рассмотрении каждого варианта закрашивать по одному квадрату.

В заключение отметим, что задачи 1 (о наличии треугольника с однозначными сторонами в графе с шестю вершинами и ребрами двух цветов) и 5 (о наличии такого треугольника в графе с семнадцатью вершинами и ребрами трех цветов) из статьи Л. Ю. Березиной «О графах с цветными ребрами» допускают следующое обобщение (предложенное на XIII Украинской Республикиской олимпиде юных математиков):

Задача 3

Послеовательность $\{a_n\}$ задана с помощью рекуррентной формулы: $a_1 = 2; a_n = n a_{n-1} + 1$. Доказать, что в графе $c a_n + 1$ вершиной, ребра коморого окружены в $n$ цветов, найдется треугольник с однозначными сторонами.

Воспользовемся методом математической индукции.

1. При $n = 1$ $a_1 = 2$. Число вершин $a_1 + 1 = 3$.

Граф является треугольником с ребрами одного цвета (то есть искомым треугольником).

2. Пусть при $n = k$ утверждение верно, то есть в графе с числом цветов $k$ и числом вершин $a_k + 1$ существует треугольник с однозначными сторонами. Пусть теперь $n = k + 1$. Тогда число вершин равно

$$a_{k+1} + 1 = [(k + 1) \cdot a_k + 1] + 1.$$

Выберем одну из вершин; назовем ее $A$. Она соединяется ребрами $k + 1$ цвета с вершинами, число которых $(k + 1) \cdot a_k + 1$. Среди этих ребер по крайней мере $a_k + 1$ — одного цвета (по «приицлу Дирихле»*)) для определенности — синERO. Если одна из $a_k + 1$ вершин $B$ связана с другой $C$ с ним ребром, то треугольник $\Delta ABC$ — искомый. Если же нет, синей цветов не использован в графе, состоящем из $a_k + 1$ вершины, и тогда там использованы только $k$ цветов. В этом графе (являющегося часть исходного) по предложению имеется искомый треугольник, а значит, он имеет и в исходном.

Утверждение доказано.

В частности, при $n = 2$ (два цвета) $a_2 = 2 \cdot 2 + 1 = 5, a_2 + 1 = 6$ (шесть вершин); при $n = 3$ ( три цвета) $a_3 = 3 \cdot 5 + 1 = 16, a_3 + 1 = 17$ (семнадцать вершин).

(Во всех этих задачах имеются в виду полные графы, у которых любая пара вершин соединена ребром.)