7.3. Раскраски и семейства графов

Применим теперь идеи, изложенные в этой главе, к теории графов. Этот подход, появившийся совсем недавно, представляется особенно интересным по двум причинам. Во-первых, он приводит к классификации графов, основанной на понятии, естественным образом обобщающем понятие раскраски графа. Во-вторых, вопросы, связанные с этой классификацией, можно отождествить с вопросами, касающимися теории грамматических форм. Таким образом, мы обнаруживаем интересную связь между теорией языков и теорией графов.

Помимо орграфов, введенных в гл. 2, мы будем рассматривать и неориентированные графы, которые для краткости будем называть просто графами. По определению графом является пара (V, E), где V - конечное множество, элементы, которого называются вершинами, а E - множество неупорядоченных пар элементов V. Элементы E называются линиями или ребрами (в отличие от стрелок в случае орграфов). В дальнейшем предполагается, что графы и орграфы не содержат петель, т. е. ребер или стрелок, ведущих из вершины в нее же. Предполагается также, что каждый граф или орграф содержит хотя бы две вершины, связанные линией или соответственно стрелкой. Сначала рассмотрим непомеченные графы и орграфы и начнем с основных определений.

Граф G' называется интерпретацией графа G, если существует отображение φ множества вершин G' в множество вершин G, такое, что для каждого ребра в G', соединяющего вершины x и y, существует ребро в G, соединяющее вершины φ(x) и φ(y).

Орграф G' называется интерпретацией орграфа G, если существует отображение φ множества вершин Gr в множество вершин G, такое, что для каждой стрелки из x в y в орграфе G' существует стрелка из φ(x) и φ(y) в орграфе G.

Каждый граф (соответственно орграф) G определяет семейство (G) графов (соответственно орграфов), состоящее из всех интерпретаций G. (Заметим, что мы применяем обозначение для семейства устройств, "машин" или "моделей"; такое же обозначение было введено для грамматик. Когда мы говорим о языках, порождаемых устройствами, то применяем обозначения .)

Мы будем говорить также, что граф G' является G-раскрашиваемым (или раскрашиваемым в соответствии с G), если G' принадлежит семейству (G). Семейство графов называется цветосемейством, если оно равно (G) для некоторого графа G.

Введенная выше терминология мотивируется следующими соображениями. Для n≥2 обозначим через K_n полный граф с n вершинами, т. е. граф, в котором две любые различные вершины соединены ребром. Очевидно, что граф G n-раскрашиваем в обычном для теории графов смысле тогда и только тогда, когда G принадлежит (K_n). Таким образом, знаменитая теорема о четырех красках утверждает, что каждый плоский граф принадлежит (K₄)!

С другой стороны, в обычной теории раскрашивания графов рассматриваются только семейства (K_n). Данное выше определение является намного более общим, поскольку рассматриваются раскрашивания, соответствующие произвольному графу.

Например, рассмотрим циклический граф C_n с n вершинами, т. е. граф, ребра которого образуют замкнутый цикл. Следующая иллюстрация показывает, как граф C₇ раскрашивается в соответствии с C₅.

Таким образом, C₇ принадлежит (C₅). Интуитивно, раскраска, соответствующая C₅, означает такое использование цветов 1-5, что сохраняется соседство в C₅: если вершина окрашена в цвет 1, то соседние с ней вершины могут быть окрашены в цвета 2 или 5, но не в 3 или 4 и т. д. Легко видеть также, что обратная раскраска невозможна: C₅ не принадлежит (C₇).

Теперь обсудим значение введенных выше понятий теории графов с точки зрения теории языков. Отождествим конечный язык F с грамматикой G, заданной продукциями

и будем также говорить об интерпретации языка F, равно как о семействе языков (F), порожденных F. Очевидно, язык L принадлежит (F) тогда и только тогда, когда L является подмножеством σ(F) для некоторой конечной подстановки σ, такой, что σ(a) является конечным множеством букв для каждой буквы a и a≠b всегда влечет σ(a)∩σ(b) = ∅. Отождествление языка F и грамматики G проведено в соответствии с леммой 7.3, которая показывает, что семейство языков, определяемое грамматикой, порождающей конечный язык, полностью определяется этим языком.

