Алгоритм Гавела — Хакими

Алгоритм Гавела — Хакими — рекурсивный алгоритм позволяющий определить появляется ли данный список целых чисел как список всех валентностей некоторого конечного простого графа. При положительном ответе на этот вопрос список называется графическим.

Алгоритм предложен Вацловом Гавелом^[чеш.] в 1955 и переоткрыт Луисом Хакими^[англ.] в 1962.

Алгоритм

Алгоритм основан на следующей теореме.

Пусть $s,d_{1},\dots ,d_{s},t_{1},\dots ,t_{k}$ есть конечный список неотрицательных целых чисел в невозрастающем порядке. Список $s,d_{1},\dots ,d_{s},t_{1},\dots ,t_{k}$ является графическим, тогда, и только тогда, когда список $d_{1}-1,\dots ,d_{s}-1,t_{1},\dots ,t_{k}$ графический.

Описанную операцию следует применять поочерёдно с упорядочиванием списка. Если в какой-то момент получаем список из нулей то изначальный список являлся графическим. Если же в списке появится отрицательное число то изначальный список не являлся графическим.

Примеры

Граф со списком валентностей 4,4,3,3,2,2,1,1.

Применим алгоритм к списку $4,4,3,3,2,2,1,1$ . Мы поочерёдно применяем теорему и упорядочивание. То что в результате получается список из нулей означает, что список $4,4,3,3,2,2,1,1$ графический.
${\begin{matrix}4&4&3&3&2&2&1&1\\&3&2&2&1&2&1&1\\&3&2&2&2&1&1&1\\&&1&1&1&1&1&1\\&&1&1&1&1&1&1\\&&&0&1&1&1&1\\&&&1&1&1&1&0\\&&&&0&1&1&0\\&&&&1&1&0&0\\&&&&&0&0&0\end{matrix}}$

Применим алгоритма к списку $7,6,3,3,2,2,1,1$ . То что в результате получается список из отрицательных чисел означает, что список $7,6,3,3,2,2,1,1$ не является графическим.
${\begin{matrix}7&6&3&3&2&2&1&1\\&5&2&2&1&1&0&0\\&&1&1&0&0&-1&0\end{matrix}}$

См. также

Теорема Эрдёша — Галлаи

Примечания

Havel, Václav (1955), "POZNÁMKA O EXISTENCI KONEČNÝCH GRAFŮ", Časopis pro pěstování matematiky, 80: 477—480
Hakimi, S. L. (1962), "On realizability of a set of integers as degrees of the vertices of a linear graph. I", Journal of the Society for Industrial and Applied Mathematics, 10: 496—506.

Похожие исследовательские статьи

Систе́ма счисле́ния — символический метод записи чисел, представление чисел с помощью письменных знаков.

Тест Миллера — Рабина — вероятностный полиномиальный тест простоты. Тест Миллера — Рабина, наряду с тестом Ферма и тестом Соловея — Штрассена, позволяет эффективно определить, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа. Тем не менее тест Миллера — Рабина часто используется в криптографии для получения больших случайных простых чисел.

Алгори́тм Евкли́да — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел. Алгоритм назван в честь греческого математика Евклида, который впервые описал его в VII и X книгах «Начал». Это один из старейших численных алгоритмов, используемых в наше время.

Ма́трица — математический объект, записываемый в виде прямоугольной таблицы элементов кольца или поля, который представляет собой совокупность строк и столбцов, на пересечении которых находятся его элементы. Количество строк и столбцов задаёт размер матрицы. Матрицу можно также представить в виде функции двух дискретных аргументов. Хотя исторически рассматривались, например, треугольные матрицы, в настоящее время говорят исключительно о матрицах прямоугольной формы, так как они являются наиболее удобными и общими.

Определи́тель (детермина́нт) в линейной алгебре — скалярная величина, которая характеризует ориентированное «растяжение» или «сжатие» многомерного евклидова пространства после преобразования матрицей; имеет смысл только для квадратных матриц. Стандартные обозначения определителя матрицы $\text{[math]}$ — $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ .

