«ДИСКРЕТНАЯ МАТЕМАТИКА УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ ДЛЯ СЛУШАТЕЛЕЙ ФАКУЛЬТЕТА ЗАОЧНОГО ОБУЧЕНИЯ Специальность 210406.65 Сети связи и системы коммутации 2010 ББК 22.161 М51 УДК 519.3 Рецензенты: начальник кафедры физики ...»

Пример 2. Показать, что множество всех действительных чисел континуально.

С этой целью найдем взаимнооднозначное соответствие между множеством I чисел, лежащих на отрезке (0,1) и множеством действительных чисел g : I R. Легко проверить, что таким соответствием является, например, y = g( x ) = tg( x Можно доказать, что континуальными являются • множество всех точек пространства R n, • множество всех подмножеств счетного множества.

Значения мощности множеств называют кардинальными числами. В частности кардинальными числами являются натуральные числа – это мощности конечных множеств.

Доказано, что мощность множества A и мощность множества всех его подмножеств 2 A связаны следующим соотношением: A < 2 A. Поэтому не существует множества максимальной мощности, т.е. не существует максимального кардинального числа.

1.4. ДЕКАРТОВЫ ПРОИЗВЕДЕНИЯ И ПРОЕКЦИИ

МНОЖЕСТВ

M 1 M 2... M n ). Если M 1 = M 2 =... = M n = M, то для декартова произведения используется обозначение M n.

Декартово произведение множеств само является множеством и поэтому к нему применимы все изученные ранее способы задания и операции.

Пример. Пусть M = {0,1}, N = {a, b, c}. Тогда M N = {( a, 0), (b, 0), (c, 0), (a,1), (b,1), (c,1)}.

Проекцией вектора на i -ю ось называется его i -я координата (обозначается прi ). Проекцией вектора на оси i1,i2,...,ik называется вектор длины k ( ai1,ai2,...,aik ) (обозначается прi i...i ).

множество всех { прi, M } (обозначается прi M ). Проекцией множества M A1 A2... An на оси i1, i2,..., ik называется множество всех {прi i...i, M } (обозначается прi i...i M ).

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

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

Рассмотрим пример нахождения множества следователей моложе лет со стажем работы в ОВД более 3 лет с указанием специальных званий и фамилий.

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

Фамилия, Год Занимаемая Год поступле- Специальное имя, отчество рождения должность ния на службу звание На языке теории множеств эту таблицу можно описать как М М 1 М 2 М 3 М 4 М 5 - множество, представляющее собой файл базы данных, где значения полей данных содержатся в следующих множествах:

М1 - фамилия, имя, отчество сотрудников отдела, М 3 - занимаемая должность, М 4 - год поступления на службу в ОВД, М 5 - специальное звание.

Будем обозначать через х – элементы множества М, представляющие собой записи базы данных.

Тогда множество всех сотрудников моложе 30 лет (для 2010 года) на языке теории множеств есть множество А1, состоящее из хi, для которых проекция хi на множество М2 меньше тридцати:

Аналогично множество следователей:

А2 = {х : пр3 х = следователь}.

Множество сотрудников со стажем более 3 лет:

Обозначим B = А1 A2 A3 - множество всех записей о следователях моложе 30 лет и со стажем более 3 лет. Проекция этого множества определяет их специальные звания и фамилии и, следовательно, является искомым множеством.

1.5. БИНАРНЫЕ ОТНОШЕНИЯ Подмножество R декартова произведения M 1 M 2... M n называется n -арным или n -местным отношением. Если R M n, то говорят, что R - n -местное отношение на множестве M.

Пример. Файл базы данных с полями, значения которых находятся в полях M 1, M 2,..., M n представляет собой подмножество декартова произведения M 1 M 2... M n, т. е. n -арное отношение.

Если n = 1, то отношение называется унарным. Оно отражает наличие какого либо признака у данного множества. Например, отношение R Z «быть четным числом» на множестве целых чисел Z является унарным.

Наиболее часто встречаются 2 -местные или бинарные отношения.

Если для отношения R - ( a,b ) R, то это обычно обозначают aRb, если же (a, b) R, то обозначают a Rb.

Примеры. а) Бинарными отношения на множестве целых чисел Z являются:

Ok - «иметь одинаковый остаток от деления на k », O2 - «иметь одинаковую четность».

б) Пусть M - множество целых, рациональных или вещественных чисел. Бинарными отношения на множество целых, рациональных или вещественных чисел M являются отношения.

в) Пусть M - множество сотрудников фирмы. Бинарными отношения на M являются отношения:

«быть начальником», «не быть начальником», Рассмотрим способы задания отношений.

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

Пусть M = { a1,a 2,...,am } ; тогда бинарное отношение R M 2 задается по правилу:

Граф бинарного отношения является его геометрическим изображением и представляет собой схему, включающую • вершины, обозначаемые точками или кружочками, соответствующие элементам множества M = { a1,a 2,...,am }, на котором • дуги, соответствующие парам элементов, входящих в бинарные отношения, обозначаемые линиями со стрелками, направленными от вершины, соответствующей элементу ai к вершине, Пример. Отношение R «быть делителем на множестве M = { 1, 2, 3, 4 } » может быть задано матрицей:

или в виде графа:

Рассмотрим основные типы бинарных отношений.

Бинарное отношение R на множестве M называется рефлексивным, если для любого a M выполняется aRa.

Примеры: 1) отношения,=, на множестве действительных чисел;

2) отношение «не быть начальником» на множестве сотрудников организации.

Бинарное отношение R на множестве M называется антирефлексивным, если для любого a M выполняется a Ra.

Примеры: 1) отношения на множестве действительных чисел;

2) отношение «быть начальником» на множестве сотрудников организации.

Бинарное отношение R на множестве M называется симметричным, если для любых Примеры: 1) отношения на множестве действительных чисел;

2) отношение «быть родственником» на множестве людей.

Бинарное отношение R на множестве M называется антисимметричным, если для любых a,b M, a b из aRb следует b Ra.

Примеры: 1) отношения <,,,> на множестве действительных чисел;

Бинарное отношение R на множестве M называется транзитивным, если для любых a,b,c M из aRb и bRc следует aRc.

Примеры: 1) отношения <,,=,,> на множестве действительных чисел;

2) отношение «быть начальником» на множестве сотрудников организации.

Бинарное отношение R на множестве M называется антитранзитивным, если для любых a,b,c M из aRb и bRc следует a Rc.

Примеры: 1) отношение «несовпадение четности» на множестве целых чисел;

2) отношение «быть непосредственным начальником» на множестве сотрудников организации.

Бинарное отношение R на множестве M называется отношением эквивалентности, если оно Примеры: 1) отношение «иметь одинаковый остаток от деления на 2) отношение «учиться в одной группе» на множестве Отношение эквивалентности R разбивает множество M на непересекающиеся подмножества так, что любые элементы одного подмножества находятся в отношении R, а любые элементы разных подмножеств не находятся в отношении R. Данные подмножества называются классами эквивалентности, а их количество – индексом разбиения.

Бинарное отношение R на множестве M называется отношением нестрогого порядка, если оно Примеры: 1) отношение на множестве действительных чисел;

2) отношение «быть не старше» на множестве людей.

Бинарное отношение R на множестве M называется отношением строгого порядка, если оно Примеры: 1) отношение < на множестве действительных чисел;

2) отношение «быть начальником» на множестве сотрудников организации.

Отношения строгого и нестрогого порядка называются отношениями порядка.

