24. Динамические типы данных: графы. Виды, структура, основные свойства.

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

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

Многосвязная структура обладает следующими свойствами:

• 1) на каждый элемент (узел, вершину) может быть произвольное количество ссылок;

• 2) каждый элемент может иметь связь с любым количеством других элементов;

• 3) каждая связка (ребро, дуга) может иметь направление и вес.

В узлах графа содержится информация об элементах объекта. Связи между узлами задаются ребрами графа. Ребра графа могут иметь направленность, показываемую стрелками, тогда они называются ориентированными, ребра без стрелок - неориентированные.

Двунаправленные графы (bi-directional graphs) - самый простой тип графов. Именно этот тип представлен на рисунке. В данном типе графов, если два узла соединены друг с другом, то между этими узлами можно свободно "перемещаться".

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

свойства.

1. Каждая дуга отображает звено системы с соответствующим математическим изображением.

2. Если к входной (начальной) вершине некоторой дуги присоединяются (входят у нее) несколько дуг, то соответствующая входная переменная является суммой исходных величин этих дуг.

3. Если из конечной вершины выходят несколько дуг, то входная величина всех дуг одинакова.

Граф САК легко построить, если известна структурная схема системы. Если известный граф, то нетрудно построить структурную схему соответствующей системы. Вершины графа изображаются кругами.

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

1. Изобразить схему таким образом, чтобы в сумматорах все входные величины имели знак плюс.

2. Каждый сумматор заменить вершиной со входной величиной, которая равняется исходной величине этого сумматора.

3. Каждое звено структурной схемы заменить дугой с оператором (передаточной функцией), который равняется оператору этого звена.

4. Каждой переменной, в том числе и возмущению, поставить в соответствие свою вершину.

5. Дополнительное изображение (если это нужно) вершины одной из дуг на общем входе некоторой дуги провести с учетом единичной передаточной функции.