Информационно-коммуникационные технологии
в педагогическом образовании

ХРОМАТИЧЕСКАЯ ЕДИНСТВЕННОСТЬ ПОЛНЫХ ДВУДОЛЬНЫХ ГРАФОВ

Раздел: Материалы I Всероссийской очно-заочной практической конференции "Математика, физика, информатика:проблемы и перспективы современного образования" (Новокузнецк, февраль 2016)

Журнал: Проблемы и перспективы современного математического образования

6 июня 2016 г.

Авторы: Качесов Н. Е. , Куликов Н. А.

Н. Е. Качесов, Н. А. Куликов

ХРОМАТИЧЕСКАЯ ЕДИНСТВЕННОСТЬ ПОЛНЫХ ДВУДОЛЬНЫХ ГРАФОВ

В своей работе Р. Рид ставит следующую проблему:

1. Охарактеризовать  хроматические многочлены графов.

2. Сформулировать необходимые и достаточные условия, при которых два графа хроматически эквиваленты.

Поскольку эти проблемы оказались очень трудными, то в теории графов на подступах к решению этих проблем возникли  такие направления исследований:

а) изучение хроматически единственных графов;

б) изучение классов хроматически эквивалентных  графов.

В работе Дмитриев И.Г. доказал, что  графом, хроматически эквивалентным k-дереву, является k-дерево. Более того, он указал явный вид хроматического многочлена k-дерева.

В работе Лоринс и Уайтхед доказали хроматическую единственность циклов и графов, близких к циклическим (в частности? модифицированных колес).

Цель настоящей работы – изучение хроматической единственности графов. Основным результатом работы является следующая теорема:

Полный двудольный граф  является хроматически  единственным графом  для любых .

Эта теорема доказана при помощи критерия хроматической эквивалентности графов.

В пункте 2 сформулированы основные определения и факты; в пункте 3 изложено доказательство теоремы.

ОСНОВНЫЕ ПОНЯТИЯ И ФАКТЫ

В работе под графом всегда понимается неориентированный граф без петель и кратных ребер.

Неориентированный граф без петель и кратных ребер  состоит из множества  вершин и множества,  ребер.

Граф  такой, что   называется дополнением графа X (см. рисунок 1): 

Если , то вершины a и b называются смежными. Два ребра называются смежными, если они инциндентны одной вершине. Полный граф  – это граф с p вершинами, каждая пара которых cсоединена ребром (граф  называется также треугольником). Объединение графов  и  называется графом , для которого  и . Соединение графов  и  называется графом  для которого и , где T состоит из ребер, соединяющих каждую вершину графа  с каждой вершиной графа .

Подмножество  замкнуто тогда и только тогда, когда его множество представимо в виде , для некоторых попарно пересекающихся полных подграфов  графа X.

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

Высотой элемента a полурешетки с наименьшим элементом o называется длина максимальной цепи между элементами o и a.

Высота элемента  в полурешетке замкнутых подмножеств графа равна .

Подмножество A решетки H называется подрешеткой если выполняется условие

Подрешетка J решетки A называется идеалом, если для любых элементов элемент  лежит в J.

Идеал, порожденный одним элементом, называется главным. Подмножество t решетки L называется коидеалом, если из  того, что  .

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

Раскраска графа – приписывание цветов вершинам и ребрам графа, обладающее определенными свойствами.

Правильная раскраска – раскраска вершин графа, при которой любые смежные вершины окрашены в разные цвета.

Хроматическое число X(G) – наименьшее число цветов, достаточное для правильной вершиной раскраски графа.

Однозначно-раскрашиваемый граф.

Каждая X(G) раскраска графа G порождает разбиение множества его вершин на X(G)  одноцветных классов (множество вершин одного цвета).

Если X(G)=n и каждая раскраска графа G порождает одно и то же разбиение множества V(G), то G однозначно раскрашиваем.

Упорядочной  – раскраской помеченного графа называют правильную раскраску вершин этого графа, использующую λ или меньше цветов. При этом две произвольные упорядочные  – раскраски считаются различными, если по крайней мере одной помеченной вершине графа прописывают различные цвета.

Через  обозначают число упорядоченных – раскрасок графа. Функцию называют хроматическим многочленом графа. Например, любую вершину полного графа можно окрасить способами. Для второй вершины можно взять любой из оставшихся  цветов и т.д. В результате получим, что .

Выражение  называется убывающим факториалом длины p и обозначается .