Элементы a, b M называются сравнимыми по отношению порядка R, если aRb или bRa.

Множество M называется полностью упорядоченным множеством, если любые два элемента в нем сравнимы по некоторому отношению порядка R.

Примеры: 1) множество действительных чисел по отношениям Множество M называется частично упорядоченным множеством, если в нем есть хотя бы два элемента, несравнимые по некоторому отношению порядка R.

Примеры: 1) множество комплексных чисел отношениям ;

2) отношение «быть начальником» на множестве сотрудников организации.

2.1. ОСНОВНЫЕ ТИПЫ КОМБИНАТОРНЫХ ЗАДАЧ

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

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

Правило суммы. Если некоторый объект x можно распределить или выбрать k x способами, а некоторый объект y - k y способами, причем эти способы не пересекаются, то любой из этих объектов можно распределить или выбрать k x + k y способами.

Задача. Найти число всех маршрутов из пункта A в пункт B, если известно, что имеется 5 автобусных и 3 железнодорожных маршрута.

Правило произведения. Если некоторый объект x можно распределить (выбрать) k x способами, а после каждого варианта распределения (выбора) объекта x некоторый объект y можно распределить (выбрать) k y способами, то оба объекта (в указанном порядке) можно распределить (выбрать) k x k y способами.

Задача. Найти число всех маршрутов из пункта A в пункт B через пункт C, если известно, что имеется 5 маршрутов из пункта A в пункт C и маршрута из пункта C в пункт B.

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

Задача распределения элементов. Дано k различимых или неразличимых между собой предметов; их необходимо распределить по n ящикам так, чтобы выполнились заданные ограничения. Сколькими существует различных наборов заполненных ящиков, являющихся решениями этой задачи?

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

Сколькими существует различных наборов предметов, являющихся решениями этой задачи?

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

• если в наборе элементы множеств могут повторяться, то такие наборы называются наборами с повторениями, а иначе - наборами без повторений;

• если порядок элементов в наборе важен, то наборы называются размещениями, а если не важен – сочетаниями;

• размещения, содержащие все элементы данного множества, называются перестановками.

Схематически это может быть представлено в виде блок-схемы, показанной на рис. 2.1.

P n (k1, k 2,..., k n ) = 2.2. РЕШЕНИЕ КОМБИНАТОРНЫХ ЗАДАЧ Числом размещений с повторениями из n по k (обозначается An ) является число всех возможных вариантов распределения k различимых между собой предметов по n ящикам.

Пример. Сколькими способами можно распределить 3 различных шара по 6 лункам.

Числом размещений без повторений из n по k (обозначается An ) является число всех возможных вариантов распределения k различимых между собой предметов по n ящикам так, чтобы в каждом ящике было не более одного предмета.

Пример. Сколько вариантов состава призеров, занявших первое, второе и третье места, если всего в соревновании участвуют 10 спортсменов.

Решение. n = 10, k = 3, A10 = = 720.Числом перестановок без повторений по n (обозначается Pn ) является число всех возможных вариантов распределения n различимых между собой предметов по n ящикам так, чтобы в каждом ящике был один предмет.

Пример. Сколько вариантов построить 5 человек в один ряд.

Числом перестановок с повторениями (обозначается P n (k1, k 2,..., k n ) ) является число всех возможных вариантов распределения n предметов s различных типов по n ( ki = n ) ящикам так, чтобы в каждом ящике был один предмет.

Пример. Сколько различных слов можно написать из букв К,О,Л,О,К,О,Л.

Числом сочетаний без повторений из n по k (обозначается С n ) является число всех возможных вариантов распределения k неразличимых между собой предметов по n ящикам так, чтобы в каждом ящике было не более одного предмета.

Пример. Сколькими способами можно назначить наряд из 3 человек, если имеется 9 претендентов.

числом сочетаний с повторениями из n по k (обозначается С n ) является число всех возможных вариантов распределения k неразличимых предметов по n ящикам;

Пример. Сколькими способами можно поделить 10 яблок между

ИСПОЛЬЗОВАНИЕ КОМБИНАТОРИКИ В

ВЫЧИСЛЕНИЯХ

Биномиальные коэффициенты могут быть найдены с помощью треугольника Паскаля, где каждый внутренний элемент строки есть сумма стоящих над ним элементов предыдущей строки (рис. 1.1.) Теорема 2 (полиномиальная формула).

Задача. Раскрыть скобки в выражении ( x1 x2 + 2 )2.

Решение.

При нахождении значения полинома, возведенного в некоторую целую степень, для уменьшения количества вычислений удобно пользоваться полиномиальной формулой Воспользуемся данной формулой для нахождения значения следующего выражения: (a – b + 3)2.

Выпишем все возможные случаи, когда сумма степеней трех элементов равна двум: 200, 020, 002, 011, 101, 110.

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

3. МАТЕМАТИЧЕСКАЯ ЛОГИКА

Иногда значение 0 удобно интерпретировать как «ложь», а значение 1 - как «истина».

Булева функция f ( x1, x 2,..., x n ) = 0 для всех значений аргументов называется логической константой 0, а булева функция f ( x1, x 2,..., x n ) = для всех значений аргументов называется логической константой 1.

Существуют два основных способа задания булевых функций - таблицы истинности и логические формулы.

Таблицы истинности содержат значения функций для всех возможных комбинаций значений входящих в них булевых переменных. Очевидно, что булева функция f ( x1, x 2,..., x n ) с n аргументами имеет 2 n комбинаций значений аргументов. Поэтому ее таблица истинности содержит 2 n строк. Всех булевых функций с n аргументами - 2 2.

Для описания логических формул необходимо определить логические операции.

Конъюнкцией или логическим произведением двух логических переменных x и y называется логическая функция, принимающая • значение 1, если обе переменные принимают значение 1, • значение 0 - во всех остальных случаях.

Конъюнкция читается «x и y» и обозначается x y или xy или x & y.

Дизъюнкцией или логической суммой двух логических переменных x и y называется логическая функция, принимающая • значение 0, если обе переменные принимают значение 0, • значение 1 - во всех остальных случаях.

Дизъюнкция читается «x или y» и обозначается x y.

Отрицанием или инверсией логической переменной x называется функция, принимающая • значение 0, если x принимает значение 1, • значение 1, если x принимает значение 0.

Отрицание читается «не x» и обозначается x или ¬ x.

Импликацией или логическим следованием двух логических переменных x, называемой посылкой, и y, называемой следствием или заключением, называется логическая функция, принимающая • значение 1 - во всех остальных случаях.

Импликация читается «если x, то y» и обозначается x y. Очевидно, Эквиваленцией или логической равнозначностью двух логических переменных x и y называется логическая функция, принимающая • значение 0, если переменные x и y принимают одинаковые • значение 1, если переменные x и y принимают различные Эквиваленция обозначается x y или x ~ y или x = y.

Важную роль играют отрицания некоторых из введенных операций.

Штрихом Шеффера или антиконъюнкцией двух логических переменных x и y называется логическая функция, принимающая • значение 0, если обе переменные принимают значение 1, • значение 1 - во всех остальных случаях.

Штрих Шеффера обозначается x | y. Очевидно, x | y = x y.

Стрелкой Пирса или антидизъюнкцией или функцией Вебба двух логических переменных x и y называется логическая функция, принимающая • значение 1, если обе переменные принимают значение 0, • значение 0 - во всех остальных случаях.