Фигурные числа — числа, которые можно представить с помощью геометрических фигур. Это историческое понятие восходит к пифагорейцам, которые развивали алгебру на геометрической основе и представляли любое положительное целое число в виде набора точек на плоскости. Отголоском этого подхода остались выражения «возвести число в квадрат» или «в куб».

Китайская теорема об остатках — несколько связанных утверждений о решении линейной системы сравнений.

Алгоритм Штрассена предназначен для быстрого умножения матриц. Он был разработан Фолькером Штрассеном в 1969 году и является обобщением метода умножения Карацубы на матрицы.

Евклидово кольцо — общеалгебраическое кольцо, в котором существует аналог алгоритма Евклида.

Threefish — в криптографии симметричный блочный криптоалгоритм, разработанный автором Blowfish и Twofish, американским криптографом Брюсом Шнайером в 2008-м году для использования в хэш-функции Skein и в качестве универсальной замены существующим блочным шифрам. Основными принципами разработки шифра были: минимальное использование памяти, необходимая для использования в хэш-функции устойчивость к атакам, простота реализации и оптимизация под 64-разрядные процессоры.

Теоре́ма Ги́льберта о нуля́х — теорема, устанавливающая фундаментальную взаимосвязь между геометрией и алгеброй. Использование этой взаимосвязи является основой алгебраической геометрии.

<span class="mw-page-title-main">Карацуба, Анатолий Алексеевич</span> советский и российский математик

Анато́лий Алексе́евич Карацу́ба — советский и российский математик. Создатель первого быстрого метода в истории математики — метода умножения больших чисел.

Деление многочленов — операция деления с остатком в евклидовом кольце многочленов от одной переменной над некоторым полем. Наивный алгоритм, реализующий эту операцию, представляет собой обобщенную форму деления чисел столбиком, легко реализуемую вручную.

$\text{[math]}$ -метод Уильямса — метод факторизации чисел $\text{[math]}$ с помощью последовательностей чисел Люка, разработанный Хью Уильямсом в 1982 году. Алгоритм находит простой делитель $\text{[math]}$ числа $\text{[math]}$ . Аналогичен $\text{[math]}$ -методу Полларда, но использует разложение на множители числа $\text{[math]}$ . Имеет хорошие показатели производительности только в случае, когда $\text{[math]}$ легко факторизуется. Как правило, на практике реализуется не часто из-за невысокого процента подобных случаев.

Алгоритм Диксона — алгоритм факторизации, использующий в своей основе идею Лежандра, заключающуюся в поиске пары целых чисел $\text{[math]}$ и $\text{[math]}$ таких, что $\text{[math]}$ и $\text{[math]}$

Алгоритм Блюма — Микали — это криптографически стойкий алогоритм генерации псевдослучайных последовательностей, с использованием зерна. Идеи алгоритма были изложены Блюмом и Микали в 1984 году. Алгоритм был разработан на основе алгоритма генератора Шамира, предложенного Ади Шамиром годом ранее. Алгоритм отличается от предшественника более сильными требованиями к сложности вычисления выходной последовательности. В отличие от генератора Шамира выходом данного алгоритма являются биты, а не числа.

Функция Мертенса — числовая функция, определяемая для натуральных чисел $\text{[math]}$ формулой:

\text{[math]}

Степень (валентность) вершины графа — количество рёбер графа $\text{[math]}$ , инцидентных вершине $\text{[math]}$ . При подсчёте степени ребро-петля учитывается дважды.

Теорема Эрдёша — Галлаи — утверждение в теории графов, задающее условие, при котором конечной последовательности натуральных чисел можно сопоставить степени вершин некоторого графа. Такие последовательности чисел называются графическими. Теорема доказана венгерскими математиками Палом Эрдёшем и Тибором Галлаи в 1960 году.

Теорема Виноградова о среднем — теорема аналитической теории чисел об оценке среднего значения интеграла некоторых тригонометрических сумм, называемого также интегралом Виноградова; ключевой результат, используемый в методе тригонометрических сумм. Теорема представляет интерес, в частности, потому что оцениваемый в ней интеграл равен количеству решений в целых числах из достаточно большого интервала системы уравнений специального вида.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.