Решение.

Решение.

Пронумеруем вершины графа, выпишем матрицу смежности и ее верхний треугольник (рис. 17).

, верхний треугольник, записанный в виде строки, имеет вид 0101011100₂ = 348₁₀.

Легко увидеть, что данная нумерация вершин не является канонической. Действительно, сменим нумерацию вершин (рис. 18).

, верхний треугольник, записанный в виде строки, имеет вид 1100011010₂ = 794₁₀.

Можно убедиться, что при всех других способах нумерации вершин получаются числа, меньшие 794. следовательно, последняя нумерация вершин является канонической, а кодом Харари данного графа является число 794.

3. Восстановить и нарисовать граф по числу 501 как по коду Харари. Проверить, действительно ли нумерация вершин каноническая (то есть, является ли это число кодом Харари).

Переведем число 501в двоичную форму, для чего будем последовательно делить его на 2, справа от черты записывая остатки от деления, а слева на следующей строке частные.

501 1

250 0

125 1

062 0

031 1

015 1

007 1

003 1

Затем выписываем число, начиная с последнего частного, и далее все остатки снизу вверх: 0111110101₂. Код Харари должен быть треугольным числом, т.е. иметь длину 1, 3, 6, 10, 15, 21 и т.д., если длина, как в нашем случае, не совпадает ни с одним из этих чисел, то добавляем слева необходимое количество нулей (в данном примере добавлен один ноль слева). Разбиваем число на разряды: 0111-110-10-1, вписываем эти числа в верхний треугольник матрицы, затем восстанавливаем всю матрицу, записывая ее строки по столбцам:

Восстанавливаем по этой матрице граф с четырьмя вершинами (рис. 19):

Заметим, что данная нумерация вершин не является канонической. Перенумеруем вершины (рис. 20):

Для получившегося графа матрица смежности

, верхний треугольник, записанный в виде строки, имеет вид 1110110011₂ = 947₁₀.

947 > 501, значит, число 501 не является кодом Харари графа.

3. Найти префиксный код бинарного ордерева (рис.21).

Рис. 21