Задания для самостоятельной работы

1. Приведите пример гиперграфа.

2. Для произвольного гиперграфа запишите матрицу инцидентости.

3. Для произвольного гиперграфа запишите матрицу смежности.

4. Для произвольного гиперграфа постройте двойственный граф.

5. Задайте произвольный гиперграф и покажите на нем примеры цепей различной длины.

6. Приведите примеры гиперграфов, являющихся деревьями.

7. Задайте произвольный гиперграф и постройте его раскраску.

8. Для произвольного гиперграфа постройте двудольный граф Кенига.

9. Составьте алгоритм задания матрицы смежности гиперграфа.

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

 

Тестовые задания к модулю 4

1. Множество линий, соединяющих любые пары вершин графа – это:

а) множество ребер,

b) множество вершин,

c) множество петель,

d) множество дуг,

e) множество элементов.

 

2. Совокупность вершин, смежных с вершиной x_i графа G – это:

a) cписок связности,

b) матрица инцидентности,

c) список смежности,

d) матрица связности,

e) матрица смежности.

 

3. Когда вершины x_i и x_j связаны между собой ребром u_ij, это означает следующее:

a) вершина x_i инцидента ребру u_ij,

b) вершина x_i смежна ребру u_ij,

c) вершина x_i смежна с вершиной x_j,

d) вершина x_i инцидента вершине x_j,

e) вершина x_i связана с ребром u_ij.

 

4. Когда два ребра инцидентны одной вершине x графа G, то справедливы высказывания:

1) вершина смежна с этими ребрами,

2) эти ребра смежны с вершиной x,

3) эти ребра смежны между собой,

4) вершина x инцидента этим ребрам,

5) ребра инциденты вершине x.

5. Когда ребро u_ij соединяет вершины x_i и x_j графа G, то справедливы высказывания:

· вершины x_i и x_j инцидентны ребру u_ij

· вершины x_i и x_j смежны с ребром u_ij,

· ребро u_ij смежно вершине x_j,

· вершина x_j инцидента вершине x_i,

· ребро u_ij смежно вершине x_{i .}

6. Граф, у которого всем вершинам соответствуют некоторые целые числа – это:

a) числовой граф,

b) целый граф,

c) помеченный граф,

d) строгий граф,

e) регулярный граф.

7. Мультичисло графа – это:

a) число ребер,

b) число вершин,

c) максимальное число ребер соединяющих две вершины,

d) число ребер соединяющих две вершины,

e) число циклов.

8. Пусть задан граф G = (X, U). При X = Æ и U = Æ, можно сказать, что граф G – это:

a) мультиграф,

b) нуль-граф,

c) пустой граф,

d) полный граф,

e) регулярный граф.

9. Граф G = (X, U) в котором любые две вершины соединены ребром – это:

a) мультиграф,

b) нуль–граф,

c) пустой граф,

d) полный граф,

e) регулярный граф.

10. Граф G = (X, U) в котором вершины имеют одинаковую локальную степень – это:

a) мультиграф,

b) нуль–граф,

c) пустой граф,

d) полный граф,

e) регулярный граф.

11. Граф G’ = (X’, U’) полученный путем удаления из графа G = (X, U) некоторого числа вершин вместе с инцидентными им ребрами – это:

a) подграф,

b) разрез,

c) суграф,

d) дополнение,

e) блок.

 

12. Конечная последовательность ребер вида S = (x ₀, x ₁), (x ₁, x ₂), …, (x_{k –1}, x_k), где x ₀ и x_k – соответственно начальная и конечная вершины, это:

a) маршрут,

b) цепь,

c) цикл,

d) простая цепь,

e) простой цикл.

 

13. Длиной маршрута в графе называется:

a) расстояние между начальной и конечной вершинами,

b) сумма стоимостей,

c) число ребер маршрута,

d) число вершин маршрута,

e) число вершин графа.

 

14. Для подсчета числа маршрутов длины n в графе необходимо выполнить следующие действия:

