Материал: Дискретная математика. учебное пособие. Горбунов В.В., Лапшина М.Л

Вопросы для самопроверки

1. Что называется высказыванием?

2. Приведите пример высказываний. Какое высказывание называется истинным, а какое ложным?

3. Что называется составным высказыванием?

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

5. Какие основные символы используются в теории высказываний?

6. Какие связки простейшие? Назовите другие связки.

7. Что такое таблица истинности высказывания и как она строится? Как еще называется эта таблица?

8. Какие существуют логические отношения между высказываниями?

9. Перечислите варианты импликации.

10. Сформулируйте основные законы алгебры высказываний. Как их доказать?

11. Что такое булева функция?

12. Как строится таблица истинности для булевых функций?

13. Что такое ДНФ и КНФ?

14. Дайте определение совершенного одночлена.

15. Приведите правило преобразования формул в СДНФ и СКНФ.

16. Как булевы функции связаны с формулами алгебры высказываний?

5. Теория графов

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

5.1. Ориентированные графы

Говорят, что задан ориентированный граф G (directed graph), если заданы два множества: непустое множество V={ ,..., } — множество вершин графа, и множество X упорядоченных пар < , >, где , V. Это множество называется множеством дуг (arcs) графа.

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

Каждой дуге < , > при изображении орграфа ставится в соответствие линия со стрелочкой (Рис. 6). Говорят, что дуга < , > исходит из вершины (начало дуги) и заходит в вершину (конец дуги). Вершины и называются смежными. Дуга вида < , > называется петлёй. Дуга называется инцидентной вершине, если она заходит или исходит из неё. Смежность есть отношение между однородными элементами графа, тогда как инцидентность является отношением между разнородными элементами.

Для орграфа, изображенного на рис. 6, множество вершин: V={ , , , , }, множество дуг: X={< >,< >,< >,< >,< >,< >,< >}.

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

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

Полустепень захода вершины ^(v) – количество дуг, заходящих в вершину (число элементов множества ). Петля увеличивает полустепень исхода вершины и полустепень захода вершины на 1.

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

Для орграфа, изображенного на рис. 7, множество , множество .

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

5.2. Неориентированные графы

Говорят, что задан неориентированный граф G (undirected graph), если заданы два множества: непустое множество V={ ,..., } – множество вершин графа (vertices, nodes), множество Q неупорядоченных пар ( , ), где , V. Это множество называется множеством рёбер (edges) графа. Таким образом, ( , ) и ( , ) обозначает одно и то же ребро. Множество Q является множеством двухэлементных подмножеств множества V.

Вершины и называются смежными, если существует соединяющее их ребро. Вершины и называются концами ребра. В этой ситуации каждая из вершин называется инцидентной ребру ( , ), а ребро ( , ) называется инцидентным каждой из вершин и . Два ребра, инцидентные одной и той же вершине, называются смежными.

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

Для графа, изображенного на рис. 8, ( )=1, ( )=3.

Каждое ребро, не являющееся петлей, вносит вклад в степень ровно двух вершин графа. Следовательно, справедлива теорема (лемма о рукопожатиях): удвоенное число ребер равно сумме степеней его вершин:

,

где n – число вершин графа, m – число его ребер.

Из равенства следует еще одна теорема: число вершин нечетной степени обязательно четно в любом графе.

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

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

Граф с петлями называется псевдографом. Граф, не содержащий петель и кратных ребер, называется обыкновенным, или простым графом (simple graph).

Подграфом называется часть графа, образованная подмножеством вершин вместе со всеми ребрами, соединяющими вершины из этого множества.

Некоторые классы графов получили особые наименования. Граф с любым количеством вершин, не содержащий ребер, называется пустым. Обыкновенный граф с n вершинами, любая пара вершин которого соединена ребром, называется полным и обозначается Kn (очевидно, что в полном графе n(n-1)/2 ребер). Граф G называется полным, если любые две его различные вершины соединены ребром, и он не содержит параллельных ребер. Дополнением графа G называется граф с теми же вершинами, что и граф G и содержащий только те ребра, которые нужно добавить к графу G, чтобы получился полный граф.

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

5.3. Матричное задание ориентированных графов

О

риентированный граф , где V={ ,..., } может быть описан квадратной матрицей смежности , где 1, если из вершины в вершину идет дуга, и 0, если нет дуги из вершины в вершину . Квадратная матрица размерности описывает отношение смежности вершин. Номера строк и столбцов матрицы A соответствуют номерам вершин графа. Для того чтобы найти число ⁺(v), необходимо найти сумму элементов соответствующей строки матрицы смежности. Для определения полустепени захода ^(v) необходимо найти сумму элементов соответствующего столбца матрицы смежности.

Для орграфа на рис. 10 матрица смежности имеет вид:

.

Граф G(V, X), где V={ ,..., }; X={ ,..., } с помощью матрицы B, может быть описан с помощью матрицы инцидентности или матрицы инциденций, отражающей инцидентность вершин и дуг. Номера строк матрицы B соответствуют номерам вершин, а номера столбцов — номерам ребер. Матрица инциденций графа является прямоугольной матрицей размерности , элемент которой равен плюс единице, если i-я вершина является началом j-ой дуги, минус единице, если i-я вершина является концом j-ой дуги, и нулю в остальных случаях. Если дуги графа, изображенного на рис. 10, расположены в порядке нумерации следующим образом: < >,< >,< >,