Стрелка Пирса обозначается x y. Очевидно, x y = x y.

Коимпликацией двух логических переменных x и y называется логическая функция, принимающая • значение 0 - во всех остальных случаях.

Коимпликация обозначается x y. Очевидно, x y = x y.

Логической неравнозначностью или исключающим «или» или сложением по модулю 2 или суммой Жегалкина двух логических переменных x и y называется логическая функция, принимающая • значение 0, если переменные x и y принимают различные • значение 1, если переменные x и y принимают одинаковые Неравнозначность обозначается x y. Очевидно, x y = x y.

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

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

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

Логические формулы строятся из элементов алфавита логики по следующим правилам:

• любая логическая константа или переменная есть формула;

• если f - формула, то f тоже формула;

• если f и g - формулы, то f * g тоже формула, где * - произвольная логическая операция;

В формулах действует следующий порядок старшинства операций:

Если этот порядок необходимо изменить, используют скобки.

Подформулой формулы f называется любая ее часть, сама являющаяся формулой.

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

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

3) законы дистрибутивности:

5) действия с логическими константами:

x x = 1 - закон исключенного третьего, x x = 0 - закон противоречия;

10) закон двойного отрицания: x = x.

3.2. УПРОЩЕНИЕ ЛОГИЧЕСКИХ ФОРМУЛ Две логические формулы называются равносильными, если они имеют одинаковые таблицы истинности.

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

Правило подстановки. Пусть f 1A и f 2A - равносильные формулы содержащие подформулу A : f 1A ~ f 2A. Если подформулу A заменить в обеих формулах на подформулу B, то формулы f 1B и f 2B также будут равносильными: f 1B ~ f 2B.

Пример. Из равносильности формул x y ~ x y вытекает равносильность формул ( x z ) y ~ ( x z ) y.

Правило замены. Пусть в формуле f A выделена подформула A и B - равносильная ей формула: A ~ B. Если подформулу A в f A заменить на подформулу B, то полученная формула f B будет равносильна f A :

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

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

Рассмотрим пример упрощения следующей логической функции:

Используя закон двойного отрицания, получим Применяя закон де Моргана, имеем Еще раз применим закон двойного отрицания:

Используя эквивалентность для импликации Н1 Н 2 = Н1 Н 2, переходим к стандартному базису:

Применим закон двойного отрицания и закон поглощения и получим упрощенную эквивалентную формулу Для проверки эквивалентности составим таблицы истинности. В таблице должно быть 2 n = 23 = 8 (n — число переменных) различных наборов логических переменных А1, А2, А3. Для всех наборов логических переменных А1, А2 и А3 должны получиться одинаковые значения результатов логических операций, стоящих в левой и правой частях рассматриваемой эквивалентности.

Для левой части получим следующую таблицу истинности:

Для правой части:

Сравнивая значения выражений в левой и правой частях для всех наборов логических переменных А1, А2 и А3, убеждаемся в правильности полученного ответа.

3.3. ПОСТРОЕНИЕ СОВЕРШЕННЫХ И МИНИМАЛЬНЫХ

НОРМАЛЬНЫХ ФОРМ ЛОГИЧЕСКИХ ФУНКЦИЙ

Конъюнктивным одночленом (элементарной конъюнкцией) называется конъюнкция логических переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.

Пример. x1 x3 x4 - конъюнктивный одночлен; x1 x3 x1, x1 x3 x1, x1 x3 x4 - формулы, не являющиеся конъюнктивными одночленами.

Дизъюнктивной нормальной формой (ДНФ) булевой функции называется формула, имеющая вид дизъюнкции конъюнктивных одночленов.

При этом конъюнктивные одночлены называются членами ДНФ.

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

Дизъюнктивным одночленом (элементарной дизъюнкцией) называется дизъюнкция логических переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.

Пример. x1 x3 x4 - конъюнктивный одночлен; x1 x3 x1, x1 x3 x1, x1 x3 x4 - формулы, не являющиеся конъюнктивными одночленами.

Конъюнктивной нормальной формой (КНФ) булевой функции называется формула, имеющая вид конъюнкции дизъюнктивных одночленов.

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

Наиболее просто СДНФ и СКНФ для логической функции f ( x1, x 2,..., x n ) строятся с помощью таблицы истинности.

• для каждого набора значений переменных x1, x 2,..., xn, для которых f ( x1, x 2,..., x n ) = 1 выписывается конъюнктивный одночлен, содержащий все переменные xi = 1 и отрицания всех переменных x j = 0 ;

• все полученные конъюнктивные одночлены объединяются знаками дизъюнкции.

• для каждого набора значений переменных x1, x 2,..., xn, для которых f ( x1, x 2,..., x n ) = 0 выписывается дизъюнктивный одночлен, содержащий отрицания всех переменных xi = 1 и все переменные x j = 0 ;

• все полученные дизъюнктивные одночлены объединяются знаками конъюнкции.

Рассмотрим в качестве примера логическую функцию, описывающую принятие решения большинством голосов в коллективе из трех человек («комитете трех»):

Часто при построении СДНФ и СКНФ полученные формы содержат избыточную информацию, от которой можно избавиться и получить минимальные дизъюнктивную нормальную форму (МДНФ) и конъюнктивную нормальную форму (МКНФ).

Метод Квайна включает два этапа:

1) переход от СДНФ (СКНФ) к сокращенной форме;

2) переход от сокращенной формы к МДНФ (МКНФ).

Реализацию метода Квайна опишем на примере.

Пусть дана логическая функция f(x1,x2,x3), заданная таблицей истинности 1. Рассмотрим способ построения МДНФ с помощью метода Квайна.

В соответствии с правилом построения СДНФ используются строки Найдем все склеивающиеся пары:

Результаты операции склеивания вводим в выражение функции. Это не изменит ее значения.

Проведем операцию поглощения новыми членами старых членов нормальной формы:

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

Построим импликантную таблицу, в которой символом «*» отмечены возможности поглощения членов СДНФ простыми импликантами, а символом «!» - простые импликанты, входящие в ядро:

Ни один из членов сокращенной формы не может быть исключен из так, чтобы обеспечить поглащение всех членов СДНФ. Следовательно, МДНФ совпадает с сокращенной формой:

2. Рассмотрим СКНФ.

В соответствии с правилом построения СКНФ используются строки № 1, 4, 6:

Поскольку в данном выражении отсутствуют склеивающиеся пары, то оно является минимальной конъюнктивной нормальной формой записи.

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

Карты Вейча являются другой, более компактной формой представления таблиц истинности. Значения логической функции записываются в клетки карты Вейча. Каждая клетка карты соответствует определенному набору значений аргументов. Эти значения записаны по краям столбцов, на пересечении которых стоит клетка. При этом принимается, что, если стоит xi, то xi = 1, а если xi, то xi = 0. В клетку записывается значение на соответствующем наборе аргументов. Ниже приведен пример.

Карты Вейча обладают следующим свойством:

при переходе из клетки в клетку, соседнюю по строке или столбцу, изменяется значение только одной булевой переменной; свойство сохраняется, если осуществить сворачивание карты Вейча в цилиндр тор (поверхность объемного кольца («бублика»)) с объединением противоположных граней.

1) Пусть булева функция задана в виде СДНФ. Тогда указанное свойство означает, что если в паре соседних клеток содержатся единицы, то над соответствующими членами СДНФ может быть осуществлена операция склеивания. Можно доказать, что могут быть склеены члены СДНФ, соответствующие 2 k, k = 0,1,2,3,... клеткам с единицами, образующим прямоугольную область.