· возвести матрицу смежности графа в степень n,

· возвести матрицу инцидентности графа в степень n,

· перебрать возможные варианты,

· перемножить ребра,

· перемножить вершины.

 

15. Цикл, не содержащий повторяющихся вершин кроме первой и последней – это:

a) цепь,

b) цикл,

c) простая цепь,

d) простой цикл,

e) эйлеров цикл.

16. Две вершины графа G являются связными, если выполняются следующие условия:

a) существует ребро инцидентное этим вершинам,

b) существует маршрут, где эти вершины являются конечными,

c) вершины соединены n ребрами,

d) вершины являются смежными,

e) граф полный.

17. Граф, между любыми двумя вершинами которого можно построить маршрут – это:

a) связный граф,

b) регулярный граф,

c) полный граф,

d) смежностный граф,

e) простой граф.

18. Цикл, проходящий по всем ребрам графа один раз – это:

a) простой цикл,

b) полный цикл,

c) эйлеров цикл,

d) гамильтонов цикл,

e) фундаментальный цикл.

19. Задача нахождения в полном графе с весами на ребрах гамильтонова цикла, у которого сумма ребер минимальна, носит название:

· задача Петри,

· задача Дирака,

· задача коммивояжера,

· транспортная задача,

· задача о назначениях.

 

20. Начальная вершина графа T – это:

a) дерево,

b) лес,

c) ветвь,

d) кустарник,

e) корень.

21. Ребра, выходящие из начальной вершины графа T – это:

a) дерево,

b) лес,

c) ветви,

d) кустарник,

e) корни.

22. Число покрывающих деревьев в полном графе K₄ равно:

a) 4,

b) 8,

c) 16,

d) 2,

e) 32.

23. Для графа T, являющегося деревом, верны следующие утверждения:

· граф T имеет n – 1 ребро,

· граф T не содержит циклов,

· граф T не связен,

· любые две вершины графа T соединены единственным циклом,

· любые две вершины графа T соединены циклом.

 

24. Длина кратчайшей цепи, соединяющей вершины x_i и x_j графа G – это:

a) протяженность вершин,

b) удаление вершин,

c) расстояние между вершинами,

d) последовательность вершин,

e) удаленность вершин.

25. Наименьшее число ребер, которые нужно удалить из графа, чтобы он стал деревом – это:

a) цикломатическое число,

b) хроматическое число,

c) число внутренней устойчивости.

d) число внешней устойчивости,

e) число внутренней полноты.

26. Цикломатическое число определяется по формуле g(G) = m – n + k, где m –число вершин графа G, n – число его ребер, а k – это

a. Число компонент связности

b. Число циклов

c. Число цепей

d. Число простых цепей

e. Число простых циклов

27. Разбиение множества вершин X на k непересекающихся классов таких, что внутри каждого класса не должно содержаться смежных вершин – это:

a) разрез графа,

b) сечение графа,

c) раскраска графа,

d) пересечение графа,

e) разбиение графа.

28. При раскраске графа одним цветом красятся вершины, отвечающие следующим требованиям:

a) они являются сильно связными,

b) они являются слабо связным,

c) они являются связными,

d) они являются не связными,

e) они являются частично связными.

29. Подмножество, любые две вершины которого являются не смежными, может называться:

a) внутренне устойчивое,

b) внешне устойчивое,

c) максимально внутренне устойчивое,

d) независимое,

e) полное.

30. Подмножество, вершины которого смежны со всеми остальными вершинами графа – это подмножество:

a) полное,

b) внутренне устойчивое,

c) внешне устойчивое,

d) независимое,

e) несвязное.

31. Для определения числа внешней устойчивости необходимо определить:

· мощность минимального внешне устойчивого подмножества,

· число внутренней устойчивости,

· число минимальных внешне устойчивых подмножеств,

· число внешне устойчивых подмножеств.

· число ребер графа.

 

32. Подмножество являющееся одновременно внутренне и внешне устойчивым – это

a) клика,

