- Код Харари
-
Код Харари в теории графов — наибольшее из двоичных чисел, полученных при обработке матриц смежности.
Определение
Пусть дан неориентированных граф. Пронумеруем его вершины произвольно и составим матрицу смежности
. Поскольку для неориентированного графа она симметрична, достаточно знать её верхний треугольник
. Расположим числа из
в виде двоичной строки (слева направо и сверху вниз). Меняя нумерацию вершин графа, получим другие двоичные строки, сравнивая эти строки между собой как двоичные числа (то есть по первому биту; при равенстве первых битов — по второму и так далее), наибольшее из найденных двоичных чисел и называется кодом Харари, а соответствующая ему нумерация вершин графа — канонической. Иногда код Харари переводят в десятичное число.
Максимальным код Харари будет в том случае, когда в графе присутствует наибольшее количество возможных связей вида 1-2, 1-3, 1-4, 1-5 …, 2-3, 2-4 … (где цифры — нумерация вершин графа), то есть если индекс
-вершины минимален, а количество связей с другими вершинами (имеющими индекс
, где
— натуральное число, причём
) максимально, то и код Харари будет максимален.
Примечания
Ссылки
Теория графов. — Харари Фрэнк.
Для улучшения этой статьи по математике желательно?: - Викифицировать статью.
- Проставить интервики в рамках проекта Интервики.
- Проставив сноски, внести более точные указания на источники.
- Викифицировать список литературы, используя шаблон {{книга}}, и проставить ISBN.
На эту статью не ссылаются другие статьи Википедии. Пожалуйста, воспользуйтесь подсказкой и установите ссылки в соответствии с принятыми рекомендациями.Категория:- Теория графов
Wikimedia Foundation. 2010.