[Править]Еще примеры

• 

• 

Десятичная кодировка Деревья представляют собой важный вид графов. С помощью де- ревьев описываются базы данных, деревья моделируют алгоритмы и программы, их используют в электротехнике, химии. Одной из актуаль- ных задач в эпоху компьютерных и телекоммуникационных сетей яв- ляется задача сжатия информации. Сюда входит и кодировка деревьев. Компактная запись дерева, полностью описывающая его структуру, может существенно упростить как передачу информации о дереве, так и работу с ним. Различные виды кодировки деревьев подробно описаны в [14]. Приведем одну из простейших кодировок помеченных деревьев с выделенным корнем — десятичную. Кодируя дерево, придерживаемся следующих правил: 1. Кодировка начинается с корня и заканчивается в корне. 2. Каждый шаг на одну дугу от корня кодируется единицей. 3. В узле выбираем направление на вершину с меньшим номером4. Достигнув висячей вершины, идем назад, кодируя каждый шаг нулем. 5. При движении назад в узле всегда выбираем направление на непройденную вершину с меньшим номером. Кодировка в такой форме получается достаточно компактной, одна- ко она не несет в себе информацию о номерах вершин дерева. Суще- ствуют еще аналогичные кодировки, где вместо единиц проставляются в таком же порядке номера или названия вершин. Есть деревья, для которых несложно вывести формулу десятичной кодировки. Рассмотрим, например графы-звезды, являющиеся полными двудольными графами K1,n, одна из долей которых состоит из одной вершины. Другое обозначение звезд K1,n = Sn. На рис. 22-25 приведены звезды и их двоичные и десятичные ко- дировки. Корень дерева располагается в центральной вершине звезды. Легко получить общую формулу Z(Sn) = 2(4n − 1)/3. Достижимость и контрдостижимость

Задач, в которых используется понятие достижимости, довольно много. Вот одна из них. Граф может быть моделью какой-то организации, в которой люди представлены вершинами, а дуги интерпретируют каналы связи. При рассмотрении такой модели можно поставить вопрос, может ли информация от одного лица х_i быть передана другому лицу х_j, т. е. существует ли путь, идущий от вершины х_i к вершине х_j. Если такой путь существует, то говорят, что вершина х_j достижима из вершины х_i. Можно интересоваться достижимостью вершины х_j из вершины х_i только на таких путях, длины которых не превосходят заданной величины или длина которых меньше наибольшего числа вершин в графе и т. п. задачи.

Достижимость в графе описывается матрицей достижимости R=[r_ij], i, j=1, 2, ... n, где n – число вершин графа, а каждый элемент определяется следующим образом:

r_ij=1, если вершина х_j достижима из х_i,

r_ij=0, в противном случае.

Множество вершин R(x_i) графа G, достижимых из заданной вершины x_i, состоит из таких элементов x_j, для которых (i, j)-й элемент в матрице достижимостей равен 1. Очевидно, что все диагональные элементы в матрице R равны 1, поскольку каждая вершина достижима из себя самой путeм длины 0. Поскольку прямое отображение 1-го порядка Г⁺¹(x_i) является множеством таких вершин x_j, которые достижимы из x_i с использованием путей длины 1, то множество Г⁺(Г⁺¹(x_i)) = Г⁺²(x_i)состоит из вершин, достижимых из x_i с использованием путей длины 2. Аналогично Г^+p(x_i) является множеством вершин, которые достижимы из x_i с помощью путей длины p.

Так как любая вершина графа, которая достижима из x_i, должна быть достижима с использованием пути (или путей) длины 0 или 1, или 2, ..., или p, то множество вершин, достижимых для вершины x_i, можно представить в виде

.

Как видим, множество достижимых вершин R(x_i) представляет собой прямое транзитивное замыкание вершины x_i, т. е. R (x_i) = T⁺(x_i). Следовательно, для построения матрицы достижимости находим достижимые множества R (x_i) для всех вершин  . Полагая, r_ij=1, если   и r_ij=0 в противном случае.