b) ядро,

c) доминирующее подмножество,

d) независимое подмножество,

e) базовое подмножество.

КРИТЕРИИ ОЦЕНКИ

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

85 – 100% правильных ответов – оценка «отлично»;

70 – 84% правильных ответов – оценка «хорошо»;

55 – 69% правильных ответов – оценка «удовлетворительно»;

менее 55% правильных ответов – оценка «неудовлетворительно».

 

ГЛОССАРИЙ к модулю 4

Глоссарий к главе 1

Блок графа – это его максимальный неразделимый подграф.

Вершинная связность графа – это наименьшее число вершин, удаление которых приводит к несвязному графу. Связность в графе с точкой сочленения равна 1. Связность в несвязном графе равна 0.

Взвешенный граф – это граф с весами на ребрах.

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

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

Длина маршрута определяется числом ребер, входящих в маршрут.

Если ребро соединяет две вершины графа, то говорят, что ребро инцидентно этим вершинам или вершины инцидентны данному ребру.

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

Локальная степень или просто степень вершины графа – это число ребер, инцидентных данной вершине. Локальная степень вершины x_i обозначается r (x_i) или r _i.

Маршрут в графе – это некоторая конечная последовательность ребер имеющая начальную и конечную вершину.

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

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

Множество вершин – это множество точек графа.

Множество ребер или дуг – множество линий, соединяющих любые пары вершин графа.

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

Неориентированный граф (неорграф) – граф, содержащий только подмножество ребер.

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

Нуль-граф – граф, у которого множество ребер является пустым, а все его вершины – изолированные.

Ориентированный граф (орграф) – это граф, содержащий только подмножество дуг.

Отношение связности являетсяотношением эквивалентности.

Перешеек (мост) в графе – это разрез, состоящий из одного ребра.

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

Подмножество дуг – подмножество ориентированных линий, для которых существен порядок соединения вершин. Каждая дуга определяется упорядоченной парой (кортежем длины два) вершин, которые она соединяет.

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

Подмножество ребер графа – подмножество неориентированных линий, для которых несуществен порядок соединения вершин. Каждое ребро определяется неупорядоченной парой вершин, которые оно соединяет.

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

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

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

Простой граф – это граф, не содержащий петель и кратных ребер.

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

Разрез графа – это такое разбиение графа на два подмножества, при котором во множестве ребер графа одни концевые вершины принадлежат первому подмножеству вершин, а другие – второму.

Реберная связность – это наименьшее число ребер, удаление которых приводит к несвязному или тривиальному графу.

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

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

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

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

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

Смешанный граф – это граф, содержащий подмножества ребер, дуг и петель.

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

Суграф – это часть графа, содержащая обязательно все вершины исходного графа, а также все либо часть его ребер.

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

Треугольник – цикл длины 3.

Цепь – это маршрут, в котором нет повторяющихся ребер.

Цикл – это замкнутая цепь, в которой первая и последняя вершины совпадают.

Циклический граф (цикл) – связный регулярный граф степени 2.

Глоссарий к главе 2

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

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

Дерево – связный граф без циклов. В дереве любые две вершины связаны единственной цепью. Любое дерево имеет n–1 ребро.

Диаметр графа – это максимальное расстояние между любыми двумя его вершинами.

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

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

Длина цепи – это число входящих в нее ребер.

Жорданова кривая – непрерывная кривая на плоскости, не имеющая самопересечений. Замкнутая жорданова кривая – это жорданова кривая, начало и конец которой совпадают.

Жордана теорема: Если L – замкнутая жорданова кривая, а x_i, x_j две различные точки, расположенные на ней, то любая жорданова кривая, соединяющая x_i и x_j, должна лежать целиком внутри L или вне L (за исключением точек x_i, x_j) или пересекать L в некоторой точке, отличной от точек x_i, x_j.

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

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

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

Корень – это начальная вершина, из которой выходят ребра – ветви дерева.

Кэли теорема: существует ровно n^n-2 различных помеченных деревьев с n вершинами.

