Русская Википедия:Код Харари

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Определение

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

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

Ссылки

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

Шаблон:Rq