Приведенным вариантом G₁ графа (орграфа) G называется граф (орграф), полученный из G удалением всех изолированных вершин, т. е. вершин, не связанных никаким ребром (стрелкой). Ясно, что (G₁) = (G). (Напомним наше соглашение о том, что все графы и орграфы содержат хотя бы одно ребро или стрелку, и поэтому, удаляя изолированные вершины, мы никогда не удалим все вершины.)

Конечный язык называется графоподобным, если он содержит только слова длины 2 и не содержит никаких слов вида a². С каждым графоподобным языком можно естественным образом ассоциировать некоторый орграф: каждая буква обозначает вершину, а слова языка - стрелки. Например, является орграфом, соответствующим языку {ab, bc, ca}. Слово ab показывает, что существует стрелка, ведущая из a в b.

Обратно, приведенный вариант произвольного орграфа определяет графоподобный язык, единственный с точностью до переименования букв. Таким образом, между графоподобными языками и приведенными орграфами существует взаимно-однозначное соответствие^*.

^* (Это соответствие можно продолжить, сопоставив произвольным конечным языкам размеченные ориентированные гиперграфы.- Прим. перев.)

Указанная выше связь между графами и языками в явном виде выражается следующей леммой (доказательство леммы опускается, ибо она сразу следует из определений).

Лемма 7.9. Если F и F' - графоподобные языки, а G и G' - соответствующие им орграфы, то F' является интерпретацией F тогда и только тогда, когда G' является интерпретацией G.

Лемма 7.9 выражает коммутативность диаграммы

Таким образом, для произвольной интерпретации F' (графоподобного) языка F ассоциированный с F орграф является одновременно интерпретацией орграфа G, ассоциированного с F. Этот результат показывает также, что все вопросы относительно иерархий семейств орграфов можно свести к вопросам относительно семейств, порожденных графоподобными языками, и обратно.

Что касается графов, то их взаимосвязь с теорией языков аналогична. Единственное отличие состоит в том, что в данном случае мы вынуждены ограничиться рассмотрением "коммутативных языков", т. е. таких языков, в которых порядок букв несуществен. Например, не имеет значения, какое из слов ab и ba принадлежит языку: и то и другое означает, что в ассоциированном графе вершины a и b соединены ребром. Понятие интерпретации можно определить и для коммутативных языков. Например, коммутативный язык

является интерпретацией коммутативного языка

в соответствии с тем, что циклический граф C₇ является интерпретацией ₆. Вообще, для графов и коммутативных языков справедливо утверждение, соответствующее лемме 7.9.

