Основы информационных технологий и автоматизированного проектирования в строительстве. Пеньковский Г.Ф. - 21 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

40 41
дублирования связи между пунктами. Для построения решения в виде
графа-дерева используется простое правило экономичности. На каждом
шаге построения дерева берется самое дешевое из возможных ребер, не
образующих цикла. Построение начинается с двух пунктов с наимень-
шей стоимостью дороги между ними (рис. 17, г). Цифрами показана пос-
ледовательность соединения пунктов.
До сих пор
описывались графы неориентированные. Граф, на кото-
ром указано направление каждого ребра, называется ориентированным
или орграфом.
Ориентированные графы используются при анализе транспортных
систем, в задачах управления строительством (при сетевом планирова-
нии). Его удобно представлять в более компактной форме матрицы
(рис. 17, д), что облегчает расчеты сетевых моделей в различных зада-
чах. В ячейках матрицы
записывается информация о наличии или отсут-
ствии связи (1 или 0). Здесь может указываться и другая информация,
представляющая интерес для расчетов в задачах планирования (продол-
жительность работ, стоимость, трудоемкость и т. п.).
При построении сетевых графиков находят применение изоморф-
ные графы, которые имеют одинаковое число вершин и соответствую-
щие друг другу ребра (
рис. 17, е). Изоморфные графы имеют одинаковое
число ребер, однако их размеры и форма могут быть различными. Изо-
морфные графы считаются равными и взаимозаменяемыми, если нет
специальных оговорок.
В процессе описания систем с помощью теории графов осуществ-
ляется структурный анализ систем, анализ всех связей между элемента-
ми системы. Процесс выделения элементов системы и
установления свя-
зей принято называть структуризацией. Глубина структуризации зави-
сит от значимости влияния элементов на свойства системы. При реше-
нии практических задач структурного анализа сложных систем могут
осуществляться три уровня описания связей между элементами.
На первом уровне устанавливается наличие или отсутствие связей
между элементами. Система представляется в виде неориентированного
графа непосредственных связей
, при этом устанавливается, является ли
граф (система) связным или он может быть представлен в виде отдель-
ных подграфов (подсистем).
На втором уровне устанавливается направление и пути передачи сиг-
налов между элементами, определяются входные, управляющие и выход-
ные полюсы. Система представляется в виде ориентированного графа.
Граф называется эйлеровым, если он имеет цикл
, содержащий каж-
дое ребро графа по одному разу (рис. 17, б). Такой граф можно полнос-
тью обойти, проходя по каждому ребру только один раз (по эйлеровой
линии). Этим свойством обладают графы, степени всех вершин которых
четны.
Эйлеров граф представляет интерес при составлении экономичных
маршрутов движения транспорта в строительстве, при разработке тех-
нологических карт
на строительные процессы. Аналогично эйлеровым
линиям в графах могут быть гамильтоновы линии, проходящие через все
вершины по одному разу.
Рис. 17. Виды графов
Графом-деревом называется связный граф, не содержащий циклов
(рис. 17, в). Графы-деревья служат наглядным и эффективным средством
решения задач, связанных с транспортом. В частности, очень важной
является задача прокладки инженерных коммуникаций (дорог, линий
электропередач и т. п.). Задача ставится следующим образом. Имеется n
населенных пунктов (объектов), которые требуется соединить между
собой сетью дорог (
коммуникаций). Для каждой пары пунктов известна
стоимость соединяющей их дороги, если бы она была построена. Необ-
ходимо построить самую дешевую из всех возможных сетей дорог без

Страницы