Лес – множество деревьев графа.

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

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

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

Метрика графа основана на понятии расстояния.

Покрывающее или остовное дерево – дерево, число вершин которого равно числу вершин графа, из которого выделено это дерево. Число остовных деревьев в полном графе равно n^n-2.

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

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

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

Радиус графа – это максимальное удаление от центра графа.

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

Соседними называют вершины и ребра графа в случае, если они смежны и инцидентны.

Тотальный граф – граф, у которого множеством вершин является объединение множества вершин и множества ребер исходного графа, и две вершины считаются смежными тогда и только тогда, когда они являются соседними в исходном графе.

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

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

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

Глоссарий к главе 3

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

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

Гиперграф Н = (Х, Е) – это объект, который состоит из множества вершин X и множества ребер E, причем каждое ребро l_i Î E представляет собой некоторое подмножество множества вершин, т.е. l_i Í X.

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

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

Гиперграф H* называется двойственным гиперграфу H = (X, E), если, вершинами H* являются ребра H, а ребрами – вершины H.

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

Гиперграф Н= (X, Е) можно представить в виде двудольного графа Кёнига К(Н) = (X È E, V), где X – первое подмножество вершин двудольного графа, соответствующее множеству вершин гиперграфа H; Е – второе подмножество вершин двудольного графа, соответствующее множеству ребер гиперграфа H; V – множество ребер двудольного графа, устанавливающее смежность между двумя множествами вершин X и Е в графе К(Н) в соответствии с инцидентностью вершин и ребер гиперграфа H.

Гиперграф H = (Х, Е) считается деревом в случае, когда его ребра имеют не более одной общей вершины.

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

Максимальное внутренне устойчивое подмножество (МВУП) или независимое (НП) подмножество – это подмножество графа такое, что добавление к нему любой новой вершины делает его внутренне неустойчивым.

Максимально планарный граф – это граф, который при добавлении любого ребра перестает быть планарным.

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

Плоской картой называется связный плоский граф вместе со всеми его гранями.

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

Понтрягина - Куратовского теорема: граф планарен тогда и только тогда, когда он не содержит подграфа, гомеоморфного графам K₅ или K_3,3.

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

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

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

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

В гиперграфе H = (X, E) две вершины называются смежными в том случае, если существует ребро, содержащие эти вершины.

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

Толщина графа – наименьшее число планарных подграфов, объединение которых дает исходный граф.

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

Харари – Татта теорема: граф планарен тогда и только тогда, когда он не содержит подграфов, стягиваемых в K₅ или K_3,3.

Хроматическое число графа c (G) – наименьшее число подмножеств, на которое разбивается граф при раскраске.

В гиперграфе Н = (Х, Е) цепь длины q определяется как последовательность вида s(H) = x ₁, l ₁, х ₂, 1 ₂, …, l_q, x_{q +1}.

Цикломатическое число графа – это наименьшее число ребер, которые необходимо удалить из графа, чтобы он стал ациклическим (деревом). Цикломатическое число определяется по формуле: g(G) = m – n + k, где n – число вершин, m – число ребер, k – число компонент связности графа.

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

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

Число скрещиваний (пересечений) графа – наименьшее число пересечений ребер, которое получается при расположении графа на плоскости.

Ядро графа – это некоторое подмножество вершин графа, являющееся одновременно внутренне и внешне устойчивым.

 

 

Библиографический комментарий

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

Ф. Бэкон

Модуль 1.

Задачам теории множеств посвящена обширная библиография, привести которую авторы не считают необходимым. Авторы при написании данного учебного пособия использовали концепции построения и описания множеств, приведенные в книге Шихановича [1]. Энциклопедической монографией по части 1 является классический труд группы известных французских математиков под псевдонимом Бурбаки [2]. Она может быть использована для углубления знаний, полученных при изучении данного пособия.

