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

Определение

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

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

Примечания

Ссылки

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