38) Эйлеровы и гамильтоновы графы, понятия эйлеровой цепи, цикла, гамильтонова цикла. Алгоритм поиска эйлеровой цепи.

Цикл в графе называется эйлеровым, если он содержит все ребра графа. Связный граф, в котором существует эйлеров цикл, называется эйлеровым графом. Эйлеровой цепью (или путем) является цепь (путь), которая включает все ребра (дуги) графа по одному разу. Собственная эйлерова цепь – это эйлерова цепь, которая не является эйлеровым циклом.

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

Теорема Эйлера-2. Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четны.

9. Граф имеет собственную эйлерову цепь (путь)  когда он связный и ровно две его вершины имеют нечетную степень.

Вершины нечетной степени являются началом и концом эйлеровой цепи.

Если снова вернуться к рассмотренному примеру, то увидим, что эйлерова цепь в нем также не существует, т. к. вершин нечетной степени в нем 4.

А теперь разберемся, как найти эйлеров цикл. Сначала вспомним еще одно определение.

Мостом (или перешейком) называется такое ребро графа G, удаление которого увеличивает число связных компонент. Если ребро r принадлежит некоторому циклу C, то оно не может быть мостом.

30. В данном графе ребра r₁ и r₂ являются мостами.

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

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

2) В очередной вершине выбираем путь по перешейку только в том случае, если нет пути по циклу.

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

Гамильтонова цепь (путь) – это простая цепь (путь), которая проходит через каждую вершину (узел) графа ровно по одному разу. Соответственно гамильтонов цикл – это простой цикл, который проходит через каждую вершину графа.

Граф, содержащий гамильтонов цикл, называется гамильтоновым графом

В отличие от эйлерова графа, не существует четкого критерия для определения, является ли граф гамильтоновым.

В качестве практического применения задачи поиска гамильтонова пути можно назвать т.н. задачу коммивояжера. В ней требуется осуществить обход всех населенных пунктов, посещая каждый по разу, и при этом постараться пройти минимальное расстояние.

39) Высказывания алгебры логики, операции над ними. Таблицы истинности основных операций.

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

В качестве примеров высказываний можно назвать «Сейчас идет снег» и «Первокурсники СибГУТИ изучают математику».

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

В дальнейшем нас будет интересовать не то, о чем идет речь в данном высказывании (его содержательная часть), а лишь какое значение истинности оно имеет. В алгебре логики все высказывания, имеющие одинаковые значения истинности, взаимозаменяемы, т.е. имеется два класса: класс истинных высказываний и класс ложных высказываний – (И, Л), (T, F), (1,0).

Высказывания a и b являются равносильными (a  b), если совпадают их значения истинности.

Высказыванию Р поставим в соответствие логическую переменную x, которая принимает значение 1, если Р истинно и 0, если оно ложно.

Переменная, которая может принимать только одно из двух значений – 1 или 0, истина или ложь, называется булевой переменной.

Логические операции, или связки: унарная операция – инверсия, бинарные – конъюнкция, дизъюнкция, импликация, равносильность (эквивалентность), штрих Шеффера, стрелка Пирса, кольцевая сумма.

Инверсия (логическое отрицание): NOT, НЕ, ¬, черта над переменной. Меняет значение переменной на противоположное.

Конъюнкция (логическое умножение): AND, И, , , . Имеет значение ложь, если значение хотя бы одного операнда ложно.

Дизъюнкция (логическое сложение): OR, ИЛИ, . Имеет значение истина, если значение хотя бы одного операнда истинно.

Импликация (логическое следование): ЕСЛИ…ТО…, . В выражении ЕСЛИ a ТО b переменная a является посылкой (основанием), переменная b – заключением (следствием, выводом). Имеет значение ложь тогда и только тогда, когда из истинной посылки делается ложное заключение.

Равносильность (эквивалентность): …ТОГДА И ТОЛЬКО ТОГДА, КОГДА…, , , . Имеет значение истина, когда переменные совпадают.

Штрих Шеффера (антиконъюнкция): по определению (a|b)  ¬(ab).

Стрелка Пирса (антидизъюнкция): (ab), по определению (ab)  ¬(ab).

Кольцевая сумма (сложение по модулю 2, исключающее ИЛИ): по определению (ab)¬(ab). Имеет значение истина, когда оба аргумента различны (для большего числа аргументов – когда количество единиц нечетно).

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

A	B	¬A	A & B	A  B	A  B	A  B	A | B	A  B	A  B
0	0	1	0	0	1	1	1	1	0
0	1	1	0	1	1	0	1	0	1
1	0	0	0	1	0	0	1	0	1
1	1	0	1	1	1	1	0	0	0

Введенные операции не являются независимыми, т.е. одни из них могут быть выражены через другие.

1. A  B  A  B.

2. A  B  (A  B)( B  A)  (A & B)  (A & B)  (A  B) & (A  B).

Доказательство: с помощью таблиц истинности.

41) Функции алгебры логики и формулы. Функции частичные и полностью определенные, переменные существенные и фиктивные.

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

Пусть {x_i | iI} – некоторое множество логических переменных. Формулой алгебры логики является любая логическая переменная (атомарной формулой) или выражение, построенное из формул с помощью логических операций.

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

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

Любая формула, кроме элементарной, должна быть заключена в наружные круглые скобки. Однако обилие скобок затрудняет чтение формул, поэтому в алгебре логики приняты некоторые соглашения относительно расстановки скобок: 1) внешние скобки не пишутся; 2) знак конъюнкции можно обозначать точкой или не писать; 3) на множестве {¬, , , , , |, ,  } вводится приоритет операций, который определяется посредством транзитивного отношения > «быть сильнее» и отношения эквивалентности «быть равносильным». Если все равносильные операции объединить в классы эквивалентности {}, то можно записать: {¬} > {, |, } > {} > {} > {, }.

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