Граф Вершины Ребра

ФАКУЛЬТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

КАФЕДРА «КОМПЛЕКСНОЕ ОБЕСПЕЧЕНИЕ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ»

КУРСОВАЯ РАБОТА

По дискретной математике

Вариант № 30

на тему:

Представление неориентированных графов в виде связанных списков смежности.

Выполнил: студент(ка) группы ИП–21

__ ПОЛОСКОВ Юрий Сергеевич _________ _________________

(фамилия, имя, отчество) (подпись)

Руководитель: _доктор технических наук, профессор __________

(ученая степень, ученое звание)

__ НЫРКОВ Анатолий Павлович _________ _________________

(фамилия, имя, отчество) (подпись)

Представлена на кафедру: «14» декабря 2012 г.

Санкт – Петербург

Представление неориентированных графов в виде связанных списков смежности.

НЕОРИЕНТИРОВАННЫЕ ГРАФЫ.

Граф G(V, E) — совокупность двух множеств: вершин V и ребер E, между которыми определено отношение инцидентности. Каждое ребро e из E инцидентно ровно двум вершинам, v’ и v’’, которые оно соединяет. При этом вершина v’ и ребро e называются инцидентными друг другу, а вершины v’ и v’’ называются смежными. Часто пишут v’, v’’ из G и e из G. Принято обозначение n для числа вершин графа (мощность множества V): |V (G)| = n, и m для числа его ребер: |E(G)| = m. Говорят, что граф G есть (n, m) граф, где n — порядок графа, m — размер графа.

Если все ребра графа неориентированные, т.е. пары вершин,

определяющие элементы множества E, неупорядочены, то такой граф называется неориентированным графом, или неографом.

Две вершины, связанные между собой ребром, равноправны:

(v’, v’’) =(v’’, v’).

Примеры неориентированных графов в жизни.

Граф Вершины Ребра

Семья Люди Родственные связи

Город Перекрестки Улицы

Сеть Компьютеры Кабели

Домино Костяшки Возможность

Дом Квартиры Соседство

Лабиринт Развилки и тупики Переходы

Метро Станции Пересадки

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

G =(V, X): X - множество ребер Е.

V ={ v ₁, v ₂, v ₃, v ₄, v ₅},

X ={ x ₁={ v ₁, v ₂}, x ₂={ v ₂, v ₃}, x ₃={ v ₂, v ₄}, x ₄={ v ₃, v ₄}}. (см. Рис. 1)

Рис. 1

СПИСКИ СМЕЖНОСТИ.

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

Для задания множества вершин, непосредственно достижимых из вершины v, используют однонаправленный линейный список. Каждый элемент такого списка включает данные (например, некоторое число) и указатель на следующий элемент списка. Список в целом задается указателем на его первый элемент (голову списка). Последний элемент списка содержит «пустой» указатель: в соответствии с примером:

v ₁ |→ v ₂→ v ₇→ …→ v ₉→ 0.

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

Примеры списков смежности:

Список смежности для этого графа:

V₁| -> V₂

V₂| -> V₁-> V₃-> V₄

V₃| -> V₄-> V₂

V₄| -> V₃-> V₂

V₅|

Еще пример представления неориентированного графа в виде списка смежности:

1 | -> 2 -> 5

2 | -> 1 -> 3 -> 4 -> 5

3 | -> 2 -> 4

4 | -> 2 -> 3 -> 5

5 | -> 1 -> 2 -> 4

Для неориентированного графа сумма длин всех списков равна удвоенному числу ребер, так как ребро (u, v) порождает элементы в списках вершины u и вершины v. Количество памяти для представления графа оценивается как O(V + E).

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

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