Математические модели в управлении. Заболотский В.П - 80 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

80
В другом случае элементам системы сопоставляются дуги, а свя-
зям между элементами – вершины графа. Получаемый граф назы-
вается реберным графом.
Построение вершинного графа, особенно при наличии структур-
ной схемы системы, довольно просто, так как для этого достаточно
установить перечень элементов системы, связи между ними и со-
ставить матрицу смежности вершин. Построение реберного графа,
эквивалентного вершинному, значительно сложнее. В то же время
модели систем, представленные в виде вершинных графов, облада-
ют тем недостатком, что физическое содержание отдельных элемен-
тов и логические условия их реализации объединены в одних и тех
же элементах графа – его вершинах. Это чрезвычайно затрудняет
исследование, делая его индивидуальным для каждой структуры,
представленной вершинным графом.
Реберные графы дают возможность сопоставить физические свой-
ства элементов дугам графа, а логические условия их осуществле-
ния – вершинам. Это позволяет разработать полностью формализо-
ванные методы исследования структур, описания которых могут
включать любые логические функции.
В теории графов известны две классические задачи: задача Эй-
лера, состоящая в отыскании простых маршрутов, проходящих че-
рез все ребра графа, и задача Гамильтона, состоящая в отыскании
элементарных маршрутов, проходящих через все вершины графа.
Маршруты, удовлетворяющие условиям задачи Эйлера, называются
эйлеровыми маршрутами (путями), а условиям задачи Гамильтона –
гамильтоновыми маршрутами (путями).
Задачу Эйлера можно рассматривать как задачу упорядочения
ребер, а задачу Гамильтона – как задачу упорядочения вершин гра-
фа. Несмотря на сходство формулировок, эти задачи имеют раз-
личную степень сложности. Доказанные Эйлером теоремы позво-
ляют однозначно по виду графа решать вопрос о существовании
эйлеровых путей. Для гамильтоновых путей такого критерия не су-
ществует.
Поэтому, с одной стороны, для сложных систем относительно про-
сто можно построить вершинный граф, задав, например, матрицу
смежности вершин. С другой стороны, проще исследуется реберный
граф. Возникшее противоречие может быть разрешено путем

Страницы