Составители:
51
следующая группа отсутствует или элемент не является первым в груп-
пе, то этот дополнительный указатель принимает значение nil.
Эта простая идея может быть расширена – можно добавлять нужное
число дополнительных указателей, группируя группы элементов и т. д.
на нужном количестве уровней.
Если реализован только один уровень, то это, фактически, обычный
список и время поиска пропорционально O(n). Однако если имеется
достаточное число уровней, то разделенный список можно считать де-
ревом с корнем на высшем уровне, а для дерева время поиска, как будет
показано ниже, пропорционально O(log n).
1.3.3. Графы
1.3.3.1. Спецификация
Граф G – это упорядоченная пара (V, E), где V – непустое множество
вершин, E – множество пар элементов множества V, называемое мно-
жеством ребер.
Упорядоченная пара элементов из V называется дугой. Если все пары в
Е упорядочены, то граф называется ориентированным (орграфом).
Если дуга e ведет от вершины v
1
к вершине v
2
, то говорят, что дуга e
инцидентна вершине v
2
, а вершина v
2
являются смежной вершине v
1
. В
случае неориентированного графа ребро e является инцидентной обеим
вершинам v
1
и v
2
, а сами вершины – взаимно смежными.
Путь – это любая последовательность вершин орграфа такая, что в
этой последовательности вершина b может следовать за вершиной a,
только если существует дуга, следующая из a в b. Аналогично можно
определить путь, состоящий из дуг.
Путь, начинающийся и заканчивающийся в одной и той же верши-
не, называется циклом. Граф, в котором отсутствуют циклы, называется
ациклическим.
Петля – дуга, соединяющая некоторую вершину сама с собой.
Теория графов является важной частью вычислительной математи-
ки. С помощью этой теории решаются большое количество задач из
различных областей. Граф состоит из множества вершин и множества
ребер, которые соединяют между собой вершины. С точки зрения тео-
рии графов не имеет значения, какой смысл вкладывается в вершины и
ребра. Вершинами могут быть населенные пункты, а ребрами дороги,
соединяющие их, или вершинами являться подпрограммы, а соедине-
Страницы
- « первая
- ‹ предыдущая
- …
- 49
- 50
- 51
- 52
- 53
- …
- следующая ›
- последняя »
