Фрагмент для ознакомления
2
В самом начале работы над исходным графом необходимо дать определение самого этого понятия.
Согласно [3] «Граф» - это объединение множеств вершин (узлов) N и ребер Х : пара множеств – G=[N,X], где каждое ребро соединяет две вершины.
Ориентированный граф G = [N, M] определяется как пара (N, M),
где N — конечное множество вершин, а M — множество дуг, представляющих собой упорядоченные ребра (бинарное отношение на N, т. е.
подмножество множества NхN). Ориентированный граф для краткости
называют орграфом.
Множество N называют множеством вершин графа. Вершина графа, не имеющая ни одного прообраза, называется истоком (источником). Вершина, не имеющая ни одного образа, называется стоком.
Множество M называют множеством ребер графа.. Вершины изображены кружками, а ребра в ориентированном графе — стрелками. Граф
может содержать ребра-петли, соединяющие вершину саму с собой.
В неориентированном графе G = (N, M) множество ребер M состоит
из неупорядоченных пар вершин. Парами являются множества {n, m},
где n, m ∈ N и m ∈ М, а n≠ m. Неориентированное ребро обозначается
как (n, m); при этом для неориентированного графа (n, m) и (m, n) обозначают одно и то же ребро. Неориентированный граф не может содержать ребер-петель, и каждое ребро состоит из двух различных вершин
(«соединяя» их).
Если в графе G имеется ребро (n, m), говорят, что вершина n смежна с вершиной m. Для неориентированных графов отношение смежности является симметричным, но для ориентированных графов это
не обязательно. Если вершина n смежна с вершиной m в ориентирован-
ном графе, то пишут m → n.
Степенью вершины в неориентированном графе называется число
инцидентных ей ребер. Для ориентированного графа различают исходящую степень, определяемую как число выходящих из нее ребер, и входящую степень, определяемую как число входящих в нее ребер. Сумма исходящей и входящей степеней называется степенью вершины.
Маршрутом в графе G называется чередующаяся последовательность вершин и ребер. Эта последовательность начинается и кончается
вершиной. Каждое ребро маршрута инцидентно двум вершинам, одна из которых непосредственно предшествует ему, а другая непосредственно
следует за ним. Маршрут замкнут, если одна и та же вершина является
его началом и концом. В противном случае маршрут называется от-
крытым. Маршрут называется путем, если все вершины (а следовательно, и ребра) различны. Цепь, в отличие от пути, может включать циклические структуры.
Замкнутый маршрут называется циклом, если в нем все вершины,
кроме начальной, различны.
Циклом в ориентированном графе называется путь, в котором начальная вершина совпадает с конечной и который содержит хотя бы одно ребро.
Граф называется связным, если между любой парой его вершин
существует путь. В противном случае граф называется несвязным. Не-
ориентированный граф называется связным, если для любой пары вер-
шин существует путь из одной в другую. Ориентированный граф называется сильно связным, если из любой его вершины достижима (по ориентированным путям) любая другая.
Полным называется граф, в котором между любой парой вершин
существует ребро. Полный граф будет связным.
Иерархическая структура в графе называется деревом. Дерево —
это связный ациклический граф.
Характерные особенности деревьев:
1) Число дуг в дереве на единицу меньше числа узлов.
2) В ориентированном связывающем дереве в каждый узел входит
одна дуга, за исключением корневого узла.
3) Из каждого узла может выходить любое количество дуг.
4) Любые две вершины в дереве связаны единственным путем.
Также перед построением исходного графа необходимо дать описание алгоритма Дейкстры, используя который, мы будем проводить все дальнейшие вычисления.
Оптимизационный инструментарий определения кратчайшего пути применяется в производственной и транспортной логистике. Также на основе алгоритма Дейкстры можно разрабатывать технологические имитационные модели.
На первом этапе нам необходимо выбрать на маршруте узлы, составить их список, который в свою очередь оформить в виде таблицы.
Исходная сеть представлена в виде чертежа в графической части работы (Приложение, рис.1).
Показать больше
