Критерий Гавела-Хакими: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Критерий Гавела - Хакими''' (''Havel - Hakimi criterion'') - критерий графичности числов...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Критерий Гавела - Хакими''' (''Havel - Hakimi criterion'') | '''Критерий Гавела - Хакими''' (''[[Havel - Hakimi criterion]]'') — критерий графичности числовой последовательности. Пусть <math>\,d</math> — [[правильная последовательность|правильная <math>\,n</math>-последовательность]]. Зафиксируем индекс <math>\,i</math>, <math>1 \leq i \leq n</math>, и образуем последовательность <math>\,c^{i}</math> вычеркиванием из <math>d</math> | ||
критерий графичности числовой последовательности. Пусть <math>d</math> | <math>\,i</math>-го члена и последовательность <math>\,d^{i}</math> уменьшением на 1 первых | ||
правильная <math>n</math>-последовательность. Зафиксируем индекс <math>i</math>, <math>1 \leq i | <math>\,d_{i}</math> членов в <math>\,c^{i}</math>. Назовем <math>\,d^{i}</math> производной | ||
\leq n</math>, и образуем последовательность <math>c^{i}</math> вычеркиванием из <math>d</math> | |||
<math>i</math>-го члена и последовательность <math>d^{i}</math> уменьшением на 1 первых | |||
<math>d_{i}</math> членов в <math>c^{i}</math>. Назовем <math>d^{i}</math> производной | |||
последовательностью. Справедлива | последовательностью. Справедлива | ||
'''Теорема'''. ''Если для данной последовательности <math>d</math> найдется такое <math>i</math>, что производная последовательность <math>d^{i}</math> является графической, то и <math>d</math> | '''Теорема'''. ''Если для данной последовательности <math>\,d</math> найдется такое <math>\,i</math>, что производная последовательность <math>\,d^{i}</math> является [[графическая последовательность чисел|графической]], то и <math>\,d</math> — графическая. Если <math>\,d</math> — графическая последовательность, то каждая последовательность <math>\,d^{i}</math> является графической.'' | ||
==Литература== | ==Литература== | ||
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990. | |||
Текущая версия от 11:12, 15 апреля 2011
Критерий Гавела - Хакими (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.