Лемма 7.9 и ее аналог для графов показывают, что результаты леммы 7.1 можно применять к графам и орграфам. В частности, если G' - интерпретация G (где и G, и G' являются или графами, или орграфами), то (G')⊂(G).

Вернемся теперь к обсуждению цветосемейств. Вспомним определения C_n и K_n, а также приведенный выше пример с C₅ и C⁷. В соответствии с этими определениями легко установить следующую дважды бесконечную иерархию:

Очевидно, что для всех п имеет место равенство (C'_2n) = (K₂). (Оно соответствует тому обстоятельству, что граф является 2-раскрашиваемым в том и только том случае, когда он не содержит циклов нечетной длины.) Таким образом, существенно, что графы в (7.7), являющиеся циклами, имеют нечетную длину.

Иерархия (7.7) является линейной иерархией цветосе-мейств (в общем случае цветосемейства не упорядочены линейно) . В действительности можно доказать следующий (сильнейший из возможных) результат о несравнимости.

Рассмотрим произвольный граф G. Если все циклы в G имеют четную длину, то (G) = (K₂). Это выводится, например, с помощью критерия 2-раскрашиваемости. Действительно, так как мы предположили, что все рассматриваемые графы имеют хотя бы одно ребро, то (K₂) содержится в каждом цветосемействе.

Итак, пусть в G имеется цикл нечетной длины 2n+1. Поскольку для некоторого m граф G является m-раскрашиваемым, получаем включения

(C_2n+1)⊆(G)⊆(K_m).(7.8)

Значит, каждый граф G либо удовлетворяет (7.8), либо (G) = (K₂). В частности, каждое семейство (G) может быть несравнимо только с конечным числом семейств (C_i) и конечным числом семейств (K_j). Оба этих числа могут быть произвольно большими, как показывает следующая теорема (ее доказательство опускается, так как необходимый для него теоретический аппарат выходит за рамки этой книги^*).

^* (Необходимые для доказательства сведения читатель может почерпнуть, например, из книг [О*], гл. 14, и [X*], гл. 12.- Прим. перев.)

Теорема 7.10. Для любых натуральных чисел m≥3 и n≥2 существует граф G, обладающий следующими свойствами:

(i) G является интерпретацией графа K_m, но не графа K_m-1;

(ii) C_2n-1 не является интерпретацией графа G.

Следовательно, каждое из цветосемейств

(C_2n-1), ..., (C₃) (K₃), ..., (K_m-1)

несравнимо с (C).

По аналогии с грамматическими семействами мы назовем цветосемейство (G₂) последователем цветосемейства (G₁), если (G₁)(G₂) и не существует цветосемейства (G₃), такого, что

(G₁)(G₃)(G₂).

Напомним, что мы исходили из того, что в каждом графе имеется хотя бы одно ребро. Если отказаться от этого предположения, то, исследуя граф K₁ с одной вершиной и без ребер, можно непосредственно убедиться в том, что (K₂), является последователем (K₁).

Этот тривиальный пример является единственным возможным примером последователя, т. е. цветосемейства образуют плотное частично упорядоченное множество. Последнее обстоятельство используется в упр. 9 и 13; примеры последователей среди семейств орграфов приводятся в упр. 10.

Наконец, мы хотим показать, как подобные идеи можно применить в более общей ситуации. Например, можно рассмотреть размеченные графы, и в частности конечные (недетерминированные) автоматы, введенные в гл. 2. Предположим далее, что в каждом автомате имеются ровно одна начальная вершина q₁ и ровно одна заключительная вершина q₂, q₁≠q₂ и что ни одна стрелка не ведет в q₁ и не выходит из q₂. Предоставляем читателю проверить, что автоматом такого типа может быть представлен каждый λ-свободный регулярный язык.

Пусть автоматы G' и G относятся к описанному выше типу. Мы назовем автомат G' интерпретацией автомата G, если существует такое отображение φ множества вершин G' в множество вершин G и такое отображение ψ множества символов, помечающих стрелки G', в множество символов, помечающих стрелки G, что для каждой помеченной символом а стрелки из x в y в графе G' найдется помеченная символом ψ(a) стрелка из φ(x) в φ(y) в графе G и, кроме того,

и никакие другие вершины графа G' не отображаются посредством ψ в q₁ или q₂. Это определение расширяет определение, данное выше: оно требует также, чтобы сохранились пометки стрелок, равно как и начальная, и заключительная вершины.

С другой стороны, каждому такому автомату G можно сопоставить конечный язык F, состоящий из слов вида qaq'. (Слово qaq' показывает, что в автомате G некоторая помеченная символом а стрелка ведет из вершины q в q'. Предполагается, что в G нет изолированных вершин.) Пусть F и F' - два таких конечных языка; мы скажем, что F' является интерпретацией F, если (i) F' является подмножеством σ(F), где σ - конечная подстановка, определенная, как и выше, и (ii) aσ(q₁)= {q₁}, σ(q₂) = {q₂} и вершины q₁, q₂ больше нигде не встречаются в области определения σ.

Нетрудно проверить коммутативность следующей диаграммы:

Эту диаграмму, как и предыдущую, можно записать, начиная с F.

Обозначим через семейство языков, представимых интерпретациями графа G. Следует подчеркнуть, что семейства (F) не находятся больше во взаимно-однозначном соответствии с семействами (G). Может иметь место (G₁) = (G₂), хотя соответствующие семейства (F₁) и (F₂) несравнимы.