Вопрос 6: Графы. Определение и способы физического представления: сравнительный анализ этих способов

 

Граф — это совокупность непустого множества вершин и множества пар вершин.

Граф или неориентированный граф G — это упорядоченная пара G: = (V,E), для которой выполнены следующие условия:

§  V это непустое множество вершин или узлов,

§  E это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

Вершины и рёбра графа называются также элементами графа, число вершин в графе | V |  — порядком, число рёбер | E |  — размером графа.

Вершины u и v называются концевыми вершинами (или просто концами) ребра e = {u,v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть e = {v,v}.

Степенью deg V вершины V называют количество инцидентных ей рёбер(при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

 

Ориентированный граф

Ориентированный граф (сокращённо орграф) G — это упорядоченная пара G: = (V,A), для которой выполнены следующие условия:

§  V это непустое множество вершин или узлов,

§  A это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.

Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v \to w ведёт от вершины v к вершине w.

 

 

Смешанный граф

Смешанный граф G — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными. Записывается упорядоченной тройкой G: = (V,E,A), где V, E и A определены так же, как выше.

Ориентированный и неориентированный графы являются частными случаями смешанного.

 

 

Способы представления графа в информатике

 

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

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

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

§  Двумерный массив;

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

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

 

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

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

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

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

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

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

 

Список рёбер

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

 

Список инцидентности

Эта структура содержит для каждой вершины vV список таких вершин uV, что существует дуга (v,u) в орграфе или ребро (v,u) в неориентированном графе. Каждый элемент такого списка содержит два поля: информацию о вершине и указатель на следующий элемент в списке.

            Пример. Графы, изображённые на рис. 1.10, имеют следующие списки инциндентности:

а                                                                                 б

            НАЧАЛО                                                                 НАЧАЛО

            I          ·®II®II®III                                                          I          ·®II

            II         ·®I®I®II                                                   II         ·®I®II

            III       ·®I                                                               III       ·®I    

 

            Адреса начала каждой записи хранятся в массиве указателей НАЧАЛО.

            Очевидно каждое ребро неориентированного графа представлено в списке инциндентности  дважды: через u в списке для вершины v и через v в списке для вершины u.

 

а                                                         б

    

 

Качество физического представления графа тем выше, чем меньше объем занимаемой им памяти (первый критерий) и чем меньше времени требуется для ответа на вопросы: “связаны ли две данные вершины?” и “с какими вершинами соединена данная вершина?” (второй критерий).

 

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

В каждой строке матрицы интидентности для неориентированного или ориентированного графа только два элемента отличны от нуля (или один, если ребро является петлёй). Такой способ задания графа оказывается неэффективным как с точки зрения первого, так и второго критериев.

Список рёбер

            Этот способ задания графа позволяет сэкономить память, однако он неэффективен с точки зрения второго критерия.

 

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

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

 

            Оптимальным способом физического представления графа в общем случае являются так называемые списки инцидентности.  Эта структура содержит для каждой вершины vV список таких вершин uV, что существует дуга (v,u) в орграфе или ребро (v,u) в неориентированном графе. Каждый элемент такого списка содержит два поля: информацию о вершине и указатель на следующий элемент в списке.