![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Как отмечалось выше, графическую последовательность всегда можно считать правильной. Кроме того, в ней должны быть равные члены (если длина ее п > 1), поскольку не существует графа, степени всех вершин которого попарно различны (см. упражнение 11 в гл. I).
Однако указанные условия отнюдь не являются до-статочными для графичности последовательности. Оче-видно, например, что последовательность (32, 12) не яв-ляется графической, хотя и удовлетворяет упомянутым условиям.
Известно несколько критериев графичности последо-вательности. Одной из важнейших теорем такого рода является критерий Гавела - Хакими, к изложению ко-торого мы приступим.
![]() |
![]() |
Когда dl называется производной последовательностью.
Например, если d = (3, 3, 1, 1), то d1= (2, 0,0 )=d2, d3 = (2, 3,1) = d4.
Теорема 46.1 (В. Гавел, 1955 г., С. Хакими, 1962 г.). Пусть d — правильная п-последователъностъ, n > 1. Если для какого-либо индекса i, 1≤ i ≤ п, производная последовательность dl является графической, то и n — графическая последовательность. Если последовательность d графическая, то каждая последовательность
(i=1, n) является графической.
Пусть di — графическая последовательность, Н — её реализация. Добавив к графу Н новую вершину и соединив ее ребрами с d{ вершинами наибольших степе-вй, получим реализацию последовательности d. Следоательно, d — графическая последовательность.
Обратно, пусть последовательность d является графической. Согласно лемме 45.2 существует такая реализа-ия G этой последовательности, в которой некоторая вершина v степени d{ смежна с d{ вершинами, степени которых наибольшие. Очевидно, что граф G — v является реализацией последовательности di
Предыдущий критерий вместе с леммой 45.2 подсказывают алгоритм распознавания графичности правильной последовательности и построения одной из ее реализаций. Назовем этот алгоритм l-процедурой. Пусть d — равильная n - последовательность, V — n -элементное множество вершин (будущего графа), каждому элемент у v которого приписано неотрицательное целое число d (v) — метка, причем d{v)<n. Пусть, далее, S(v) —подмножество V, составленное из d(v) отличных от вершины v вершин с максимальными.метками (S(v) определено не однозначно). Шаг l-процедуры заключается в следующем:
1) фиксировать произвольную вершину v с положительной меткой (далее эта вершина называется ведущей);
2) фиксировать одно из подмножеств S(v);
3) вершину v соединить ребром с каждой вершиной из S(v);
4) изменить метки вершины v и каждой из вершин и, входящих в S(v), положив d(v):=0, d(u):= d(u)— 1.
Если в результате применения шага l -процедуры какая-либо из меток становится отрицательной, то говорят, что этот шаг проваливается.
![]() | ![]() |
Рис. 46.1
полагаем d(i) = du Из леммы 45.2 и критерия 46.1 вытекает, что возможно одно из двух: либо мы приходим к нулевой последовательности меток и одновременно получаем реализацию последовательности d, либо очередной шаг проваливается, т. е. последовательность d не является графической.
На рис. 46.1 Z-процедура демонстрируется на примере последовательности (З2, 23). Каждый столбец на этом рисунке соответствует одному шагу /-процедуры.
Отметим еще один критерий графичности последовательности.
Теорема 46.2 (П. Эрдёш, Т. Галлаи, 1960 г.). Правильная п-последователъностъ d является графической тогда и только тогда, когда для каждого к = 1, п- 1 верно
![]() |
Необходимость неравенства (1) проверяется легко.
![]() |
![]() |
откуда и вытекает неравенство (1).
Приведем доказательство достаточности условий теоремы, принадлежащее С. А. Чоудаму (1986 г.). Пусть d — правильная n -последовательность, причем неравенство (1) верно для каждого k = 1, п— 1. Если di = r (i—1, п), то хотя бы одно из чисел r и n четное, поскольку сумма членов последовательности d — четное число. Кроме того, r≤п—1. При этих условиях существует п -вершинный регулярный граф степени r (утверждение 7.1). Стало быть, d — графическая последовательность.
![]() |
![]() |
![]() |
Это совсем просто при k ≥ t. Имеем
![]() |
![]() |
![]() |
т. е. неравенство (2) верно.
Далее отдельно рассмотрим две возможности: 1) dk = k, 2) dk ≥ k + l.
![]() |
![]() |
![]() |
![]() |
т. е. неравенство (2) верно.
![]() |
Поэтому
![]() |
и неравенство (2) верно.
![]() |
![]() |
Положив r = min (i: dt+i+1 < k) и учитывая (3), получим
![]() |
Последнее противоречит тому, что последовательность d удовлетворяет неравенствам (1). Неравенство (6) доказано. С учетом (6) и (3) получаем
![]() |
![]() |
Тем самым доказано, что в любой ситуации последовательность с удовлетворяет условиям теоремы. Так как сумма членов этой последовательности равна Σ — 2, то она графическая по индуктивному предположению. Возьмем произвольную реализацию G последовательности с. Пусть а, b €VG, deg a = ci, deg b = сп. Если вершины а и b не смежны, то граф G + аb является реализацией последовательности d и, следовательно, d — графическая последовательность.
Пусть аb € EG. Так как deg а — dt — 1 ≤ п — 2, то существует вершина е € VG, не смежная с а. Но deg e ≥ deg b, поэтому существует вершина f € VG, смежная с е и не смежная с b. Итак, граф G допускает переключение s = (ab, ef). Граф sG = G — ab — ef + ae + bf также служит реализацией последовательности с, причем в нем вершины а и b не смежны. Но тогда, как доказано выше, последовательность d является графической.
При тестировании последовательности с помощью критерия Эрдёша — Галлаи нет необходимости проверять все п— 1 неравенств (1). Пусть d — правильная n -последовательность, k(d)= max { i: di ≥ i). Тогда верно следующее
Утверждение 46.3. Если последовательность d удовлетворяет каждому из неравенств (1) при k = 1, k(d), то она удовлетворяет и каждому из оставшихся неравенств (1).
Доказательство опускается.
Дата публикования: 2015-01-23; Прочитано: 1132 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!