Графовая модель

Графовая модель (или граф) - это множество вершин графа (элементов) и множество ребер графа, т.е. соответствий, отношений между этими элементами.

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

Началом теории графов считается 1736 год, когда вышла в свет статья Эйлера с его знаменитыми рассуждениями о Кенигсбергских мостах. Затем около 100 лет эта статья оставалась единственной, а методы теории графов невостребованными практикой. Интерес к графам появился только в середине 19 века благодаря исследованиям электрических сетей, моделей кристаллов и структур молекул. С тех пор сфера применений теории графов непрерывно расширялась и сегодня она представляет собой мощную формальную систему, имеющую необозримое множество областей практического применения.

(Задача Эйлера: в Кенигсберге течет река Неман. Она омывает два острова. Между берегами реки и островами во времена проживания в Кенигсберге Эйлера существовали 7 мостов, расположение которых показывает рисунок 1. Задача Эйлера состояла в том, чтобы определить, можно ли выйдя из пункта С (или любого другого пункта) пройти каждый мост только по одному разу и вернуться в исходный пункт. Рассуждения и действия Эйлера в ходе решения этой задачи можно представить последовательностью следующих шагов: 1) он нарисовал план, 2) нарисовал неориентированный граф, ассоциированный с берегами, островами и мостами, 3) абстрагировал ассоциированный с данными граф от его содержания (см. рис. 1); это решающий шаг рассуждений Эйлера, поскольку абстрактный граф можно ассоциировать с чем угодно, например с площадями и улицами между ними, 4) граф должен быть связным и каждая его вершина должна быть инцидентна чётному числу рёбер.)

Рис.1 – Задача Эйлера

В отличии от произвольно нарисованной схемы графовая модель строится по определенным правилам. При изображении графов чаще всего используется следующая система обозначений: каждой вершине сопоставляется точка на плоскости, и если между вершинами существует ребро, то соответствующие точки соединяются отрезком. В случае ориентированного графа отрезки заменяют стрелками. Не следует путать изображение графа с собственно графом (абстрактной структурой), поскольку одному графу можно сопоставить не одно графическое представление. Изображение призвано лишь показать, какие пары вершин соединены рёбрами, а какие — нет. Часто на практике бывает трудно ответить на вопрос, являются ли два изображения моделями одного и того же графа или нет. В зависимости от задачи, одни изображения могут давать более наглядную картину, чем другие.

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

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

Графовые математические модели стали эффективным средством формализации задач из самых различных областей: экономики, физики, химии, планово-производственной практики, управления производством, сетевого и календарного планирования, информационных систем, и многих других. Эффективные алгоритмы, разработанные для решения задач о кратчайших путях, максимальных потоках в сетях, задач о случайных блужданиях стали мощным инструментом решения различных задач маршрутизации, анализа и расчета электрических сетей. Все более активно графовые математические модели применяются для анализа и синтеза коммуникационных сетей и навигации в них. Маршрутизация в Интернете осуществляется с помощью эффективного графового алгоритма нахождения кратчайшего пути между заданными узлами этой глобальной сети. Широкая применимость графовых методов и математических моделей, основанных на использовании ориентированных взвешенных графов привела к формированию класса алгоритмов, который сегодня имеет свое собственное название «Алгоритмы на графах».

Области применения графовых моделей:

• В химии (для описания структур, путей сложных реакций); компьютерная химия — сравнительно молодая область химии, основанная на применении теории графов. Теория графов представляет собой математическую основу хемоинформатики. Теория графов позволяет точно определить число теоретически возможных изомеров у углеводородов и других органических соединений.
• В информатике и программировании (граф-схема алгоритма)
• В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете.
• В экономике
• В логистике
• В схемотехнике (топология межсоединений элементов на печатной плате или микросхеме представляет собой граф или гиперграф)

Конкретные примеры применения:

• Блок-схема
• Карта улиц города
• Схема метро
• Родословная (фамильное дерево)
• Топология компьютерной сети
• PERT-диаграмма (план работы над проектом)