Код Харарі

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

Визначення

Нехай дано певний неорієнтований граф. Пронумеруємо його вершини довільним чином і утворимо матрицю суміжності $A$. Оскільки для неорієнтованого графу вона є симетричною, то нам достатньо знати тільки її верхній трикутник $A^{\prime }$ (Верхню трикутну матрицю). Запишемо числа з $A^{\prime }$ у вигляді двійкового рядка (зліва направо і зверху вниз). Змінюючи нумерацію вершин графу, отримаємо інші двійкові рядки, порівнюючи між собою ці рядки як двійкові числа (тобто по першому біту, якщо вони рівні — по другому і так далі), найбільше із отриманих чисел і називається кодом Харарі, а відповідна йому нумерація вершин графу — канонічною. Максимальним код Харарі буде у тому випадку, коли в графі присутня найбільша кількість можливих зв'язків виду 1-2, 1-3, 1-4, 1-5, …, 2-3, 2-4, … (де цифри — нумерація вершин графу), тобто якщо індекс $i$-вершини мінімальний, а кількість зв'язків з іншими вершинами (які мають індекс $i+a$, де $a$ — натуральне число, при чому $a\to min$) максимальне, тоді і код Харарі буде максимальним.

Приклади застосування

Код Харарі доволі широко застосовується у теорії графів, зокрема для перевірки на ізоморфність графів: якщо код Харарі у обидвох графів збігається, значить дані графи — ізоморфні.

Джерела

• Frank Harary Graph Theory. — : Perseus Books, 1994. — 274p.