Различным аспектам теории множеств посвящены книги [3 – 10]. Всевозможные операции над множествами и большое количество примеров приведено в книгах [1, 3, 8 - 10]. Более подробный материал по упорядоченным множествам и кортежам можно найти в книгах [1, 2, 8 - 13]. Сведения об отношениях в том или ином объеме включены в множество книг по теоретико-множественной тематике. Различные способы представления отношений описаны в книгах [1, 2, 8 - 11].

Наиболее полно вопросы представления соответствий и примеры представления и преобразования соответствий даны в монографии Шихановича [1]. Материал по бесконечным множествам наиболее удачно для студентов описан в книгах [1, 2, 12, 13, 23]. Понятие мультимножества является относительно новым и более полно описано в монографии Петровского [14].

Основателем теории нечетких множеств является Заде [15]. Для подробного изучения теории нечетких множеств рекомендуем следующую литературу [11, 16 - 20]. Различные разделы дискретной математики описаны на доступном языке в учебнике [21,22].

Вопросы посвященные приближенным множествам подробно описаны в книге [24].

Модуль 2.

Задачам теории алгоритмов посвящена обширная библиография. Авторы при написании данного учебного пособия использовали концепции классического учебника Кормен Т., Лейзерсон Ч., Ривест Р. «Алгоритмы: построение и анализ». Он является энциклопедической монографией по дискретной математике. Кроме того, этот учебник может быть использован для углубления знаний, полученных при изучении данного пособия [25], Авторы советуют также книги О.П. Кузнецова «Дискретная математика для инженеров» [7, 26], Сигорского В.П. «Математический аппарат инженера», а также методические разработки по теории алгоритмов авторов данного пособия [27,42-44].

Различным аспектам теории алгоритмов посвящены книги [28 – 31,35,45]. Всевозможные описания типов универсальных алгоритмических моделей приведены в учебном пособии Гладков Л.А., Курейчик В.В., Курейчик В.М. Основы теории алгоритмов [27]. Более подробный материал по нечетким моделям и алгоритмам можно найти в книгах [17-20,32].

Наиболее полно примеры и задачи с решениями приведены в книге Шапорева [33] и учебном пособии авторов [27].

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

В учебнике Дж. Макконелла [35] обсуждаются алгоритмы решения распространенных задач программирования: сортировки, сравнения с образцом, на графах, поиска и выборки и др.

Фундаментальный учебник Д.А. Андерсона [8] по дискретной математике подробно рассматривает вопросы логики, исчисления предикатов, алгоритмов и рекурсии. Особое внимание уделено теории доказательств. Книга содержит большое количество примеров и упражнений.

Сведения о комбинаторике в том или ином объеме включены в множество книг по дискретной математике.

 

Модуль 4.

В книге [34] приведены методы и средства дискретной математики как инструментарий при обработке информации на ЭВМ. Книга удобна для студентов, так как содержит обширный материал по решению задач, особенно в разделе по теории графов.

В книге [35] широко обсуждаются практические алгоритмы на графах. Книга будет особенно интересна студентам, так как содержит описание реальных программ для решения графовых задач.

Книга [8] – это современный классический учебник по дискретной математике. Особое внимание уделено теории доказательств. Материал сопровождается многочисленными примерами и упражнениями, особенно по теории графов.

Книгу [30] можно рассматривать как справочник по графовым и сортировочным алгоритмам. Для студентов интерес может представлять наличие программ.

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

В книге [48] представлено систематизированное введение в теорию графов с доказательствами теорем и примерами.

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

Книга [49] представляет интерес для студентов тем, что авторы показали связь общей теории сетей с прикладными задачами на графах различного вида.

В учебном пособии [50] с методической точки зрения излагается теория графов. Особый интерес для студентов представляет сведение прикладных практических задач к задачам теории графов.

Учебное пособие [51] ориентировано на студентов технических вузов с хорошей математической подготовкой.

Книга [24] ориентирована на инженеров в области информационных технологий. Особое внимание уделено оптимизационным задачам на графах, имеющим практическое применение.

