Содержание

• Содержание
  • Список рёбер
  • Списки смежности
• Иерархический список
• Деревья
  • Основные определения
• Примечания

Список рёбер

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

<номер_начальной_вершины> <номер_конечной_вершины> [<вес_ребра>]

В качестве примера приведём списки ребёр (дуг), задающие те же три графа с рис. 11.5, рис. 11.6 и рис. 11.7 (см. рис. 11.9).

Таблица 11.9. Примеры списков рёбер (дуг)

a b 
a c 
b c
b d
c d
c f
f d
b f

1 2
1 4
3 1
3 2
3 5
4 3

a b 1
a c 10
b c 2
b d 10
c d 3

Если задаётся ориентированный граф, то номера вершин понимаются как упорядоченная пара, а если граф неориентированный — как неупорядоченная.

Списки смежности

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

<номер_начальной_вершины>: <номера_смежных_вершин>

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

В качестве примера приведём списки смежности, задающие всё те же три графа, изображённые на рис. 11.5, рис. 11.6 и рис. 11.7 (см. рис. 11.10).

Таблица 11.10. Примеры списков смежности

a: b c
b: c d f
c: d f
d: f

1: 2 4 
3: 1 2 5
4: 3

b: a 1 c 2 d 10
c: a 10 d 3

Иерархический список

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

Рис. 11.11.  Пример иерархического списка

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

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

Деревья

Дерево — это частный случай графа, наиболее широко применяемый в программировании.

Основные определения

Существует довольно много равносильных определений деревьев, вот лишь некоторые из них.

1. Дерево — это связный граф без циклов.
2. Дерево — это связный граф, в котором при N вершинах всегда ровно N-1 ребро.
3. Дерево — это граф, между любыми двумя вершинами которого существует ровно один путь.

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

Таблица 11.4. Примеры деревьев

Рис. 11.12.  Корневое дерево высоты 3

Мы будем изучать и использовать только один частный случай ориентированных деревьев — корневые деревья (см. рис. 11.12).

Корневое дерево — это ориентированное дерево, в котором можно выделить вершины трёх видов: корень, листья (другое их название: терминальные вершины) и остальные вершины (нетерминальные); причём должны выполняться два обязательных условия:

1. из листьев не выходит ни одна дуга; из других вершин может выходить сколько угодно дуг;
2. в корень не заходит ни одна дуга; во все остальные вершины заходит ровно по одной дуге.

Традиционно в математике и в родственных ей науках (в том числе и в теоретическом программировании) деревья «растут» вниз головой: это делается просто для удобства наращивания листьев в случае необходимости. Таким образом, на рисунках корень дерева оказывается самой верхней вершиной, а листья — самыми нижними.

Предок вершины v — это вершина, из которой исходит дуга, заходящая в вершину v. Потомок вершины v — это вершина, в которую заходит дуга, исходящая из вершины v. В этих терминах можно дать другие определения понятиям корень и лист: у корня нет предков, у листа нет потомков.

Бинарное дерево — это корневое дерево, каждая вершина которого имеет не более двух потомков. В таком случае иногда говорят о левом потомке и правом потомке для текущей вершины.

Высота корневого дерева — это максимальное количество дуг, отделяющих листья от корня. Если дерево не взвешенное, то его высота — это просто расстояние от корня до самого удалённого листа.

И в заключение мы приведём определение, связывающее произвольные графы с деревьями более плотно.

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

Рис. 11.13.  Каркас графа

Примером каркаса является (корневое) дерево кратчайших путей от некоторой выделенной вершины (она будет корнем каркаса) до всех остальных вершин графа.

Примечания