Основные понятия. Графы – это математическая модель, с помощью которой можно представлять и исследовать формальное описание систем и процессов

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

При этом природа зависимостей компонент систем может быть произвольной для конкретных систем в разных областях деятельности.

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

1. Транспортные сети. Компонентами таких систем являются отдельные населенные пункты или строения, а связями - указание на наличие дорог, которые их соединяют.

2. Молекулы химических соединений. Частями таких систем являются отдельные атомы, составляющие молекулы, а связями - химические соединения между атомами.

3. Электронные схемы. В качестве компонентов, в них входят функциональные узлы или элементы, а связи указывают на наличие проводов, соединяющих узлы друг с другом.

4. Административный аппарат учреждения. Здесь частями являются отдельные должностные лица, а связи указывают на наличие должностной подчиненности между сотрудниками учреждения.

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

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

Изображение системы, для которой выполнены перечисленные условия, называется геометрической реализацией этой системы.

Пример. Возможна следующая система подчиненности по службе сотрудников аппарата управления некоторой фирмы (рис.5.1.):

Директор

Главный Начальник Референт

менеджер отдела по правовым

маркетинга вопросам

Менеджер Менеджер

Рис. 5.1.