Матрица смежности. Матрица инцидентности

Матрица смежности

Матрица смежности — таблица, где как столбцы, так и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу (либо наоборот).

Недостатком являются требования к памяти — очевидно, квадрат количества вершин.

- двумерный массив;

- матрица с пропусками;

- не явное задание (при помощи функции).

Матрица инцидентности

Каждая строка соответствует определённой вершине графа, а столбцы соответствуют связям графа. В ячейку на пересечении i-ой строки с j-м столбцом матрицы записывается:

1 - в случае, если связь j «выходит» из вершины i,

−1 - если связь «входит» в вершину,

0 - во всех остальных случаях (т.е. если связь является петлёй или связь не инцидентна вершине)

Данный способ является самым ёмким и неудобным для хранения, но облегчает нахождение циклов в графе.

Список рёбер — это тип представления графа в памяти, подразумевающий, что каждое ребро представляется двумя числами — номерами вершин этого ребра. Список рёбер более удобен для реализации различных алгоритмов на графах по сравнению с матрицей смежности.

Обычно в теории графов выделяют некоторые разновидности графов. Среди таких разновидностей выделим следующие:

- полный граф - граф, матрица смежности которого состоит из одних единиц;

- полный обыкновенный граф - граф, у матрицы смежности которого все элементы, за исключением нулевых элементов главной диагонали, равны единице;

- пустой (нулевой) граф - граф, матрица смежности которого нулевая (обыкновенный граф, все вершины которого изолированы, т.е. нет ни одной пары смежных вершин);

- единичный граф - граф, матрица смежности которого единичная (граф, все вершины которого имеют петли и изолированы);

- плоский (планарный) граф - граф, который можно начертить на плоскости так, чтобы его ребра (дуги) пересекались только в его вершинах.

⇐ Предыдущая 123 Следующая ⇒