Модели и структуры данных



         

Логическая структура, определения - часть 2


ребро направлено к этому узлу.

Логически структура-граф может быть представлена матрицей смежности или матрицей инцидентности.

Матрицей смежности для n узлов называется квадратная матрица adj порядка n. Элемент матрицы a(i,j) равен 1, если узел j смежен с узлом i (есть путь < i,j >), и 0 -в противном случае (рис.6.2).

Рис.6.2. Графа и его матрица смежности

Если граф неориентирован, то a(i,j)=a(j,i), т.е. матрица симметрична относительно главной диагонали.

Матрицы смежности используются при построении матриц путей, дающих представление о графе по длине пути: путь длиной в 1 - смежный участок - , путь длиной 2 - (< A,B >,< B,C >), ... в n смежных участков: где n - максимальная длина, равная числу узлов графа. На рис.6.3 даны путевые матирцы пути adj2, adj3, adj4 для графа рис.6.2.

Рис.6.3. Матрицы путей

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

Рис.6.4. Матрицы инцидентности




Содержание  Назад  Вперед