Приложения теории графов в теории систем

Вводные замечания. Неориентированные графы. Маршрут, путь, цепь, цикл. Изоморфизм графов и инварианты. Деревья, двудольные графы, разделяющие множества и разрезы. Ориентированные графы. Отношения на графах Теоретико-множественное представление графов. Матричное представление графов. Порядковая функция на графе. Прикладные задачи теории графов.

ВВОДНЫЕ ЗАМЕЧАНИЯ

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

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

Рис. 5.1. Графические схемы описания раничных систем

На таких диаграммах ни способ изображения элементов, ни форма или длина линий не имеют значения — важно лишь, какие именно пары элементов соединены между собой. На рис. 5.1, а и 5.1, б изображена одна и та же структура связей между элементами А, В, С, Д ?, F. Эту же структуру можно описать, не прибегая к графическому изображению, а перечислив пары связанных между собой элементов: (А, В), (A, D), (B_t С), (В, Е), (В, f), (С, F), (Д ?). Так можно получить два списка: список элементов и список пар элементов. Отсюда видно, что понятие графа не связано напрямую с геометрией или графикой.

Методы теории графов, анализа их топологии ифают важную роль в теории электрических цепей. Наряду с расчетами электрических параметров (тока, напряжения и др.) топологические методы широко применяются для синтеза схем. Роль теории графов велика при структурно-ситуационном анализе задач диспетчерского управления электрическими сетями и системами, в которых существенны вопросы распознавания текущей ситуации, идентификации состояния электрической системы. Методы теории графов позволяют распознать свойства электрической схемы, которые определяются не только собственными характеристиками элементов, но и их связями.