Cтраница 3
Запишем строки А последовательно одну за другой и рассмотрим полученную последовательность из нулей и единиц как двоичное число. Меняя нумерацию вершин, будем для одного и того же графа получать разные числа. Наибольшее из них определяется для графа однозначно и носит название кода Харари. Код Харарп определяет граф однозначно, поэтому, например, задачу определения изоморфизма двух графов можно свести к сравнению соответствующих кодов Харари. Правда, этот метод столь же неэффективен, как и другие методы установления изоморфизма двух произвольных графов. Нумерация вершин ( и матрица смежности), соответствующая коду Харари, носит название канонической и используется при перечислении ( генерировании) графов с заданными свойствами. [31]
Такой метод контроля используется при возникновении ошибки от случайного сбоя. Метод заключается в том, что образуются специальные контрольные коды, в которых к имеющимся информационным разрядам добавляется определенное число контрольных разрядов. Контрольные разряды формируются путем подсчета единиц для определенных групп информационных разрядов. Один из этих кодов носит название кода Хэмминга. [32]
Информация, которую несет этот объект, равна его энтропии. Она максимальна, когда оба значения сигнала равновероятны. Следовательно, основой оптимального кодирования должно быть требование, чтобы элементарные сигналы встречались в среднем одинаково часто. Поставленному условию удовлетворяет способ, известный под названием кода Шеннона - Фэно. Идея его заключается в следующем. [33]