17. Минимизация днф Карты Карно.

Карта Карно для n переменных содержит 2ⁿ ячеек, каждая из которых соответствует одной из возможных 2ⁿ комбинаций значений n логических переменных x₁,…,x_n. Карта строится в виде матрицы размера 2^n-k на 2^k так, что ее столбцы соответствуют значениям переменных x₁,…,x_k, строки – значениям переменных x_k+1,..,x_n, а соседние ячейки отличаются только значением одной переменной.

Булева функция может быть представлена на карте Карно выделением 1-ячеек. Подразумевается, что необозначенные ячейки соответствуют 0-точкам.

Для построения импликант берутся всевозможные наборы 1-ячеек, образующих вершины некоторого k-куба (т.е. 2^k точек таких, что пары соседних отличаются ровно одной координатой). Совпадающие координаты образуют набор (δ₁,…,δ_n-k) и требуемая импликанта имеет вид , где x_j – переменная, соответствующая значению δ_j.

При наглядном размещении простых импликант в карте Карно удается непосредственно находить МДНФ, выбирая простые импликанты, которые покрывают все единицы и имеют наименьшее возможное число вхождений переменных

19. Принцип двойственности. Самодвойственные функции.

Функция f⁺(x₁,…,x_n) называется двойственной по отношению к функции f(x₁,…,x_n), если . Двойственная функция получается из исходной при замене значений всех переменных, а также значений функции на противоположные.

Принцип двойственности: Если , то Таким образом, функция, двойственная суперпозиции функций, есть соответствующая суперпозиция двойственных функций.

Функция f(x₁,…,x_n) называется самодвойственной, если f⁺(x₁,…,x_n)=f(x₁,…,x_n).

26. Объекты теории графов. Цели и методы.

Во многих прикладных задачах изучаются системы связей между различными объектами. Объекты называются вершинами и отмечаются точками, а связи между вершинами называются дугами и отмечаются стрелками между соответствующими точками. Такие системы и образуют графы. Граф может изображать сеть улиц: вершины граф – перекрестки, а дуги – улицы с разрешенными направлением движения. Также в виде графов можно изображать: блок-схемы программ, электрические цепи, географические карты и молекулы хим. соединений.

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

Степенью вершины a неорграфа G называется число ребер, инцидентных вершине a (петли считаются дважды). Вершина степени 0 называется изолированной, степени 1 – концевой или висячей.

Лемма о рукопожатиях: Сумма степеней всех вершин графа является четным числом и равна удвоенному числу ребер.

Критерий «эйлировости» графа: Связный неориентированный мультиграф тогда и только тогда является эйлеровым, когда степень каждой из его вершин – четное число.

Алгоритм построения эйлерова цикла:

1. Выбрать произвольно некоторую вершину a.

2. Выбрать произвольно некоторое ребро u, инцидентное a, и присвоить ему номер 1 (назовем это ребро пройденным).

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

4. Находясь в вершине x, не выбирать ребро, соединяющее x с a, если есть возможность иного выбора.

5. Находясь в вершине x, не выбирать ребро, которое является перешейком (т.е. ребром, при вычеркивании которого граф распадается на две компоненты связности).

6. После того как в графе будут занумерованы все ребра, образуется эйлеров цикл.

Теорема: Если связный граф содержит k вершин нечетной степени, то минимальное число покрывающих его реберно непересекающихся цепей равно k/2.

1.Построим в графе цикл Гамильтона –цикл в котором все вершины графа участвуют только 1 раз.

2. Изобразим граф таким образом чтобы цикл Гамильтона

имел форму выпуклого многоугольника, а ребра находились

Внутри этого цикла.

3.Построим вспомогательный граф вершины которого являются ребрами не вошедшие в цикл Гамильтона, а ребра пересекающиеся пары этих ребер.

4. На вершинах вспомогательного графа строим максимально

возможный связанный фрагмент без циклов

5. Наносим пометки, чтобы смежные вершины

были помечены по разному.

6. Наносим оставшиеся ребра (- - - - ).

Если хотя бы одно из ребер соединяет вершины с

одинаковыми пометками, то граф не является планарным.

Для того что бы граф был планарным необходимо и

достаточно, чтобы он не содержал в себе подграфов,

гомеоморфных К3 и К5.