Шаг 176.
Основы языка Haskell. Программное представление графов в языке Haskell: матрица смежности, матрица инцидентности. Матрица смежности

    На этом шаге мы рассмотрим структуру такой матрицы.

    Пусть G - помеченный граф порядка N, V={1, 2, ..., N}.

    Классическим способом представления неориентированного графа является матрица смежности - это матрица B ⇔ [Bij] размера N × N, где


        ⌈ 1, если существует ребро, соединяющее вершины i и j;
   B ⇔ 
        ⌊ 0, в противном случае.
   

    Аналогично способом представления ориентированного графа является матрица смежности - это матрица B ⇔ [Bij] размера N × N, где


        ⌈ 1, если существует дуга, соединяющее вершины i и j;
   B ⇔ 
        ⌊ 0, в противном случае.

    Основным достоинством представления графа с помощью матрицы смежности является тот факт, что за один шаг можно получить ответ на вопрос: "Существует ли ребро из вершины i в вершину j?".

    Основным недостатком является тот факт, что независимо от количества рёбер объём занятой памяти составляет N × N.

    На практике это неудобство можно уменьшить, сохраняя целую строку (столбец) матрицы в одном машинном слове (для малых N).

    Для представления матрицы смежности в виде S-выражения воспользуемся следующей структурой: строки матрицы определим как упорядоченные списки их элементов, а саму матрицу как список строк.


    Пример. Построим S-выражение, соответствующее неориентированному графу:


Рис.1. S-выражение, соответствующее неориентированному графу

    Построим S-выражение, соответствующее ориентированному графу:


Рис.1. S-выражение, соответствующее ориентированному графу


    Замечания (важные).
  1. Количество единиц в строке матрицы смежности равно степени соответствующей вершины.
  2. Матрица смежности неориентированного графа всегда симметрична (для ориентированного графа это не так).

    Представление графов с помощью матриц смежности иногда удобно в теоретических рассуждениях; например имеют место следующая теорема [1, с.28]: графы изоморфны тогда и только тогда, когда их матрицы смежности получаются друг из друга одинаковыми перестановками строк и столбцов.

    Рассмотренная в приведённой на следующем шаге программе реализация матрицы смежности с помощью S-выражения является неэффективной: основным её недостатком является отсутствие прямого доступа к элементам матрицы.


(1)Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. - М.: Наука, 1990. - 384 с.

    На следующем шаге мы приведем демонстрационный пример.




Предыдущий шаг Содержание Следующий шаг