В монографии [52] изложены фундаментальные основы ИКТ с применением теории графов. Интерес для студентов может представлять наличие программных кодов для решения основных графовых задач.

В книге [53] с математической точки зрения рассматривается решение важнейшей теоретической и практической задачи: «сколько существует графов». Интерес для студентов представляет обзор решенных и нерешенных задач, перечисления графов.

Книга [54] дает полное представление о направлениях исследований в теории графов, приводятся упражнения и нерешенные задачи.

В книге [55] приводится множество интересных приложений теории графов в различных областях науки и техники.

В учебном пособии [56] особое внимание уделено алгоритмическим методам теории графов.

Основное внимание в учебнике [57] уделено алгебраическим методам анализа графов, ориентированным на практические инженерные задачи.

Книгу [58] можно использовать как справочное руководство по современной теории графов.

В книге [59] описаны основы теории графов и ее применение к сетям в ЭВМ.

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

ЛИТЕРАТУРА

Книга – немой учитель

Платон

 

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

У. Оден

1. Шиханович Ю.А. Введение в дискретную математику. М.: Наука, 1965.

2. Бурбаки Н. Теория множеств. Под ред. В.А. Успенского. – М.: Мир, 1965.

3. Горбатов В.А. и др. Дискретная математика. Учебник для студентов ВТУЗов. – М.: ООО «Издательство АСТ», 2003.

4. Прикладная комбинаторная математика. Сб. статей под ред. Э. Беккенбаха. – М.: Мир, 1968.

5. Хаггарти Р. Дискретная математика для программистов. Учебное пособие. – М.: Техносфера, 2003.

6. Яблонский С.В. Введение в дискретную математику. Учебное пособие. – М.: Наука, 1979.

7. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988.

8. Андерсон Д. Дискретная математика и комбинаторика. – М.: Издательский дом «Вильямс», 2003.

9. Новиков Ф.А. Дискретная математика для программистов. М.: Из-дательский дом «Питер», 2000.

10. Стол Р. Множества. Логика. Аксиоматические теории. – М.: Просвещение, 1968.

11. Мелихов А.Н., Берштейн Л.С. Конечные четкие и расплывчатые множества. Ч. 1, 2. – Таганрог, ТРТУ, 1981.

12. Александров П.С. Введение в теорию множеств и общую топологию. – М.: Наука, 1977.

13. Куратовский К., Мостовский А. Теория множеств. – М.: Мир, 1970.

14. Петровский А.Б. Пространства множеств и мультимножеств. – М.: УРСС, 2003.

15. Заде Л. Понятие лингвистической переменной и его применение к принятию приближенных решений. – М.: Мир, 1976.

16. Борисов А.Н. и др. Обработка нечеткой информации в системах принятия решений. – М.: Радио и связь, 1989.

17. Ярушкина Н.Г. Основы теории нечетких и гибридных систем. Учебное пособие. – М.: Финансы и статистика, 2004.

18. Нечеткие множества и теория возможностей. Под ред. В.Б. Кузьмина. – М.: Радио и связь, 1986.

19. Рыжов А.П. Элементы теории нечетких множеств и измерения нечеткости. – М.: Диалог-МГУ, 1998.

20. Кофман А. Введение в теорию нечетких множеств. – М.:Радио и связь, 1982.

21. Спирина М.С., Спирин М.А. Дискретная математика. – М.: Издательский центр «Академия», 2004.

22. Микони С.В. Теория и практика рационального выбора. – М.: Изд-во «Маршрут», 2004.

23. Хаусдорф Ф. Теория множеств. – М.: КомКнига, 2006.

24. Вагин В.Н., Головина Е.Ю., Загорянская А.А., Фомина М.В. Достоверный и правдоподобный вывод в интеллектуальных системах. – М.: Физматлит, 2004.

25. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.- М.: Издательский дом «Вильямс», 2000.

26. Кузнецов О.П. Дискретная математика для инженера. – СПб: Лань, 2004.

