Код Харарі

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Визначення

[ред. | ред. код]

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

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

[ред. | ред. код]

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

Джерела

[ред. | ред. код]
  • Frank Harary Graph Theory. — : Perseus Books, 1994. — 274p.