2) Пусть булева функция задана в виде СКНФ. Тогда указанное свойство означает, что если в паре соседних клеток содержатся нули, то над соответствующими членами СКНФ может быть осуществлена операция склеивания. Можно доказать, что могут быть склеены члены СКНФ, соответствующие 2 k, k = 0,1,2,3,... клеткам с нулями, образующим прямоугольную область.

Указанные свойства позволяют построить МДНФ (или МКНФ) в соответствии со следующим алгоритмом.

Шаг 1. Все клетки содержащие 1 (0), объединяются в минимальное число возможно больших прямоугольников с числом клеток 2 k, k = 0,1,2,3,.... Прямоугольники могут пересекаться или появляться в результате сворачивания карты Вейча в цилиндр.

Шаг 2. Каждый из прямоугольников представляется членом МДНФ (МКНФ), число переменных в котором на k меньше числа всех переменных. В этот член в соответствии с правилом склеивания включаются те переменные, которые в этой области не меняют своих значений (отрицания этих переменных для МКНФ).

Шаг 3. Полученные члены объединяются в минимальную форму.

Опишем метод построения МДНФ для этой карты Вейча.

Выделим прямоугольные области в карте Вейча, содержащие единицы (количество клеток в прямоугольной области может быть 1 или 2 или или 8; при определении прямоугольников карты Вейча предполагаются склеенными по краям).

Каждый из 4 полученных прямоугольников представляется членом МДНФ. В этот член в соответствии с правилом склеивания включаем те переменные, которые в этой области не меняют своих значений. Полученные члены объединяем в минимальную форму.

Следует отметить, что одна ячейка x1 x2 x3 не объединилась с другими, поэтому соответствующий член выписан полностью.

Опишем метод построения МКНФ для этой карты Вейча.

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

Следует отметить, что ячейки, содержащие нули, не могут быть объединены друг с другом. Поэтому выписываем соответствующие члены СКНФ полностью.

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

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

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

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

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

Схемы для МДНФ и МКНФ данной функции будет иметь вид:

4.1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ТЕОРИИ ГРАФОВ

• E = {e1, e2,..., em } - конечное множество, каждый элемент которого соответствует паре не обязательно различных элементов множества V.

Элементы множества V называются вершинами графа.

Если элемент множества E соответствует неупорядоченной паре вершин, т. е. ei ~ {vi1, vi 2 }, то он называется ребром, вершины vi1 и vi 2 - концами этого ребра. Говорят, что ребро ei = (vi1, vi 2 ) соединяет вершины vi1 и vi 2. Ребро, для которого vi1 = vi 2, называется петлей. Граф, содержащий только ребра, называется неориентированным графом.

Если элемент множества E соответствует упорядоченной паре вершин, т. е. ei ~ (vi1, vi 2 ), то он называется дугой, вершина vi1 - началом, а vi 2 концом этой дуги. Говорят, что дуга ei = (vi1, vi 2 ) исходит из вершины vi1 и заходит в вершину vi 2. Дуга, для которой vi1 = vi 2, называется ориентированной петлей. Граф, содержащий только дуги, называется ориентированным графом.

Обычно рассматривают только ориентированные или неориентированные графы.

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

Если ei ~ {vi1, vi 2 } или ei ~ (vi1, vi 2 ), то вершины vi1 и vi 2 называются смежными, а ребро (дуга) ei и вершины vi1 и vi 2 - инцидентными. Если конец ребра ei совпадает с концом ребра e j, то эти ребра называются смежными; если начало или конец дуги ei совпадает с началом или концом дуги e j, то эти дуги называются смежными.

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

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

Предположим, что G = (V, E ) простой или мультиграф.

Часть G = (V, E ) называется подграфом графа G, если в ней сохраняются все ребра или дуги между вершинами множества V V.

Часть G = (V, E ) называется суграфом графа G, если V = V.

Примеры.

Рассмотрим некоторые наиболее часто встречающиеся части графов.

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

Вершина, не имеющая смежных вершин, называется изолированной.

Последовательность вершин и ребер (дуг) (не обязательно различных) такая, что соседние вершины и ребра (дуги) инцидентны, называется путем. Если граф G ориентированный и в (4.1) vi 1 и vi - начало и конец дуги ei, то путь называется ориентированным. Если путь не содержит повторяющихся вершин (кроме, может быть, первой и последней) и ребер или дуг, то он называется простым. Если первая и последняя вершины пути совпадают, то он называется циклом.

Длиной пути называется число ребер (дуг), которые он содержит.

Неориентированный граф G Ориентированный граф G Суграф графа G, не содержащий циклов и являющийся максимальным по включению ребер или дуг суграфом, называется остовом графа G.

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

Если граф содержит одну компоненту связности, то он называется связным, а если более одной – несвязным.

Вершина v называется точкой сочленения, если ее исключение из графа G увеличивает количество его компонент связности. Ребро или дуга e называется мостом, если его исключение из графа G увеличивает количество его компонент связности.

Как легко видеть через не один простой цикл не может содержать точек сочленения и мостов.

Подграф G ориентированного графа G называется кликой, если 1) любые две вершины G смежны, 2) G не является подграфом ни одного подграфа графа G, обладающего свойством 1), т.е. является максимальным по включению вершин сильно связным подграфом графа G.

Графы, не содержащие циклов, называются лесами. Связные графы, не содержащие циклов, называются деревьями. Легко видеть, что компонентами связности лесов являются деревья.

Граф G называется пустым, если он не содержит вершин.

Неориентированный простой граф G называется полным, если 1) любые две различные его вершины являются смежными;

2) он не содержит петель.

Ориентированный простой граф G называется полным, если 1) для любой его вершины есть дуга, концом которой являются любая другая вершина;

2) он не содержит ориентированных петель.

Полный граф, как ориентированный, так и неориентированный, содержащий n вершин, обозначают K n.

Граф G = (V, E ) называется дополнительным к графу G = (V, E ) с тем же множеством вершин V, если он содержит все ребра или дуги, которые содержатся в полном графе и не содержатся в графе G.

Граф On, дополнительный к полному графу K n, называется 0графом. Легко видеть, что 0-граф On состоит из n изолированных вершин.

Рис. 4.12. Полный граф K 5 и дополнительный к нему 0-граф Граф G = (V1 V2, E ) называется двудольным, если его множество вершин разбивается на два непустых непересекающихся подмножества V и V2 так, что все вершины каждого подмножества попарно несмежны.

Двудольный граф G = (V1 V2, E ) называется полным двудольным графом, если любые две вершины из разных подмножеств V1 и V2 смежны.

Полный двудольный граф, у которого V1 = n1 и V2 = n 2 обозначается K n1,n2.

Теорема (Кёнига). Граф G является двудольным тогда и только тогда, когда он не содержит в качестве подграфов циклов нечетной длины.

Следствие. Лес является двудольным графом.

Примеры.

30. Планарные графы.

Граф G называется планарным, если его можно геометрически изобразить на плоскости без пересечения ребер (дуг).

Теорема (Понтрягина-Куратовского). Граф G является планарным тогда и только тогда, когда он не содержит в качестве подграфов графы K или K 3,3.

4.2. ИНВАРИАНТЫ ГРАФОВ Пусть задан граф G = (V, E ). К основным числовым характеристикам относятся:

число вершин графа - n ;

число компонент связности - k ;

цикломатическое число c = m + k n.