27. Гладков Л.А., Курейчик В.В., Курейчик В.М. Основы теории алгоритмов. Учебное пособие. – Таганрог: изд-во ТРТУ, 2003.

28. Ерусалимский Я.М. Дискретная математика: Теория, задачи, приложения. – М.: Вузовская книга, 2002.

29. Судоплатов С.В., Овчинникова Е.В. Дискретная математика: Учебник. – М.: ИНФРА-М, 2005.

30. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. Учебное пособие. – М.: Лаборатория базовых знаний, 2001.

31. Плотников А.Д. Дискретная математика: Учебное пособие. – М.: Новое знание, 2005.

32. Берштейн Л.С., Боженюк А.В. Нечеткие модели принятия решений: дедукция, индукция, аналогия: Монография. – Таганрог: Изд-во ТРТУ, 2001.

33. Шапорев С.Д. Дискретная математика: Курс лекций и практических занятий. – СПб.: БХВ-Петербург, 2006.

34. Капитонова Ю.В. и др. Лекции по дискретной математике. – СПб.: БХВ – Петербург, 2004.

35. Макконелл Дж. Анализ алгоритмов: Краткий курс. – М.: Техносфера, 2002.

36. Непейвода Н.Н. Прикладная логика. – Новосибирск: Изд-во Новосибирского университета, 2000.

37. Клини С.К. Математическая логика. – М.: Мир, 1973.

38. Ершов Ю.Л., Палютин Е.А. Математическая логика. – М.: Наука, 1979.

39. Гиндикин С.Г. Алгебра логики в задачах. – М.: Наука, 1972.

40. Судоплатов С.В., Овчинникова Е.В. Дискретная математика: Учебник. – М.: ИНФРА-М, 2005.

41. Акимов О.Е. Дискретная математика: логика, группы, графы, фракталы. – М.: Издатель АКИМОВА, 2005.

42. Сигорский В.П. Математический аппарат инженера – Киев: Техника, 1997.

43. Курейчик В.М. Учебное пособие по дискретной математике. Часть 1. – Таганрог: Изд-во ТРТУ, 1997.

44. Курейчик В.М., Гладков Л.А., Лисяк Н.К., Курейчик В.В. Учебное пособие для практических и лекционных занятий по курсу «Математические основы дискретной техники». Часть 1. – Таганрог: Изд-во ТРТУ, 1997.

45. Панадимитриу Х., Стайниц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир,1983.

46. Довгий П.С., Поляков В.И. Синтез комбинационных схем. – СПб.: Изд-во ИТМО, 2006.

47. Редькин Н.П. Дискретная математика: Курс лекций для студентов-механиков. – СПб.: Издательство «Лань», 2003.

48. Зыков А.А. Основы теории графов. – М.: Вузовская книга, 2004.

49. Френк Г., Фриш И. Сети, связи и потоки. – М.: Связь, 1978.

50. Емеличев В.А. и др. Лекции по теории графов: Учеб. пос. – М.: Книжный дом «ЛИБРОКОМ», 2009.

51. Белов В.В. и др. Теория графов: Учеб. пос. для ВТУЗов. – М.: Высшая школа, 1976.

52. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. – СПб.: БХВ – Петербург, 2003.

53. Харари Ф., Палмер Э. Перечисление графов. – М.: Мир, 1977.

54. Оре О. Теория графов. – М.: Книжный дом «ЛИБРОКОМ»/URSS, 2009.

55. Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1973.

56. Асеев Г.Г., Абрамов О.М., Ситников Д.Э. Дискретная математика: Учеб. пос. – Ростов-на-Дону: Феникс, 2003.

57. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учеб. пос. для вузов. – М.: изд-во МГТУ им. Баумана, 2004.

58. Татт У. Теория графов. – М.: Мир, 1988.

59. Евами М., Тхуласкрами К. Графы, сети и алгоритмы. – М.: Мир, 1984.

60. Абондо-Бодино Д. Применение в экономике теории графов. – М: Прогресс, 1966.

