Критерий Гавела-Хакими

Критерий Гавела - Хакими (Havel - Hakimi criterion) — критерий графичности числовой последовательности. Пусть [math]\displaystyle{ \,d }[/math] — правильная [math]\displaystyle{ \,n }[/math]-последовательность. Зафиксируем индекс [math]\displaystyle{ \,i }[/math], [math]\displaystyle{ 1 \leq i \leq n }[/math], и образуем последовательность [math]\displaystyle{ \,c^{i} }[/math] вычеркиванием из [math]\displaystyle{ d }[/math] [math]\displaystyle{ \,i }[/math]-го члена и последовательность [math]\displaystyle{ \,d^{i} }[/math] уменьшением на 1 первых [math]\displaystyle{ \,d_{i} }[/math] членов в [math]\displaystyle{ \,c^{i} }[/math]. Назовем [math]\displaystyle{ \,d^{i} }[/math] производной последовательностью. Справедлива

Теорема. Если для данной последовательности [math]\displaystyle{ \,d }[/math] найдется такое [math]\displaystyle{ \,i }[/math], что производная последовательность [math]\displaystyle{ \,d^{i} }[/math] является графической, то и [math]\displaystyle{ \,d }[/math] — графическая. Если [math]\displaystyle{ \,d }[/math] — графическая последовательность, то каждая последовательность [math]\displaystyle{ \,d^{i} }[/math] является графической.

Литература

• Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.