Граф G = (V, E ) называется раскрашенным, если каждой его вершине приписан цвет (или номер) так, чтобы никакие две смежные вершины не имели одного цвета (номера).

Минимальное число цветов, которыми можно раскрасить граф, называется его хроматическим числом - h.

Число вершин в клике наибольшего размера графа называется плотностью графа p. Плотность дополнительного к G графа G называется неплотностью графа G, которую обозначим p.

Максимальная длина простого пути в графе G называется диаметром графа d.

Степенью вершины vi V - deg vi называется число ребер или дуг, инцидентных этой вершине. При этом каждая дуга учитывается дважды.

Следующим инвариантом графа является вектор степеней вершин графа deg G = (deg v1, deg v 2,..., deg v n ).

Если граф G является ориентированным, то кроме степени для вершины vi V определяются deg vi - полустепень исхода – число дуг, началом которых является вершина vi ;

deg + vi - полустепень захода – число дуг, концом которых является вершина vi.

Инвариантами всего графа G являются вектор полустепеней исхода deg G = (deg v1, deg v 2,..., deg v n ), вектор полустепеней захода deg + G = (deg + v1, deg + v 2,..., deg + v n ).

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

Полные инварианты могут быть построены с помощью матричных представлений. Рассмотрим их.

Пусть G = (V, E ) - неориентированный граф.

Матрицей смежности графа G называется матрица A = ( aij ) размерности n n ( n - число вершин), которая определяется по правилу:

nij число ребер, концами которых являются вершины vi и v j aij = (петля учитывается дважды), 0, если вершины vi и v j несмежны.

Матрица A является симметрической, т. е. симметрична относительно главной диагонали.

Матрицей инциденций графа G называется матрица B = (bik ) размерности n m ( n - число вершин, m - число ребер), которая определяется по правилу:

2, если вершина vi инцидентна петле ek, bik = 1, если вершина vi инцидентна ребру, не являющемуся петлей ek, 0, если вершина vi неинцидентна ребру ek.

Числовые характеристики графа связаны с введенными матрицами следующими соотношениями: deg vi = a ij = bik Пусть G = (V, E ) - ориентированный граф.

Матрицей смежности графа G называется матрица A = ( aij ) размерности n n ( n - число вершин), которая определяется по правилу:

nij число дуг, исходящих из вершины vi и входящих в вершину v j, 0, если вершины vi и v j несмежны.

Матрица A в общем случае уже не будет являться симметрической.

Если G = (V, E ) - простой граф, то A - матрица бинарного отношения E.

Матрицей инциденций графа G называется матрица B = (bik ) размерности n m ( n - число вершин, m - число ребер), которая определяется по правилу:

1, если из вершины vi исходит дуга ek, не являющаяся петлей, bik = 1, если в вершину vi входит дуга ek, не являющаяся петлей, 0, если вершина vi неинцидентна дуге ek или ek является петлей.

Если граф G = (V, E ) не содержит петель, то матрица B полностью его характеризует. Если есть петли то вместо одной матрицы инциденций рассматривают две матрицы: исходящую матрицу инциденций В = (bik ) и входящую матрицу инциденций B + = (bik ), которые определяются следующим образом:

1, если из вершины vi исходит дуга ek, bik = 0, если вершина vi неинцидентна дуге ek ;

1, если в вершину vi входит дуга ek, bik = 0, если вершина vi неинцидентна дуге ek.

Все введенные матрицы инциденций связаны соотношением:

B = B B. Для петель, в частности, поучаем: bik = bik bik = 1 1 = 0.

Числовые характеристики графа связаны с введенными матрицами Матрица инциденций B является полным инвариантом, т. е. характеристикой однозначно определяющей неориентированный мультиграф или ориентированный мультиграф без петель. Для ориентированного мультиграфа с петлями полным инвариантом является пара матриц B + и Если G = (V, E ) является простым графом, то множество ребер или дуг однозначно определяется отношением E и, тем самым, полным инвариантом будет служить кроме матриц инциденций и матрица смежности A, независимо от того, является ли граф ориентированным или нет.

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

Рассмотрим примеры вычисления основных числовых инвариантов графов и их матричных представлений.

Пример 1. Пусть задан следующий неориентированный граф:

Обозначим вершины и ребра графа:

V = {v1,…,v7} – множество вершин графа;

E = {e1,…,e9} – множество ребер графа.

Рис. 4.15. Означенный ориентированный граф G = (V, E) Найдем основные инварианты:

3. Число компонент связности k = 2.

Одна компонента составлена из вершин{v1,v2, v3,v4, v5}, другая – {v6,v7}.

5. Хроматическое число h = 2.

Минимальная раскраска графа цветами «А» и «В» приведена на рис.

4.3.

Рис. 4.16. Минимальная раскраска графа G = (V, 6. Плотность графа p = 2: максимальную клику составляют, например, вершины v1 и v2.

7. Диаметр графа равен 4:

Это следует из того, что максимально длинный простой путь, например, (v1, e3, v3, e7, v5, e6, v2,, e5, v4) содержит 4 ребра.

8. Вектор степеней вершин графа G:

9. Матрица смежности графа G:

10. Матрица инциденций графа G:

Рассмотрим пример нахождения основных инвариантов ориентированных графов.

Пример 2. Пусть задан следующий граф:

Рис. 4.17. Исходный ориентированный граф Обозначим вершины и дуги графа:

V = {v1,…,v7} – множество вершин графа.

E = {e1,…,e10} – множество дуг графа.

Рис. 4.18. Означенный ориентированный граф G = (V, E) Найдем основные инварианты:

1. Число вершин |V| = n = 7.

2. Число ребер |E| = m = 10.

3. Число компонент связности k = 3. Одна компонента составлена из вершин{v1,v3, v5,v6}, вторая – {v2,v4}, третья – {v7}.

4. Цикломатическое число с = m + k – n = 10 + 3 – 7 = 6.

5. Хроматическое число h = 3.

Минимальная раскраска графа цветами «А», «В» и «С» приведена на рис.

4.6.

Рис. 4.19. Минимальная раскраска графа G = (V, E) Максимальную клику составляют вершины v3, v5 и v6 (рис. 4.5.).

7. Диаметр графа равен 3:

Это следует из того, что максимально длинный простой путь, например, (v1, e3, v3, e5, v5, e9, v6, ) содержит 3 дуги.

8. Вектор степеней вершин графа G:

Вектор полустепеней исхода вершин графа G:

Вектор полустепеней захода вершин графа G:

9. Матрица смежности графа G:

10. Матрица инциденций графа G:

исходящая матрица инциденций:

входящая матрица инциденций:

4.3. ЭЙЛЕРОВЫ И ГАМИЛЬТОНОВЫ ПУТИ И ЦИКЛЫ

Эйлеровым циклом называется цикл в графе G, который содержит все ребра в графе и каждое только один раз.

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

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

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

Следующая теорема устанавливает необходимое и достаточное условие эйлеровости и полуэйлеровости графа.

Теорема (Эйлера).

1) Граф G является эйлеровым тогда и только тогда, когда все вершины графа имеют четную степень.

2) Граф G является полуэйлеровым тогда и только тогда, когда все вершины графа, кроме двух, имеют четную степень. При этом путь начинается в одной вершине с нечетной степенью и заканчивается в другой.

20. Гамильтоновы графы.

Пусть G = (V, E ) - связный ориентированный мультиграф.

Гамильтоновым циклом называется простой цикл в графеG, который содержит все вершины в графе и каждую только один раз.

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

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

