4.11. Раскраска вершин и теорема Шеннона об информационной емкости графа

Пусть дан граф G. Этот граф называется k‑раскра­шиваемым, если существует такое разбиение множества его вершин на k классов

C₁, C₂, …, C_k, (4.9)

что все ребра в G соединяют вершины только из разных классов. Само такое разбиение называется k‑раскраской. При раскраске каждое ребро имеет две вершины необхо­ди­мо разного цвета, а все вершины, относящиеся к одному и то­му же классу, окрашены в один и тот же цвет.

Наименьшее число k классов раскраски называется хроматическим числом графа G. Если число способов рас­краски графа равно хроматическому числу, то граф именуют k‑хроматическим, а классы (4.9) — хроматичес­ким раз­ложением G.

Теорема 4.12 Пусть G — связный неориен­ти­ро­ванный граф. Для того, чтобы граф был бихрома­тическим, необходимо и достаточно, чтобы он не имел циклов нечетной длины.

Необходимость. Предположим, что граф G — бихро­матический и имеет хотя бы один цикл нечетной длины. Об­хо­дя этот цикл, мы будем иметь чередующиеся цвета смеж­ных вершин. Поскольку число вершин в цикле нечетно, то дойдя до вершины, с которой начали обход цикла, полу­чим, что она должна иметь цвет противоположной рас­краски. Приходим к противоречию.

Достаточность. Произвольный граф G может быть раскрашен бихроматически следующим образом. Зафикси­руем произвольную вершину V и раскрасим ее в один из двух различных цветов. Все смежные с ней вершины рас­красим в противоположный цвет и так далее, пока не рас­красим весь граф. Предположим, что при такой раскраске некоторая вершина V^* оказалась раскрашена в два раз­личных цвета. Тогда из V в V^* существует две цепи: одна четной, а другая — нечетной длины. Эти две цепи образуют цикл нечетной длины. Приходим к противоречию, что и до­ка­зывает теорему.

В [5] показано, что если максимальная степень вершин графа G равна r, то граф G представляется r‑раскрашиваем, за исклю­чением двух случаев:

при r = 2 граф G имеет компоненту связности, явля­ющуюся циклом нечетной длины,

при r > 2 полный граф с r + 1 вершинами является ко­мпо­нентой связности графа G.

Пусть G — граф без петель и кратных ребер. Подмно­жество вершин S  G называется внутренне устойчивым, если любые вершины v₁,v₂  S не смежные. Пусть A — се­мейство всех таких подмножеств. Числом внутренней ус­той­чивости графа G называется величина

G) = max_{S  A}S.

Теорема 4.13 Хроматическое число k(G) и число внутренней устойчивости G) связаны неравенством

V  G)k(G)

для G = (V, E).

Доказательство. Правильно раскрасим вершины гра­фа G в k(G) цветов. Тогда каждое множество вершин V_i, ок­рашенных в один и тот же цвет, внутренне устойчиво и сле­довательно, V_i  G) и V = _i V_i  G)k(G).

Отображение  множества V в себя называется сох­ран­ным, если для любой пары несмежных вершин v₁ и v₂ вер­шины (v₁) и (v₂) также несмежные и различны. Ясно, что сохранное отображение переводит всякое внутренне ус­той­чивое множество во внутренне устойчивое.

Определим произведение графов G₁ = (V₁, E₁) и G₂(V₂, E₂) следующим образом. Под произведением G₁G₂, будем понимать граф, множеством вершин которого явля­ется декартово произведение V₁V₂, а вершины (v₁, v₂), (v₁, v₂)  V₁V₂ смежные, если

• v₁ смежная с v₁ в G₁ и v₂ cмежная с v₂ в G₂ либо

• v₁ смежная с v₁, v₂ = v₂ либо

• v₁ = v₁, а v₂ смежная с v₂.

Теорема 4.14 (Шеннон) Для любых двух графов G₁ = (V₁, E₁) и G₂ = (V₂, E₂) имеем

G₁)G₂)  G₁G₂),

но если для графа G₁ существует сохранное отобра­жение , такое, что множество (V₁) внутренне ус­той­чиво, то

G₁)G₂) = G₁G₂).

Доказательство. Если S₁ и S₂ наибольшие внутренне устойчивые множества для G₁ и G_2, то S₁S₂ — внутренне устойчиво и G₁G₂)  S₁S₂ = S₁S₂ = G₁)G₂).

Пусть теперь ‑сохранное отображение для графа G и множество (V₁) внутренне устойчиво. Для произвольных v  V₁ и v  V₂ обозначим f(v, v) = ((v), v). Пусть S₀ —наибольшее внутренне устойчивое множество графа G₁G₂. Непосредственно проверяется, что f(S₀) также внутренне устойчиво и f(S₀) = S₀. Распределим элементы из f(S₀) по k классам в зависимости от элемента v в паре (v, v). Каждый класс содержит не более, чем G₂) элементов. Следовательно, G₁G₂) = f(S₀)  kG₂)  G₁)G₂). Отсюда и вытекает доказываемое равенство.

Рассмотрим пример применения теоремы Шеннона к задаче об информационной емкости множества инфор­ма­ционных сообщений.

Пусть по информационному каналу передается пять сообщений: v₁, v₂, v₃, v₄, v₅. При приеме сообщение v₁ может быть истолковано как v₁ или v₂, соответственно сообщение v₂ как v₂ или v₃ и так далее, наконец, v₅ — как v₅ или v₁. Какое наибольшее количество сообщений можно принять, не спутав друг с другом?

Задача сводится к нахождению наибольшего внутренне устойчивого множества S графа, который изображен на рисунке 4.14.

Очевидно, что здесь G) = 2 и можно считать, что S = (v₁, v₃) или S = (v₁, v₄) или S = (v₃, v₅ ) и т.д.

v₁

v₂ v₅

v₃ v₄

Рисунок 4.14

Предположим, что мы будем использовать сообщения, определенные на GG. Тогда GG)(G₂))²  4.

Построив для нашего примера внутренне устойчивое множество, получим

S = { v₁,v₁,v₂,v₃ , v₃,v₅, v₄,v₂, v₅,v₄}.

Видим, что в этом случае GG) = 5.

Информационной емкостью графа G называют число (G) = supⁿ√Gⁿ). Так как Gⁿ)  Vⁿ = Vⁿ, то (G)  V.

Отсюда и из теоремы 4.14 следует, что если для графа G = (V,E) существует сохранное отображение , такое что множество (V) внутренне устойчиво, то для такого графа (G) = G).