61. Берштейн Л.С., Боженюк А.В. Введение в теорию нечетких графов. – Таганрог: Изд-во ТРТУ, 1995.

62. Галкина В.А. Дискретная математика: комбинаторные методы оптимизации. – М.: Гелиос АРВ, 2003.

63. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982.

64. Кирсанов М.Н. Графы в MAPLE. Задачи, алгоритмы, программы. – М.: Физматлит, 2007.

65. Костюкова Н.И. Графы и их применение. Комбинаторные алгоритмы для программистов: Учеб. пос. – М.: Интернет-университет информационных технологий; БИНОМ, Лаборатория знаний, 2007.

66. Кофман А. Введение в прикладную комбинаторику. – М.: Наука, 1975.

67. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978.

68. Курейчик В.М. Математическое обеспечение КТП с применением САПР. – М.: Радио и связь, 1990.

69. Курейчик В.М. Дискретная математика: Учеб. пос. Ч. 2. Элементы теории графов. – Таганрог: Изд-во ТРТУ, 1998.

70. Курейчик В.М., Гладков Л.А., Лисяк Н.К., Курейчик В.В. Учебное пособие для практических и лекционных занятий по курсу «Математические основы дискретной техники». Ч. 2. – Таганрог: Изд-во ТРТУ, 1998.

71. Мелихов А.Н., Берштейн Л.С., Курейчик В. М. Применение графов для проектирования дискретных устройств. - М.: Наука, 1974.

72. Мелихов А.Н., Карелин В.П. Методы распознавания изоморфизма и изоморфного вложения четких и нечетких графов. – Таганрог: Изд-во ТРТУ, 1995.

73. Микони С.В. Элементы дискретной математики. – СПб.: Изд-во ПГУПС, 1999.

74. Палий И.А. Дискретная математика: Курс лекций. – М.: ЭКСМО, 2008.

75. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.

 

В любой науке столько истины, сколько в ней математики.

И. Кант

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

 

 

ПРИЛОЖЕНИЕ 1

оСНОВНЫЕ ПОЛОЖЕНИЯ гост 19.701-90 (исо 5807-85) «сХЕМЫ АЛГОРИТМОВ, ПРОГРАММ, ДАННЫХ И СИСТЕМ. уСЛОВНЫЕ ОБОЗНАЧЕНИЯ И ПРАВИЛА ВЫПОЛНЕНИЯ»

1. Введение

Схема программы отображает последовательность операций в программе и состоит:

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

2) линейных символов, указывающих поток управления;

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

2. Символы

2.1. Процесс

Символ отображает функцию обработки данных любого вида.

2.2. Предопределенный процесс

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

2.3. Ручная операция

Символ отображает любой процесс, выполняемый человеком.

2.4. Подготовка

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

2.5. Решение

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

2.6. Линия

Символ отображает поток данных или управления.

2.7. Соединитель

Символ используется для обрыва ЛИНИИ и продолжения ее в другом месте. Соответствующие символы-соединители должны содержать одно и тоже уникальное обозначение.

2.8. Терминатор

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

 

 

2.9. Комментарий

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

3. Правила применения символов

3.1. Символ предназначен для графической идентификации функции, которую он обозначает, независимо от текста внутри этого символа.

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

3.3. Текст для чтения должен записываться слева направо и сверху вниз независимо от направления потока. Если объем текста, помещаемого внутри символа, превышает его размеры, следует использовать символ комментария.

 

4. Правила выполнения соединений

4.1. Направление потока слева направо и сверху вниз считается стандартным.

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

4.3. Линии в схемах должны подходить к символу либо слева, либо сверху, а исходить либо справа, либо снизу. Линии должны быть направлены к центру символа.

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

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

5. Специальные условные обозначения

Несколько выходов из символа следует показывать:

1) несколькими линиями от данного символа к другим символам;

2) одной линией от данного символа, которая затем разветвляется в соответствующее число линий.

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

 

ДЛЯ ЗАМЕТОК

 

 

Учебное издание