Очевидно, что если граф содержит гамильтонов цикл, то он содержит и гамильтонов путь.

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

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

Теорема (Дирака).

Если для всех вершин vi V графа G, имеющего n вершин, выполn няется deg vi, то граф является гамильтоновым.

Рассмотрим алгоритмы построения эйлерова пути или цикла в связном неориентированном эйлеровом мультиграфе G = (V, E ), принадлежащие Х.Тую.

Пусть сначала G = (V, E ) - полуэйлеров граф.

Обозначим u и w - вершины, между которыми будет строиться эйлеров путь, т. е. вершины с нечетными степенями Алгоритм построения эйлерова пути имеет следующий вид.

Шаг 1. Находим простой путь, соединяющий вершины u и w.

Шаг 2. Всем ребрам найденного пути присвоим метки h = 0.

Шаг 3. Если в G помечены все ребра, то переход к шагу 8.

Шаг 4. Пусть максимальная пометка ребер равна h. Найти непомеченное ребро e, смежное с каким-либо уже помеченным.

Шаг 5. Построить простой цикл из непомеченных ребер, содержащий ребро e Шаг 6. Пусть ранее достигнутая максимальная пометка ребер равна h. Тогда всем ребрам вновь построенного цикла присвоить пометку h + 1.

начинающийся в вершине u и заканчивающийся в вершине w.

При этом, если путь был определен до вершины xi, то последующее ребро ei +1 должно обладать следующими свойствами:

1) быть инцидентным xi ;

2) не быть уже включенным в путь;

3) иметь максимальную пометку.

Пусть теперь G = (V, E ) - эйлеров граф.

Обозначим u и w - две произвольные смежные вершины, соединенные ребром e0.

Алгоритм построения эйлерова цикла отличается от приведенного алгоритма только следующими шагами.

Шаг 1. Находим простой цикл, содержащий вершины u и w.

Шаг 8. Построить эйлеров цикл При этом, если путь был определен до вершины xi, то последующее ребро ei +1 должно обладать следующими свойствами:

1) быть инцидентным xi ;

2) не быть уже включенным в путь;

3) иметь максимальную пометку.

Теорема (Хоанг Туя). Алгоритм Хоанг Туя всегда позволяет построить эйлеров цикл в эйлеровом графе и эйлеров путь в полуэйлеровом графе.

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

Пусть задан неориентированный мультиграф.

Рис. 4.20. Исходный неориентированный граф Обозначим вершины и ребра графа:

V = {v1,…,v9} – множество вершин графа.

E = {e1,…,e18} – множество ребер графа.

Рис. 4.21. Означенный неориентированный граф G=(V,E) Найдем степени вершин графа G:

Все степени вершин являются четными, поэтому по теореме Л. Эйлера граф является эйлеровым, т. е. содержит эйлеров цикл.

Для того чтобы найти эйлеров цикл, выделим ребро e1, соединяющее различные вершины v1 и v9 и осуществим пометку ребер в соответствии с алгоритмом Х. Туя:

Рис. 4.22. Граф, помеченный в соответствии с алгоритмом Х.Туя Используя полученные пометки вершин, найдем эйлеров цикл:

v1, e4, v4, e11, v6, e14, v6, e12, v8, e18, v8, e17, v9, e16, v7, e8, v5, e10, v8, e13, v4, e9, v5, e7, v2, e5, v3, e3, v1, e2, v2, e6, v7, e15, v9, e1, v1.

Если граф является полуэйлеровым, т. е. содержит эйлеров путь, то пометки «0» ставятся на ребра любого простого пути, соединяющего обе вершины с нечетными степенями.

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

Условие теоремы Г. Дирака для рассматриваемого графа не выполняется. Поэтому сделать вывод о гамильтоновости, используя только эту теорему, нельзя.

С помощью перебора вариантов найдем гамильтонов путь v1, e3, v3, e5, v2, e7, v5, e8, v7, e16, v9, e17, v8, e14, v6, e11, v и гамильтонов цикл v1, e3, v3, e5, v2, e7, v5, e8, v7, e16, v9, e17, v8, e14, v6, e11, v4, e4, v1.

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

4.4. КРАТЧАЙШИЙ ПУТЬ В ГРАФЕ Пусть G = (V, E ) - ориентированный взвешенный связный граф. При этом веса приписаны дугам. Сумму весов дуг в пути будем называть длиной пути. Путь называется кратчайшим, если его длина минимальна.

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

Если (vi, v j ) E, то обозначим pij - вес этой дуги; иначе примем pij =.

В процессе реализации алгоритма вершины получают метки, равные длине пути от начальной вершины v0 до данной вершины vi.

Метки могут быть временными и окончательными.

Временная метка вершины vi qi - это кратчайший путь от вершины v0 до вершины vi, когда учтены возможно не все пути от вершины v0 до вершины vi.

Окончательная метка вершины vi Qi - это кратчайший путь от вершины v0 до вершины vi, когда учтены все пути от вершины v0 до вершины vi.

Рассмотрим общую схему реализации алгоритма.

Пусть требуется найти кратчайший путь от вершины v0 до вершины Шаг 1. Вершине v0 присваивается окончательная метка Q0 = 0 (что означает нулевой кратчайший путь от вершины до самой себя). Всем остальным вершинам графа приписываются временные метки qi =.

Шаг 2. Пусть v j - последняя вершина которой присвоена окончательная метка. Каждой вершине vi, не имеющей окончательной метки присваивается новая временная метка qi = min( qi, Q j + pij ).

Шаг 3. Определяется наименьшая из всех временных меток и объявляется окончательной (если таких меток несколько, выбирается любая).

Шаг 4. Если вершина vn не получила окончательной метки, то переход к шагу 2. Иначе величина Qn искомая длина кратчайшего пути.

Шаг 5. Величина Qn - искомая длина кратчайшего пути. Найти кратчайший путь, двигаясь обратно от vn к v0 только через те вершины, из которых последующие получали окончательные метки.

Рассмотрим пример нахождения кратчайшего пути в заданном графе из вершины v0 в вершину u.

1. Исключим петли и кратные дуги большего веса из графа, после чего обозначим вершины графа:

V = {v0,…,v5, u} – множество вершин графа.

Построим таблицу, описывающую шаги реализации метода поиска в ширину.

шаги Таким образом, кратчайший путь проходит через вершины: v0, v2, v1, v3, u. Его длина равна 12.

4.5. ПОСТРОЕНИЕ МИНИМАЛЬНОГО ОСТОВНОГО ДЕРЕВА

При этом веса прописаны ребрам. Граф G может содержать несколько остовных деревьев, т. е. связных суграфов T = (V,U ), U E, не содержащих циклов. Сумму весов ребер остовного дерева будем называть весом этого дерева. Дерево называется минимальным, если его вес минимален.

Наиболее просто описывается построение остовного дерева с помощью жадного алгоритма (алгоритма Краскала).

Пусть граф G имеет n вершин. Тогда, как это было показано выше, число ребер в остовном дереве будет содержать n 1 ребро.

Алгоритм имеет следующий вид.

Шаг 1. Построим 0-граф T = (V, ).

Шаг 2. Составить список ребер графа, упорядоченных по возрастанию весов.

Шаг 3. Добавить очередное ребро ei из списка в граф T.

Шаг 4. Проверить, не появился ли в графе T цикл.

Шаг 5. Если цикл появился, то ребро ei из графа T исключить.

