Код Харарі
Код Харарі в теорії графів — найбільше з двійкових чисел, отриманих при обробці матриць суміжності.
Визначення ред.
Нехай дано певний неорієнтований граф. Пронумеруємо його вершини довільним чином і утворимо матрицю суміжності . Оскільки для неорієнтованого графу вона є симетричною, то нам достатньо знати тільки її верхній трикутник (Верхню трикутну матрицю). Запишемо числа з у вигляді двійкового рядка (зліва направо і зверху вниз). Змінюючи нумерацію вершин графу, отримаємо інші двійкові рядки, порівнюючи між собою ці рядки як двійкові числа (тобто по першому біту, якщо вони рівні — по другому і так далі), найбільше із отриманих чисел і називається кодом Харарі, а відповідна йому нумерація вершин графу — канонічною. Максимальним код Харарі буде у тому випадку, коли в графі присутня найбільша кількість можливих зв'язків виду 1-2, 1-3, 1-4, 1-5, …, 2-3, 2-4, … (де цифри — нумерація вершин графу), тобто якщо індекс -вершини мінімальний, а кількість зв'язків з іншими вершинами (які мають індекс , де — натуральне число, при чому ) максимальне, тоді і код Харарі буде максимальним.
Приклади застосування ред.
Код Харарі доволі широко застосовується у теорії графів, зокрема для перевірки на ізоморфність графів: якщо код Харарі у обидвох графів збігається, значить дані графи — ізоморфні.
Джерела ред.
- Frank Harary Graph Theory. — : Perseus Books, 1994. — 274p.
| На цю статтю не посилаються інші статті Вікіпедії. Будь ласка розставте посилання відповідно до прийнятих рекомендацій. |