Код Харари

Код Харари в теории графов — наибольшее из двоичных чисел, полученных при обработке матриц смежности.

Определение

Пусть дан неориентированный граф. Пронумеруем его вершины произвольно и составим матрицу смежности $A$. Поскольку для неориентированного графа она симметрична, достаточно знать её верхний треугольник $A^{\prime }$. Расположим числа из $A^{\prime }$ в виде двоичной строки (слева направо и сверху вниз). Меняя нумерацию вершин графа, получим другие двоичные строки, сравнивая эти строки между собой как двоичные числа (то есть по первому биту; при равенстве первых битов — по второму и так далее), наибольшее из найденных двоичных чисел и называется кодом Харари, а соответствующая ему нумерация вершин графа — канонической. Иногда код Харари переводят в десятичное число.

Максимальным код Харари будет в том случае, когда в графе присутствует наибольшее количество возможных связей вида 1-2, 1-3, 1-4, 1-5 …, 2-3, 2-4 … (где цифры — нумерация вершин графа), то есть если индекс $i$-вершины минимален, а количество связей с другими вершинами (имеющими индекс $i+a$, где $a$ — натуральное число, причём $a\to min$) максимально, то и код Харари будет максимален.

Ссылки

Теория графов. — Харари Фрэнк.

Шаблон:Rq