Задачи и упражнения

1. Доказать, что в неорграфе число вершин с нечетной степенью четно.

2. Построить граф (если он существует) с последовательностью степеней

а) (4,3,3,2,2);

б) (5,4,2,2,1) .

3. Найти матрицы достижимости и контрдостижимости для графов G₁ ,G₂, G₄, изображенных на рис. 4.57.

Рис. 4.57

4. Доказать, что если в n-вершинном графе степень каждой вершины не меньше, чем (n-1)/2 , то он связен.

5. Доказать, что если G  несвязный граф, то G  связный.

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

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

Рис. 4.58

8. Доказать, что хроматическое число каждого n-вершинного дерева (n2) равно 2.

9. Построить остовы для графов, изображенных на рис. 4.59.

Рис. 4.59

10. Существует ли эйлеров цикл в графах, изображенных на рис. 4.60 ?

Рис. 4.60

11. Определить, какие из графов пяти правильных многогранников имеют эйлеровы циклы.

12. Составить алгоритм, основанный на алгоритме Флери и позволяющий найти все эйлеровы циклы графа.

13. Определить гамильтоновы пути и контуры методом перебора Робертса и Флореса в графах, изображенных на рис. 4.61.

Рис. 4.61

14. Для графа построить, если это возможно, его уклад­ку на плоскости.

а ) б)

д ) е)

5. Алгебра логики

Под высказыванием понимают повествовательное предложение, относительно которого имеет смысл утверждать, истинно оно (обозначается символами 1 или И) или ложно (символы 0 или Л). Значения И и Л (или 1 и 0) называются истинностными значениями высказывания, множество {И, Л} (или {0,1}) называется множеством истинностных значений. Заметим, что значение высказывания ситуативно, при этом в каждой ситуации высказывание принимает одно и только одно из двух значений – И или Л.

Например, повествовательное предложение «3 есть простое число» является истинным, а «3.14… – рациональное число» – ложным, «Колумб открыл Америку» – истинным, а «Киев – столица Узбекистана» – ложным, «Число 6 делится на 3» – истинным, а «Сумма чисел 2 и 3 равна 6» – ложным и т. п.

Такие высказывания называют простыми или элементарными. При формальном исследовании сложных текстов вместо понятия «простые высказывания» используют понятие «пропозициональные переменные» (от лат. propositio – предложение), которые обозначают прописными буквами латин­ского алфавита A, B, C,… Истинность или ложность высказывания будем отмечать символами 1 – истина или 0 – ложь.

Пример:

1. если A₁=«5 – простое число», то A₁ = 1;

2. если A₂=«2 – вещественное число», то A₂ = 1;

3. если B₁=«3, 14…– рациональное число», то B₁ = 0;

4. если D=«Сумма чисел 2 и 3 равна 6», то D = 0.

Замечание. Символ «=» означает, что пропозициональной переменной, стоящей слева, присвоить значение высказывания, стоящего справа от символа.

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

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