Графическая последовательность

Последовательность (d₁, d₂,.., d_n) целых неотрица­тельных чисел ниже называется п-последователъностъю и обозначается одной буквой d. n -последовательность d на-зывается графической, если существует граф, степенная последовательность которого совпадает с d Этот граф называется реализацией последовательности d.

Очевидно, что порядок членов в графической n- после-довательности d несуществен, а каждый ее член d_i удов­летворяет неравенствам 0< d_t < п- 1. Часто удобно эти последовательности считать невозрастающими. Согласно лемме о рукопожатиях сумма всех членов графической последовательности является четным числом.

Назовем n- последовательность d правильной, если вы-полняются два следующих условия:

1) n -l>d_l>d₂>...>d_n,

П

2) 2j di — четное число.

i=l

Без ограничения общности графическую последова­тельность можно считать правильной.

Иногда последовательность d удобно записывать в ви­де d = (c₁^k1, c₂^k2,..., с_р^kp), где числа c_i, попарно различны, а показатель k_i означает количество повторений числа с_i в последовательности d. Так, (5, 2, 1⁶) = (5, 2, 1, 1, 1, 1, 1, 1).

Рассмотрим последовательность d=( 2⁴, 1⁴).Существуют ровно пять графов, являющихся реализациями последовательности d. Они имеют следующие компонен-ты: 1) С ₄, К ₂ и К ₂, 2 ) К₃ ,P₃ и К ₂ , 3) P ₆ и К ₂ , 4) P ₅ и P ₃ ,5) Р ₄и Р ₄.

В общем случае графическая последовательность име­ет много реализаций и их число определить сложно. В установлении связи между этими реализациями важ­ную роль играет вводимое ниже понятие переключения. Пусть G - граф, а,b,с,d - четыре его попарно различные вершины, причем ab € EG,cd € EG, но ac¢EG, bd ¢ EG. Тогда говорят, что граф G допускает переключение s = (ab, cd). Полученный в результате переключения s граф обозначается через sG;граф G превращается в sG в результате удаления ребер аb и cd и присоединения ребер ас и bd: sG = G - ab - cd + ac + bd. Обратное переключение s^-1=(ac, bd) применимо к графу sG.

Тождественное преобразование ребер графа также по определению является переключением. Например, на рис. 45.1 изображены графы G и sG, ({1, 3},{4, 2}).

Очевидно, что переключение не меняет степеней вершин графа. Роль переключений определяется следующей теоремой.

Теорема 45.1. Любая реализация графической последовательности получается из любой другой ее реализации посредством применения подходящей цепочки переключений.

Доказательство этой теоремы основано на следующей лемме.

Рис. 45.1

Лемма 45.2. Пусть G - граф, вершины которого пронумерованы числами 1, 2,..., п в порядке невозраста-ния степеней: G = {1, 2,..., n }, deg i = d_i d_t> d_i+1 , i = 1, n - 1. когда для любой его вершины i существует такая последовательность переключений s₁ ,..., s_t, что в графе Н = s_t...s₁G окружение вершины i совпадает с множе-ством из d_i вершин наибольших степеней, т. е.

{1,2,. ..,d_i }, если i>d_i,

({1, 2,..., i - 1, i + 1, ...,d_i +1}, если i< d_i.

Пусть i,j, k € VG, j > k, ij € EG, ik ¢ EG. Так как > dj, то существует четвертая вершина l, смежная с k, не смежная с j ( рис. 45.2, где, как и всюду в этой главе, пунктирными линиями обозначены ребра, отсутствующие в
графе). Следовательно, граф G допускает переключение s=(ij, kl).
Если G'=sG, то ik € EG', ij € EG'. Сделав несколько подобных переключений, придем к нужному графу Н.

Доказательство теоремы 45.1. Пусть d — правильнаяя графическая n -последовательность.Воспользуемся индукцией по п. Как подтверждает прямая проверка,
при n ≤ 4 каждая графическая последовательность имеет только одну реализацию. Следовательно, для п≤ 4 утверждение теоремы тривиально. Пусть п> 4 и это утверждение верно для всех графических (п - 4)-последовательностей. Пусть, далее, G₁ и G₂ – две реализации последовательности d. Для каждого из графов G₁ и G₂ обозначим через v какую-либо вершину степени d₁ . Согласно лемме 45.2 существуют такие цепочки переключений s₁,..., s_t и s₁,..., s_r, что в графах H₁ = s_t... s₁G₁ и H₂= s_r....s₁G₂ окружения вершины v состоят из вершин степеней d₂ ,d₃ ,...,d_d1+1. Поэтому степенные последовательности графов H₁ - v и H₂ - v совпадают. По индуктивному предположению существует такая цепочка переключений s₁ ,..., s_h, что

H₁ - v =s_k,..., s₁ (H₂ - v).

Эти переключения не затрагивают вершины v, поэтому H₁ = s_k,..., s₁H₂. Далее имеем

G₁ = s₁^-1... s_t^-1H₁ = s₁^-1... s_t^-1s_k.... s₁H₂ = s₁^-1... s_t^-1s_k ....s₁s_t^'... s₁^'HG₃.

Иногда, хотя и редко, граф определяется своей сте­пенной последовательностью однозначно. Если все реа­лизации графической последовательности изоморфны, то эта последовательность называется униграфической, а ее реализация — униграфом. Строение униграфов из­вестно, однако его описание слишком сложно. Унигра­фом является, например, простой цикл C₅.