Представление графа в памяти компьютера

 

Определим граф G как пару (V,E), где V – конечное множество вершин, а Е – множество неупорядоченных и упорядоченных пар вершин. Мощности множеств V и E обозначим буквами N и M. (Мощность конечного множества совпадает с количеством элементов в нем.) Неупорядоченная пара вершин называется ребром, а упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги – ориентированным или орграфом. Единственное структурное различие между ориентированным и неориентированным графом состоит в том, что в первом случае граничные вершины ребра образуют упорядоченную пару, а во втором неупорядоченную. Говорят, что ребро (U, V) соединяет вершины U и V. Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро и любая из его 2-х вершин называютя инцидентными. Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам и дугам. Направление дуги графа на рисунке обозначается стрелкой. В 3-х мерном пространстве любой граф можно представить таким образом, что линии не будут пересекаться.

 

рис.1

 

На рис.1 представлены различные изображения одного и того же графа.

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

Например, при соединении электрических приборов одно направление необходимо обозначить как положительное, для того чтобы однозначно описать распределение электрического тока, хотя действительное направление может и не быть жестко ограничено.

 

Способы описания графа:

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

 

Для хранения перечня ребер необходим 2- мерный массив Х размерности 2*М. Каждая строка массива описывает одно ребро.

Пример:

 

 l₁   V₁ V₃

 l₂   V₁ V₂

          l₃         V₁ V₂

          l₄         V₂ V₃

 

 

Матрица смежности – это двумерный массив А размерности N*N

 

                                            1, если вершины i и j - смежные

                            A[i,j]=

                                             0, если вершины i и j - несмежны

                       

       Пример: Данный граф можно представить в виде матрицы смежности:

 

                                         V₁  V₂ V₃    V₄    V₅    V₆    V₇    V₈

           V₁  0 0 0 0 0 0 0 0

                                  V₂ 1 0 0 0 0 0 0 0

                                  V₃ 0 1 0 1 1 0 0 0

                                         A= V₄ 0 0 0 0 1 0 0 0

                                   V₅ 0 1 0 0 0 0 0 0

                                   V₆ 0 0 0 0 0 0 1 1

                                   V₇ 0 0 0 0 0 0 0 1

                                   V₈ 0 0 0 0 0 0 0 0

Матрица инцидентности графа, имеющего n вершин и m ребер– это двумерный массив А размерности N*M

                    1, если j-е ребро инцидентно i-й вершине

    A[i,j]=  

                    0, если j-е ребро неинцидентно i-й вершине

 

 

                  e1 e2 e3 e4 e5 e6

v1 1 0 0 0 0 0

v2 1 1 0 0 0 1

v3 0 1 1 0 1 0

            v4 0 0 1 1 0 0

            v5 0 0 0 1 1 1

 

Пример. На рис. 2 представлены различные типы конфигураций локальных вычислительных сетей (ЛВС), являющиеся информационными моделями структур ЛВС, представленными в виде графов:

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

• кольцевая конфигурация, когда каждый абонент непосредственно связан с двумя соседними абонентами, а информация передаётся по замкнутому кольцу, чаще всего в одну сторону;

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

• древовидная конфигурация образуется подсоединением нескольких простых каналов связи к одному магистральному;

• полносвязная конфигурация обеспечивает выбор наиболее быстрого маршрута связи между абонентами и удобна там, где управление оказывается достаточно сложным.

Рис. 2

Различные типы                

конфигураций   Шинная

локальных

вычислительных

сетей

 

 

                                                          

Кольцевая

 

 

 

 

Звездообразная

 

 

 

 

                            Полносвязная

 

 

 

                                                          

Древовидная