Шаг 6. Если число ребер в графе T равно n 1, то T - искомое минимальное остовное дерево. Иначе - переход к шагу 3.

Теорема (Краскала). Приведенный алгоритм приводит к построению минимального остовного дерева.

Покажем способ нахождения минимального остовного дерева с помощью жадного алгоритма (алгоритма Краскала) на примере.

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

Рис. 4.24. Исходный неориентированный взвешенный граф Обозначим вершины и ребра графа:

V = {v1,…,v7} – множество вершин графа.

E = {e1,…,e14} – множество ребер графа.

Составим таблицу на основе матрицы инциденций графа G=(V,E), в которой 1) все ребра упорядочены по возрастанию весов;

2) указаны веса ребер;

3) отмечен признак «+» образования цикла при добавлении данного ребра.

Образ.

На основе таблицы построим минимальное остовное дерево:

Рис. 4.26. Минимальное остовное дерево графа G=(V,E) Меньшую вычислительную сложность имеет алгоритм ближайшего соседа (алгоритм Прима), построенный по схеме поиска в ширину.

Пусть граф G имеет n вершин. Тогда, как это было показано выше, число ребер в остовном дереве будет содержать n 1 ребро.

Алгоритм имеет следующий вид.

Шаг 1. Выбирается произвольная вершина vi и строится граф из одной изолированной вершины T = ( vi, ).

Шаг 2. Среди всех ребер, не включенных в граф T и инцидентных вершинам графа T, выбирается ребро e = ( v j, v k ), где v j предполагается включенным в граф T. Если таких ребер несколько, то выбирается любое.

Шаг 3. Ребро e и вершина v k включаются в граф T.

Шаг 4. Если число ребер в графе T равно n 1, то T - искомое минимальное остовное дерево. Иначе - переход к шагу 2.

Теорема (Прима). Приведенный алгоритм приводит к построению минимального остовного дерева.

Покажем способ нахождения минимального остовного дерева с помощью алгоритма ближайшего соседа (алгоритма Прима) на примере.

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

Рис. 4.27. Исходный неориентированный взвешенный мультиграф Обозначим вершины графа:

V = {v1,…,v8} – множество вершин графа.

Построим таблицу, описывающую шаги реализации метода поиска в ширину.

Вершина На основе таблицы построим минимальное остовное дерево:

Рис. 4.29. Минимальное остовное дерево графа G=(V,E)

5. КОНЕЧНЫЕ АВТОМАТЫ

Число символов в слове называется его длиной. Допускается существование пустых слов.

При функционировании автомата по входному слову x и начальному состоянию s0 находятся выходное слово y и слово состояний s.

Если в автомате выделено начальное состояние s0, то он называется инициальным. Инициальный автомат задается шестеркой 20. Способы задания конечных автоматов.

Конечные автоматы можно задавать с помощью таблиц, определяющих функции f и g или графически с помощью диаграммы Мура, представляющей собой взвешенный ориентированный мультиграф. При этом • вершины графа соответствуют состояниям, • дуги - переходам из состояния в состояние;

• веса дуг – пары {xi / y j }, где xi - входной, а y j соответствующий выходной символ при данном переходе.

Если автомат является инициальным, то начальное состояние обычно помечают символом «*».

Обычно выделяют два основных класса задач, решаемых с помощью автоматов:

1) распознавание принадлежности входных слов данному множеству (автоматы-распознаватели);

2) преобразование входных слов в выходные в соответствии с основным предназначением автомата (автоматы-преобразователи).

Точно провести границу между этими типами автоматов не всегда оказывается просто.

Приведем пример функционирования автомата-преобразователя.

Пусть функция переходов f и функция выходов g заданы таблично:

Составим по данной таблице полное описание автомата с помощью кортежа Входной алфавит: X = {А, Ш, Л}, алфавит состояний S = {s0, s1, s2}, выходной алфавит Y = {0, 1}, функция переходов f : XS S:

функция выходов g : XS Y:

начальное состояние s1.

По заданному описанию построим диаграмму Мура.

Рис. 5.1. Диаграмма Мура автомата-преобразователя Для заданного начального состояния автомата s1 и заданного входного слова x = ШАЛАШ найдем выходное слово y и конечное состояние, в котором будет находиться автомат:

Конечное состояние - s0, выходное слово y = 01011.

5.2. АВТОМАТЫ-РАСПОЗНАВАТЕЛИ Автомат-распознаватель позволяет распознать принадлежность входного слова данному множеству. Его описание аналогично описанию автомата-преобразователя.

Приведем пример построения автомата-распознавателя, осуществляющего подсчет количества троек последовательно следующих символов «К». Для этого необходимо найти функции выходов g и переходов f автомата-распознавателя и построить для него диаграмму Мура.

