Введение в теорию графов. Способы представления ориентированных и

графов

вершин V и множеством пар вершин E. Пишут G=(V, E).

Будем также использовать обозначения |V| = n и |Е| = m.
Если пара вершин неупорядочена, то ее принято называть ребром. Если упорядочена – дугой.
Граф, состоящий только из ребер называется неориентированным графом. Граф, содержащий только дуги - ориентированным графом или орграфом.
Две вершины x и y, соединенные ребром (x, y), называют смежными вершинами. Если вершины соединены дугой (x,y), то вершина x смежна вершине y, а обратной смежности нет.

и любая из двух его вершин называются инцидентными.
Любому ребру или

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

ребрам графа
Списки инцидентности

Это матрица А с n строками, соответствующими вершинам, и m

столбцами, соответствующими ребрам. Для ориентированного графа столбец, соответствующий дуге (x,y) содержит 1 в строке, соответствующей вершине х, -1 в строке, соответствующей вершине у, и нули во всех остальных строках. В случае неориентированного графа столбец, соответствующий ребру {х,у}, содержит 1 в строках, соответствующих х и у, и нули в остальных строках.
Этот способ один из самых худших способов представления графов с алгоритмической точки зрения. Он требует n*m ячеек памяти, причем большинство этих ячеек занято нулями. Неудобен также доступ к информации.
Матрица инцидентности лучше всего подходит для операции «перечисление ребер, инцидентных вершине x».

В = [bij] размера nхm, где bij =1, если существует

ребро, идущее из вершины х в вершину у, bij =0 в противном случае.
Здесь мы подразумеваем, что ребро {х,у} неориентированного графа идет как от х к у, так и от у к х, так что матрица смежности такого графа всегда является симметричной.
Недостатком является тот факт, что независимо от числа ребер объем занятой памяти составляет n2.
Этот способ хорош, когда нам надо проверять смежность или находить вес ребра по двум заданным вершинам.

когда m гораздо меньше n2) является метод представления графа с

помощью списка пар, соответствующих его ребрам.
Пара соответствует дуге <х,у>, если граф ориентированный, и ребру {х,y} в случае неориентированного графа. Очевидно, что объем памяти в этом случае составляет 2m.
Неудобством является большое число шагов, необходимое для получения множества вершин, к которым ведут ребра из данной вершины.

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

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

теорию графов.Способы представления ориентированных и неориентированных графов» на основе презентации.
2.

Комбинаторика для программистов. Липский В. М.: «Мир», 1988, стр. 79-83.