Математические основы моделей на графах
Граф представляет собой совокупность вершин, связанных линиями. Вершины могут обозначаться овалами, прямоугольниками, точками и т.п.
Рисунок 1. Пример графа. Автор24 — интернет-биржа студенческих работ
Направленная линия (со стрелкой) называется дугой, ненаправленная - ребром графа. Линия, выходящая из некоторой вершины и возвращающаяся в нее же, называется петлей.
Граф, вершины которого соединены ребрами, называется неориентированным. Цепью называется маршрут, проложенный по вершинам и ребрам графа и включающий каждое ребро не более одного раза. Циклом называется цепь, у которой начальная и конечная вершины совпадают.
Ориентированным называется граф, вершины которого соединены дугами. Взвешенным, - если его вершины, ребра или дуги характеризуются весом (дополнительной количественной информацией).
Выделяют также графы, в которых все связи между вершинами уникальны или специфичны. Такие модели называются семантическими сетями. В форме семантических сетей, где есть объекты (понятия) и связи (отношения) между ними, можно представить любую информацию.
Древовидные графы
Частным случаем моделей-графов являются иерархические (древовидные) структуры.
Иерархией называется расположение элементов целого в порядке от высшего к низшему. Отсчет ведется от единого элемента, называемого корневым.
Для систем, описываемых такими структурами, характерны такие отношения, как «является разновидностью», «входит в состав» и другие выражения подчиненности.
Примером иерархической структуры может служить любое коммерческое предприятие, где установлены отношения подчиненности "директор — заместители", "заместители - начальники отделов", "начальники отделов - исполнители".
Граф иерархической системы называют также деревом. Его отличительной особенностью является то, что между любыми двумя вершинами такого графа существует единственный путь, т.е. он не содержит циклов и петель.
Вершины древовидного графа состоят друг с другом в отношениях «предок - потомок». Любая вершина дерева (кроме корня) имеет только одного предка, т.е. объект, входящий в один из классов верхнего уровня. Любая вершина древовидного графа может указывать на несколько потомков. Этот принцип отношений называется «один ко многим». Вершины, не имеющие вершин-потомков, называются листьями.
Иерархию легко изобразить в форме «лестницы», т.е. многоуровневого списка. Чем дальше от корня уровень иерархии, тем правее находится соответствующий уровень списка. В качестве примера можно привести зоологическую классификацию:
Рисунок 2. Классификация биологических видов. Автор24 — интернет-биржа студенческих работ
Связи между членами семьи также удобно изображать с помощью древовидной схемы. Такой граф называется родословным деревом.
По иерархическому принципу построена и система хранения файлов на жестком диске компьютера, где файлы распределены по папкам (каталогам, директориям). Папки, в свою очередь, принадлежат другим папкам и т.д. Корневая вершина этой иерархии в среде Windows называется "Мой компьютер". Ей принадлежат локальные диски и сетевые ресурсы (второй уровень иерархии). Папки начинаются с третьего уровня. Дальнейшая степень вложенности (количество уровней иерархии) ограничена достаточно большим числом, пригодным для большинства практических задач.
Рисунок 3. Иерархия папок в среде Windows. Автор24 — интернет-биржа студенческих работ
Пути к файлам записывают особым образом. Уровни иерархии разделяются спецсимволами «\» (в среде Windows), «/» (в среде Unix) или «:» (в среде MacOS), например (для Windows):
./Современные языки программирования/Most-popular-programming-languages.png
./Современные языки программирования/README.md
./Современные языки программирования/800px-Цифровой_код_ЭВМ_«Минск-22».jpg
./Современные языки программирования/shot00.png
./Электронная почта/virus.png
./Электронная почта/README.md
./Электронная почта/письмо.png
./Электронная почта/доставка электронной почты.png
./Создание web-страниц, введение в стандарты HTML и PHP/code-2.png
./Создание web-страниц, введение в стандарты HTML и PHP/web-server.jpg
./Создание web-страниц, введение в стандарты HTML и PHP/README.md
./Создание web-страниц, введение в стандарты HTML и PHP/code-3.png
./Создание web-страниц, введение в стандарты HTML и PHP/code-1.png
./Создание web-страниц, введение в стандарты HTML и PHP/html example.png
./Информационные системы и технологии/README.md
./Информационные системы и технологии/vuz-information-system_1.jpg
./Информационные системы и технологии/каталоги.jpg
./Информационные системы и технологии/рынок it.png
Задача обхода вершин графа
С моделями-графами связана задача обхода его вершин, которая решается при проектировании реальных систем. Например, часто требуется найти кратчайший проезжий путь на местности. Такую задачу можно описать в виде графа, где вершинами буду населенные пункты, а ребрами - связывающие их дороги.
Существует множество способов решения таких задач и готовых компьютерных алгоритмов. В общем случае для каждой не пройденной вершины находят все не пройденные смежные вершины и повторяют поиск для них. Пройденные вершины запоминаются и последовательно исключаются из обработки. Пошаговое представление выглядит так:
- выбирается любая вершина из не пройденных (обозначим ее как u);
- запускается функция поиска find(u);
- вершина u помечается как пройденная.
Для каждой не пройденной вершины, смежной с u (обозначим ее v) запускается find(v), затем повторяются шаги 1 и 2, пока все вершины не будут обработаны.
Пример реализации:
// функция принимает граф G
// с количеством вершин n
// и выполняет обход в глубину во всем графе.
function findAll(G[n]: Graph):
// создаём массив посещённых вершины
// длины n, заполненный false изначально
visited = array[n, false]
function find(u: int):
visited[u] = true
for v: (u, v) in G
if not visited[v]
find(v)
for i = 1 to n
if not visited[i]
find(i)
Обход графа - пример рекурсии, когда функция многократно вызывается изнутри себя самой.