Пусть входной алфавит представляет собой множество X = {#, К}, где # - любой символ, кроме «К»;

выходной алфавит – множество Y ={0, 1, 2, …N}, где N – максимальная длина входного слова.

Для решения задачи достаточно использовать алфавит состояний, включающий 3 состояния:

• s0 – начальное состояние или состояние, в котором находится автомат после ввода #, • s1 – состояние, в котором находится автомат после ввода «К», если предыдущий символ был # или пустой, • s2 – состояние, в котором находится автомат после ввода не менее двух «К».

Таким образом, алфавит состояний представляет собой множество S = {s0, s1, s2}.

Из описания состояний вытекает, что функция переходов f имеет следующий вид:

Для описания функции выходов g необходимо описать алгоритм подсчета числа троек n последовательно следующих символов «К». Первый выходной символ n=0. Выражение n:=n+1 означает, что текущий выходной символ увеличивается на 1. В дальнейшем используется новое значение n.

Таким образом, функция выходов g имеет вид:

Полученное описание автомата-распознавателя позволяет построить его диаграмму Мура:

Рис. 5.2. Диаграмма Мура автомата-распознавателя

ЧАСТЬ III. КОНТРОЛЬНАЯ РАБОТА

1. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ

КОНТРОЛЬНОЙ РАБОТЫ

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

Слушатель-заочник выполняет контрольную работу строго в соответствии со своим вариантом. Номер варианта определяется по номеру в списке группы, предоставляемым преподавателем. Произвольный выбор варианта контрольных работ не допускается.

Контрольная работа № 1 включает в себя 17 заданий по всем разделам курса.

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

- условие каждой задачи записывается полностью;

- решение задач излагается подробно, при необходимости делаются ссылки на учебную литературу;

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

Контрольная работа оценивается преподавателем по системе «зачтено» или «незачтено». Если контрольная работа не зачтена, слушатель должен внимательно изучить рецензию на контрольную работу, исправить все недостатки, указанные преподавателем, и прислать на повторную проверку исправленные задания совместно с первоначальной работой.

К итоговому зачету слушатель-заочник допускается только при наличии зачтенной контрольной работы.

2. ЗАДАНИЯ КОНТРОЛЬНОЙ РАБОТЫ

(Здесь использованы следующие обозначения:

N – множество натуральных чисел, Z – множество целых чисел).

варианта Построить матрицу и граф бинарного отношения и определить тип этого отношения.

варианта Быть в сумме четным числом на множестве {1, 2, 4, 5, 6} Быть отцом на множестве {внук, сын, отец, дед, прадед} Быть в сумме действительным числом на множестве Быть в сумме чисто мнимым числом на множестве Быть больше по длине на множестве векторов Быть младше на множестве воинских званий {майор, капитан, подполковник, лейтенант, полковник} Быть меньшим по мощности на множестве множеств { {0, 1.

Быть в сумме нечетным числом на множестве {-1, -2, 9, -7, -6} Быть делителем на множестве {2, 3, 4, 6, 9} Иметь различное количество букв на множестве слов {король, Быть раньше в календаре на множестве месяцев { декабрь, Быть в сумме четным числом на множестве {-1, -2, 3, -7, 6} Быть меньше по длине на множестве векторов Быть больше по модулю на множестве из комплексных чисел Относиться к одному времени года на множестве месяцев { декабрь, июнь, июль, май, март } варианта Быть в сумме числом, принадлежащим множеству {1, 2, 3,4, 5, Быть в сумме нечетным числом на множестве {1, 2, 4, 5, 6} Иметь одинаковое количество букв на множестве слов { декабрь, июнь, июль, май, март } Быть больше по модулю на множестве из комплексных чисел Быть старше на множестве воинских званий {майор, капитан, подполковник, лейтенант, полковник} Иметь одинаковое количество букв на множестве слов {король, Быть потомком на множестве {внук, сын, отец, дед, прадед} Быть большим по мощности на множестве множеств { {0, 1. 2}, Быть в сумме кратным 3 на множестве чисел{1, 2, 4, 5, 6} Быть в сумме отрицательным числом на множестве Начинаться с одной буквы на множестве слов {король, ферзь, Быть расположенным в одном государстве на множестве городов {Москва, Воронеж, Киев, Минск, Одесса, Новгород} Быть подчиненным на множестве {командир отделения, командир взвода, начальник курса, начальник факультета} Быть меньше по мощности на множестве из множеств {множество курсантов, множество учащихся, множество людей младше 25 лет, множество людей} Раскрыть скобкив заданном выражении, пользуясь полиномиальной формулой.

варианта варианта Решите следующие задачи по комбинаторике (в случае возможности различных толкований условий выбрать любое и пояснить).

варианта На должности командиров отделений требуется поставить курсантов. Сколькими способами можно их выбрать, если в На плацу были построены взвода с различных курсов: 4 взвода с 1-го курса, 7 взводов со 2-го курса, 3 взвода с 3-го курса и взвод с 4-го курса. Сколько способов повзводного убытия с На концерт из 10 отличников требуется отобрать 6. Сколькими Студент купил 7 шоколадок и повстречал на своем пути 3 девушек? Сколькими способами он мог их угостить?

В портмоне 4 отделения. Сколькими способами можно разложить 2 денежные купюры, чтобы в отделении было не более В городе N всем семьям военнослужащих выдали двухкомнатные квартиры. Среди льготников – 23 семьи имеют 1 ребенка, у 32 семей есть два ребенка, 4 семьи имеют трех и более детей.

Сколькими способами можно распределить между ними квартиры?

В магазине продаются различные виды товаров по одной цене:

погоны, звездочки, нашивки, нарукавные знаки, пуговицы, заколки, кокарды. У покупателя денег хватит только на три предмета. Сколько различных наборов товаров он может приобрести?

варианта Сколькими способами можно распределить 6 пистолетов для Для создания баскетбольной команды требуется выбрать 8 человек. Сколько различных команд можно составить, если желающих оказалось 13?

Для уборки территории было выдано 12 веников. Сколькими способами можно распределить их между 18 курсантами?

На ужин пришли 16 курсантов, а накрыто было на 19. Сколькими способами можно распределить лишние блюда между В комнате хранения спецсредств имеется 12 пустых мест. После дежурства 6 человек сдали спецсредства. Сколькими способами можно их разложить по местам хранения?

На выдаче вторых блюд в столовой осталось 23 тарелки.

Сколькими способами их можно распределить между 8 курсантами, стоящими в наряде?

В группе 16 юношей и 8 девушек. Сколько возможно вариантов построения их в одну колонну?

В распоряжении инженера 12 извещателей различных типов.

На объекте система сигнализации состоит из 3 рубежей. Каждый рубеж оборудуется извещателями только одного типа, причем запрещается использовать на двух и более рубежах извещатели одного типа. Сколько различных вариантов системы сигнализации можно спроектировать?

На дежурство ППС заступает с собаками: 12 овчарок, 4 терьера, 3 добермана. Сколькими способами их можно распределить варианта На линию старта вышли 8 спортсменов. Сколько последовательностей можно составить из результатов их финиширования при условии, что все приходят на финиш поодиночке?

На контрольной работе дано 6 заданий. Выполнять задания можно непоследовательно. Сколько последовательностей выполнения задач можно составить?

В группе 32 студента. В течение занятия половина из них должна отчитаться за домашнюю работу. Сколько последовательностей из отсчитывающихся студентов можно составить?м К окну выдачи оружия подошли 14 офицеров. Сколькими способами они могут образовать очередь?

В комнате проживают 15 курсантов. Сколькими способами их можно разместить на 15 кроватях?

На взвод курсантов из 23 человек возложено 14 обязанностей по совершению общественных поручений. Сколькими способами их можно распределить между курсантами?

В строю стоят 25 курсантов. Сколькими способами можно выбрать 6 из них для проверки строевой подготовки?

В патруль по охране на 8 трехсменных постов заступили курсантов. На каждый пост заступает 1 человек. Сколькими способами можно распределить курсантов между постами для На складе имеется 16 персональных компьютеров. Сколькими различными способами их можно распределить между 22 кафедрами, но так, чтобы никто не получил более одного компьютера?

В столовой предлагается комплексный обед из 4 блюд. На обед поварами было приготовлено 12 различных блюд. Сколькими способами можно пообедать в столовой?

варианта Палитра состоит из 8 цветов. Требуется раскрасить «Боевой листок» в 3 цвета. Сколькими способами это можно выполнить?

На группу в количестве 28 курсантов дано 12 нарядов. Сколькими способами можно распределить их между курсантами?

В оружейной комнате находится 23 автомата, 24 пистолета, бронежилетов, 23 каски, 42 палки резиновых. Разрешается взять два предмета. Сколькими способами можно вооружиться?

Сколькими способами можно распределить 6 автоматов между Построить таблицу истинности для следующих выражений и представить их в СДНФ и СКНФ.

варианта варианта Упростить логическое выражение. Осуществить переход к стандартному базису (отрицание только над логическими переменными) и построить схему из функциональных элементов.

варианта варианта Найти МДНФ и МКНФ для логической функции f(x1,x2,x3), заданной таблицей истинности а) методом Квайна-Мак-Клосски;

б) методом карт Вейча.

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

11.

19.

21.

31.

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

21.

31.

1. Проверить, является ли граф, изображенный на рисунке, эйлеровым или полуэйлеровым.

2. Найти эйлеров путь или эйлеров цикл.

3. Проверить достаточное условие гамильтоновости графа, изображенного на рисунке (теорему Г. Дирака).

4. Найти гамильтонов путь или цикл, если они существуют.

5. Сделать вывод о гамильтоноввости или полугамильтоновости заданного графа.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

25.

26.

27.

28.

29.

30.

31.

ЗАДАНИЕ 15.

Найти кратчайший путь и его длину из вершины v0 в вершину u.

11.

15.

17.

22.

29.

ЗАДАНИЕ 16.

Найти минимальное остовное дерево • для четных номеров вариантов - с помощью жадного алгоритма (алгоритма Краскала);

• для нечетных номеров вариантов - с помощью алгоритма ближайшего соседа (алгоритма Краскала).