Элементы теории графов

A.a-1 = e, (a-1).a = e.

Если, кроме того, для "a, b ÎG имеет место коммутативность a^.b = b^.a, то группа называется коммутативной или абелевой.

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

Граф Г – геометрическая фигура, построенная на множестве вершин V = {v₁, v₂, … v_m} и ребер R = {r₁, r₂, … r_n}:

Г = (V, R). (3.1)

Если ребра ориентированы, то их называют дугами, а граф - ориентированным (орграфом). При этом вершины называются узлами.

а) б)

Рис. 3.1.

Примеры использования графов для моделирования:

1. Неориентированные графы описывают (моделируют) дороги между населенными пунктами А, B, C и D (см. рис. 3.1, а).

2. Орграф описывает однонаправленные каналы передачи информации (см. рис. 3.1, б).

Дуга r_i, связанная с злом v_j, называется инцидентной этому узлу, причем, если заходит – положительно инцидентная, если выходит – отрицательно инцидентная.

Два узла v_k и v_i смежны, если им инцидентна одна дуга. Аналогично, две дуги смежны, если они инцидентны одному узлу, причем, если одна выходит, а другая заходит – последовательно смежны, в противном случае - параллельно смежны.

Дуга, выходящая из узла и в не же заходящая называется петлей.

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

Две системы S₁ и S₂ с заданными на них отношениями R₁ и R₂ изоморфны, если:

1) их структурные элементы попарно взаимно однозначно соответствуют друг другу;

2) подмножество элементов А₁ системы S₁ связано отношением R₁, тогда соответствующее подмножество (см. п. 1) А₂ системы S₂ связано отношением R₂.

Существует гомоморфизм (гоморфизм) – упрощенная модель исходной системы, т.е. не выполняются вышеуказанные условия.

Связи в системе можно изображать двояко:

1) элементы – это вершины, а связи – дуги (вершинный граф),

2) элементы – дуги, а связи – узлы (реберный или сигнальный граф).

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

Матрица смежности – квадратная матрица А = {a_ij}, , где m – число узлов, т.е. А_mxm, для которой

.

Число единиц в матрице А равно числу дуг n.

Эта матрица обладает интересным свойством: если возвести матрицу А в k-ую степень, то каждый элемент матрицы А^k будет равен числу путей из узла v_i в узел v_j длиной в k дуг.

Путь в графе – это последовательность последовательно смежных дуг, ориентированных в одном направлении.

Дата добавления: 2013-12-12