Дискретная математика

 

СОДЕРЖАНИЕ

 

1. ВВЕДЕНИЕ
2. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
3. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ
4. МАТРИЦА СМЕЖНОСТИ
5. МАТРИЦА ИНЦИДЕНТНОСТИ
6. МАТРИЦА ИНЦИДЕНТНОСТИ ПРИМЕНЯЕТСЯ ПРИ АНАЛИЗЕ РЕШЕНИЙ
7. БИБЛИОГРАФИЯ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение:

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

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

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

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

Разделы Дискретной математики:

1. Математическая логика
2. Математическая кибернетика
3. Теория функциональных систем
4. Общая алгебра
5. Комбинаторика
6. Комбинаторная логика
7. Сортировки
8. Теория графов
9. Машинная арифметика
10. Теория алгоритмов
11. Теория игр
12. Теория кодирования
13. Теория автоматов
14. Теория множеств (отдельные разделы)
15. Теория чисел (отдельные разделы)
16. Теория формальных грамматик
17. Вычислительная геометрия
18. Теория булевых функций
19. Логическое программирование
20. Функциональное программирование
21. Булева алгебра
22. Комбинационная логика
23. Секвенциальная логика
24. Асинхронная логика
25. Математическая лингвистика
26. Теория искусственного интеллекта
27. Теория расписаний

 

Рассмотрим один из разделов Дискретной математики, теорию графов:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Элементы теории графов.

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Основные понятия  теории графов

 

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

Х- обозначается кружками

U- обозначается линиями со стрелками(дугами) и линиями без стрелок (ребрами).

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

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

Началом теории графов считают 1736 год, когда Л.Эйлер решил задачу о «задачу о кенигсбергских мостах». Однако термин «Граф» впервые был введен только в 1936 году Д. Кенигом, то есть спустя 200 лет.

Определение графа: задано конечное множество  Х, состоящие из n элементов (Х₁,Х₂,Х₃, …, X_n) называемых вершинами графа,и подмножество V Декартова произведения Х*Х, то есть V X², называемое множеством дуг, тогда ориентированным графом G называется совокупность (X,V), неориентированным графом называется совокупность множества Х и множества неупорядоченных пар элементов каждый из которых принадлежит множеству Х.

Дугу между вершинами  I и j, I,j ∈ X будем обозначать  (I,j). Число дуг графа будем обозначать   m (V = (v1, v2, ..., vт)).

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

1. «Транспортные» задачи, в которых вершинами графа являются пункты, а ребрами - дороги (автомобильные, железные и др.) и/или другие транспортные (например, авиационные) маршруты.
2. «Сети снабжения» (электроснабжения, газоснабжения и т.д.), в которых вершинами являются пункты производства и потребления, а ребрами – возможные маршруты перемещения (газопроводы, дороги, линии электропередач).
3. Задачами «обеспечения(размещения)»  называют оптимизацию потоков грузов, размещению пунктов производства и потребления.
4. «Технологические» задачи, в которых вершины отображают производственные элементы (заводы, цеха, станки), а дуги – потоки сырья, материалов и продукции между ними,  заключаются в определении оптимальной загрузки производственных элементов и обеспечивающих эту загрузку потоков.

 

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

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

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

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

 

Например, у графа па рис. 3 имеется 3 пути из V₁ в V₅: V₁,V₂,V₄,V₅; V_1,V₃,V₂,V₄,V₅; V₁,V₃,V₄,V₅. Длина первого равна 2+1+5=8, длина второго  3+4+1+5=13, третьего 3+3+5=11. Таким образом, первый из рассмотренных путей имеет наименьшую длину, т.е. является наикратчайшим из V₁ в V₅.

Граф, для которого (I,j) V следует (I,j) V называется симметрическим. Если из (I,j) V следует, что (I,j) V, то соответствующий граф называется антисимметрическим.

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

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

 

 

 

Рис. 1                                                                                                               Рис. 3

                                                              Рис. 2

 

 

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

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

В неориентированном графе степенью вершины i называется число d_i инцидентных ей ребер. Очевидно, d_j < n - i, iX. Граф, степени всех вершин которого равны n - 1, называется полным графом. Граф, все степени вершин которого равны, называется однородным графом.

Вершина, для которой не существует инцидентных ей ребер (d_i=0) называется изолированной вершиной. Вершина, для которой существует только одно инцидентное ей ребро (d_i=1), называется висячей вершиной.

 

∑ d_i = 2m

 

Деревом называется связный граф без простых циклов, имеющий не менее двух вершин. Для дерева m=n-1, а число висячих вершин равно

n_i =2+∑ (i-2) n_i. Легко показать, что в дереве любые две вершины связаны единственной цепью. Во многих задачах, связанных с графами, бывает полезно представление графа в виде таблицы, или матрицы.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Матрица смежности

 

Матрица смежности представляет собой квадратную таблицу, у которой n строк и n столбцов, где n - число вершин графа.

Построение матрицы смежности  следует рассмотреть на примерах. Построим матрицу смежности для  ориентированного графа (рис.4).

Сначала запишем в строку и в столбец номера вершин данного  графа

 

 

 

 

Рис. 4

Строка	Столбцы
	1	2	3	4
1	0	1	1	0
2	0	0	1	2
3	0	0	0	1
4	1	0	0	0

 

Если из вершины V_i в вершину V_j идет k дуг, то в таблице на пересечении строки с номером I и столбца с номером j стоит число k, в противном случае 0.

Например, для рассматриваемого графа из V₁ в V₂ идет одна дуга, поэтому на пересечении первой строки и второго столбца стоит 1; а поскольку из V₂ в V₁ нет дуги, то на пересечении второй строки и первого столбца стоит 0. Из V₂ в V₄ идут две дуги, поэтому на пересечении второй строки и четвертого столбца ставится 2. Полученную матрицу обозначим через А:

 

0  1  1  0

0  0  1  2

А= 0  0  0  1

0  0  0  1

 

В матрице смежности неориентированного графа на пересечении строки с  номером i и столбца с номером j стоит число k, если вершины V_i и V_J соединены k ребрами, в противном случае стоит 0. Так для графа на рис.5 матрица смежности задается матрицей В:

                                                            

                             V₁                                            V₂

 

                                                  V₃

                                                                V₄               V₅

                                      

                                        Рис. 5

 

  

0  1  0  0  0

1  0  1  1  1

                           B= 0  1  0  0  0

0  1  0  0  0

                                        0  1  0  0  0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Матрица инцидентности.

Матрица инцидентности (инциденций) представляет собой таблицу, у которой число строк равно числу вершин, а число столбцов - числу дуг (ребер) графа.

Пусть граф ориентирован. Тогда  на пересечении строки с номером  i и столбца с номером j стоит:

1, если вершина V_i является концом дуги U_j;

1, если вершина V_i является началом дуги U_j;

0 - в противном случае.

Например, для графа на рис.6  матрицей инцидентности является матрица С:

 

 

 

                                          V                                    V

                                                          U    U

                                           U                                  U

                                            V                                V

                                                               U