Код Харари

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

Определение

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

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

Примечания

Ссылки

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

Для улучшения этой статьи по математике желательно?: Викифицировать статью. Проставить интервики в рамках проекта Интервики. Проставив сноски, внести более точные указания на источники. Викифицировать список литературы, используя шаблон {{книга}}, и проставить ISBN.

Связать^?

На эту статью не ссылаются другие статьи Википедии. Пожалуйста, воспользуйтесь подсказкой и установите ссылки в соответствии с принятыми рекомендациями.