- •1. Основные понятия и принципы исследования операций
- •2. Типичные задачи исследования операций
- •3. Понятие модели и моделирования
- •4. Виды моделирования. Различные модели исследования операций
- •5. Основная задача линейного программирования.
- •7. Задача о снабжении сырьем
- •8. Сведение произвольной задачи линейного программирования к основной
- •9.Использование электронных таблиц при решении задач линейной оптимизации.
- •10.Графическое решение задач линейного программирования
- •11.Ключевая идея дп. Принцип оптимальности Беллмана.
- •12. Решение задачи о распределении ресурсов методами динамического программирования
- •13.Моделирование случайных чисел.
- •14. Вычисление определенного интеграла методом Монте-Карло
- •15. Нахождение площади геометрической фигуры методом Монте-Карло
- •16. Основные понятия и определения теории графов
- •17. Способы задания графа. Матрицы смежностей и инциденций.
- •18. Графы типа дерево. Остовное дерево. Минимальное остовное дерево
- •19. Задачи оптимизации на графах. Алгоритм Краскала построения минимального остовного дерева
- •20. Сетевое планирование: основная идея и модели решаемых задач
- •21. Моделирование систем массового обслуживания
- •22.Моделирование смо: каналы ,очереди, дисциплины обслуживания.
16. Основные понятия и определения теории графов
Теория
графов
- это область дискретной математики,
особенностью которой является
геометрический подход к изучению
объектов. Теория графов находится сейчас
в самом расцвете. Графом
G
называют пару множеств (V, E), где V –
множество вершин
графа (точек); E – семейство ребер
графа (отрезков или дуг, соединяющих
вершины в пары):
V={v1,v2,v3,…,vn};E={e1,e2,e3,…,em};Пример
графа:
То
есть, элементы множества V называются
вершинами графа. Элементы множества E
ребрами графа. Ребра вида (v,v), в которых
первый элемент и второй совпадают,
называются петлями.
Или, если концевые вершины ребра
совпадают, то ребро образует петлю
(дугу, начало и конец которой совпадают).
Если пара (v1,v2)
E
− ребро, то v1
и v2
называются концами
этого ребра. В этом случае вершины v1
и v2
называются смежными
в графе, а само ребро (v1,
v2)
называется инцидентным
вершинам
v1
и v2.
Пусть в графе есть ребро (v1,v2), тогда можно считать, что в нем есть ребро (v2,v1). Если при этом указанные ребра не различать (т. е. (v1,v2)= (v2,v1), пары считаются неупорядоченными), то граф называется неориентированным графом. Если в графе есть несколько одинаковых ребер вида (v1,v2) , то такое ребро называют кратным.
Графы можно изображать графически. Вершины изображаются точками, ребра изображаются линиями соединяющие соответствующие вершины. Число вершин графа называют порядком графа и обозначают V= n. Граф будем обозначать парой G = (V, E).
Граф
G называется помеченным, если его вершинам
приписаны числа 1,
2, …, п,
где п
−
порядок графа. Граф можно задать с
помощью матрицы размера n
x n:
А(G)=[aij],
где
эта матрица симметрична с нулями по
главной диагонали. Она
называется матрицей смежностей графа G = (V, E). Ребра графа могут быть ориентированными или неориентированными. При изучении бинарных отношений были использованы графы, все ребра которых ориентированы. Такие графы называют ориентированными графами или орграфами. Если вершины vi и vj (i≠j) соединены ребром ek= (vi,vj), то их называют смежными вершинами. Если ребра ek, el имеют общую вершину, то их называют смежными ребрами. Если вершина vi является концом ребра ej, то vi называют вершиной, инцидентной ребру ej, а ej– ребром, инцидентным вершине vi.
Степенью вершины графа называется число инцидентных ей ребер, (число вершин смежных этой вершине, число ребер выходящих из этой вершины, число ребер входящих в нее). Обозначают степень вершины v через deg (v).
Вершина называется изолированной, если еѐ степень равна нулю, и называется концевой (висячей), если еѐ степень равна единице. Вершина называется доминирующей, если она смежная со всеми вершинами графа. Сумма степеней всех вершин графа есть четное число.
в любом графе число вершин с нечетными степенями четно.
17. Способы задания графа. Матрицы смежностей и инциденций.
Фиксируем
на плоскости произвольным образом п
точек и
произвольным образом дадим им в качестве
имен имена вершин данного графа. В итоге
на плоскости возникнут точки, обозначенные
как
.
Затем для каждой пары точек
таких, что
,
проведем отрезок прямой, соединяющий
точки
.
В результате таких действий возникнет
некоторый рисунок, который и называется
геометрической интерпретацией графа.
Заметим, что одному и тому же графу
соответствует много рисунков, которые
могут быть его геометрическими
интерпретациями. Вот два рисунка, каждый
из которых является геометрической
интерпретацией графа, приведенного
выше в качестве примера:
Число вершин графа называют порядком графа и обозначают /V/= n. Граф будем обозначать парой G = (V, E). Граф G называется помеченным, если его вершинам приписаны числа 1, 2, …, n, где n − порядок графа.
В приведенном выше примере графа матрица смежностей такова:
В
каждом столбце матрицы инциденций
всегда ровно две единицы, остальные
элементы равны нулю. Если в графе все
вершины имеют степень ноль, то матрицы
инциденций - нулевая.
Во многих задачах, решаемых с использованием графов, требуется проложить маршрут от одной вершины графа к другой или обойти все его вершины, учитывая те или иные ограничения.
Маршрут – это последовательность вершин и ребер графа, следуя по которым, можно попасть из одной его вершины в другую.
Цепь – это маршрут без повторяющихся ребер.
Путь – это цепь, все вершины которой (за исключением, быть может, начальной и конечной) различны.
Цикл – это цепь, у которой совпадают начальная и конечная вершины, а все остальные различны
Граф называют связным, если из каждой его вершины существует путь в любую другую его вершину. Граф, рассмотренный в примере, является, связным. Если удалить из него ребро , то он потеряет связность и распадется на компоненты: одна из компонент будет содержать вершину Д и петлю , вторая компонента – вершины А,В,С,Е, связанные между собой всеми оставшимися ребрами.
Для представления данных в алгоритмах на дискретных структурах часто используются графы, которые называются деревьями. Деревом называют связный неор граф, не содержащий циклов.
Если граф связный, но не является деревом, в нем всегда можно выделить часть, включающую все вершины и образующую дерево. Такую часть графа называют остовом графа. Если граф несвязен, то можно превратить в дерево каждую его компоненту. Полученная совокупность деревьев носит название остовного леса.
Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.
