Код Харари

Код Харари

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

Определение

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

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

Примечания

Ссылки

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



Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Полезное


Смотреть что такое "Код Харари" в других словарях:

  • Харари — (амх. ሐረሪ) Флаг …   Википедия

  • текстовой анализ — Франц. analyse textuelle. Первый вариант деконструктивистского анализа в собственном смысле этого слова, предложенным Р. Бартом. В нем исследователь переносит акцент своих научных интересов с проблемы «произведения» как некоего целого,… …   Постмодернизм. Словарь терминов.

  • ISO 3166-2:ET — ISO 3166 2:ET …   Википедия

  • Эфиопия — У этого термина существуют и другие значения, см. Эфиопия (значения). Федеративная Демократическая Республика Эфиопия የኢትዮጵያ ፌዴራላዊ ዲሞክራሲያዊ ሪፐብሊክ  (амх.) Federaalawaa Dimokraatawaa Repabliikii Itoophiyaa  (оромо) …   Википедия

  • Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С …   Википедия

  • Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) …   Википедия

  • Переходный национальный совет Ливийской республики — араб. المجلس الوطني الانتقالي‎‎ Герб …   Википедия

  • Афар — У этого термина существуют и другие значения, см. Афар (значения). Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей …   Википедия

  • Амхара (регион) — У этого термина существуют и другие значения, см. Амхара (значения). Амхара амх. አማራ Флаг …   Википедия

  • Бенишангул-Гумуз (регион) — Бенишангул Гумуз (амх. ቤንሻንጉል ጉምዝ) Флаг Страна Эфиопия …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»