Определим связь раскраски графа с его полурешеткой.

Пусть граф G имеет n вершин. Каждому замкнутому подмножеству графа соответствует единственная раскраска этого графа. Замкнутые подмножества образуют полурешетку H(G). Тогда наименьшему элементу соответствует n раскраска, атомам из H(G) соответствует (n-1) - раскраска, элементам высоты два из H(G) соответствует (n-2) - раскраска и т.д.

Если h высота полурешетки тогда

Пусть H стандартная полурешетка высоты   – число элементов высоты i в H, , назовем характеристическими числами полурешетки H.

Многочлен вида  назовем характерестическим многочлена полурешетки H.

Последовательность чисел  назовем характеристическим  спектром или просто спектром полурешетки.

Графы x и  называются хроматически эквивалентными, если .

Критерий хроматической эквивалентности графов.

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

Граф называется хроматически единственным, если из  следует .

Граф  называется полным двудольным графом.

ХРОМАТИЧЕСКАЯ ЕДИНСТВЕННОСТЬ ПОЛНОГО ДВУДОЛЬНОГО ГРАФА

Теорема. Полный двудольный граф  является хроматически единственным графом для любых .

Доказательство.

Предположим, что выполняются следующие необходимые условия хроматической эквиваленции графа X графу :

X – двудольный граф.

Покажем, что . Полным двудольным графом, не изоморфным графу граф X быть не может, т.к. равенство

 имеет место только при i=0 и i-k.

Пусть X двудольный граф, полученный из  удалением  ребер, и . Полурешетки замкнутых подмножеств  и H имеют высоту . Если каждая вершина подграфа  графа  соединена с некоторой вершиной подграфа  или наоборот, то в полурешетке H будет по крайней мере два элемента высоты (см. схему 1),

т.е. спектры полурешеток и H будут различными, а это противоречит хроматической эквивалентности графов и X.

Предположим, что в каждом из подграфов и графа  нет вершины смежных со всеми вершинами другого подграфа.

Покажем, что в этом случае число элементов высоты  в этих полурешетках различно. В полурешетке     элементов указанной высоты (см. числа Стирлинга второго рода).

Наибольшее число замкнутых подмножеств будет в том случае когда s вершин подграфа соединены с вершинами из подграфа , где .

Минимальным число ребер, соединяющих подграфы и в может быть . Рассмотрим первый случай . Тогда максимальное число элементов высоты будет  , t – это число замкнутых подмножеств, полученное с использованием ребер, соединяющих и в . Для t будет выполняться неравенство . В этом случае число замкнутых подмножеств будет больше, чем в исходном графе .

Рассмотрим второй случай . Максимальное число замкнутых подмножеств высоты будем искать  в следующем случае:

s вершин, где , подграфа соединены с вершинами (каждая с каждой) подграфа . Замкнутые подмножества в этом случае будут иметь вид  (см. схему 3).

            Какая-то часть s вершин подграфа , а какая-то с (S+1) вершинами (см. схему 4).

Тогда максимальное число замкнутых подмножеств будет , следовательно t будет иметь следующие границы: .

Число замкнутых подмножеств у графа X равно .

Число s будет наибольшим, если наибольшее и m наименьшее, т.е. если .

 

Рассмотрим случай, когда , тогда .

Если ,  и .

Рассмотрим случай, когда  тогда .

 и

.

При любых m, k и i<k>.</k>

Таким образом полурешетки  и  имеют различные спектры, поэтому . Значит,  – хроматически единственный граф.

ИНФОРМАЦИОННЫЕ ИСТОЧНИКИ

1.      Read R.C., An introduction to chromatic polynomials.// J. Comtin Theory, – 1968. –  A. –  №1 – P. 52-71.

2.      Дмитриев И.Г. Характеризация классов k-деревьев. Сб. «Методы дискретного анализа в оценках сложности управляющих систем».// Вып. 38. Новосибирск: Наука, – 1982. – С. 9-18.

3.      Loerinc B.,Whitehead E.G., Cromatic polynomals for regular graphs and modified wheels. // J. Comtin Jhory, – 1981. B(31).– № 1.–Р. 54-61.

4.      Зыков А.А. Теория конечных графов. Новосибирск: Наука,  – 1969.

5.      Айгнер М. Комбинаторная теория. М: Мир,–1982.

6.      Харари Ф. Теория графов. М: Мир, –1973.