Переведем число 501в двоичную форму, для чего будем последовательно делить его на 2, справа от черты записывая остатки от деления, а слева на следующей строке частные.
501 1
250 0
125 1
062 0
031 1
015 1
007 1
003 1
Затем выписываем число, начиная с последнего частного, и далее все остатки снизу вверх: 01111101012. Код Харари должен быть треугольным числом, т.е. иметь длину 1, 3, 6, 10, 15, 21 и т.д., если длина, как в нашем случае, не совпадает ни с одним из этих чисел, то добавляем слева необходимое количество нулей (в данном примере добавлен один ноль слева). Разбиваем число на разряды: 0111-110-10-1, вписываем эти числа в верхний треугольник матрицы, затем восстанавливаем всю матрицу, записывая ее строки по столбцам:
Восстанавливаем по этой матрице граф с четырьмя вершинами (рис. 19):
Заметим, что данная нумерация вершин не является канонической. Перенумеруем вершины (рис. 20):
Для получившегося графа матрица смежности
, верхний треугольник, записанный в виде строки, имеет вид 11101100112 = 94710.
|
|
947 > 501, значит, число 501 не является кодом Харари графа.
3. Найти префиксный код бинарного ордерева (рис.21).
Рис. 21