Хроматическое число и хроматическая функция графа

18. Вершинами графа перестановок являются перестановки n чисел {1, 2, 3,  , n}. Вершины, отличающиеся транспозицией, содединяются ребрами. Будет ли граф перестановок плоским при n≥ 3 ? Найти хроматическое число графа перестановок чисел

{1, 2, 3,  , n}.

19. Булев куб B_n размерности n состоит из вершин (₁ , ₂ ,    , _n ), _i {0, 1}, где две вершины смежны если они отличаются одной компонентой _i . Найти хроматическое число графа B_n .

20.Найти хроматическую функцию графа An , приведенного на рис. 4.16.

Рис. 4.16. Граф A_n

21. Найти хроматическую функцию полного графа K_n .

22. Найти хроматический многочлен графа, изображением которого является буква «A».

23. Найти хроматический многочлен графа C₅ .

Ответ: f(q) = q⁵ – 5q⁴ + 10q³ – 10q² + 4q.

24. Найти хроматические многочлены и хроматические числа графов, приведенных на рис. 4.17.

Рис. 4.17. Примеры графов

25. Соседние области флага имеют различные цвета. Сколькими способами можно раскрасить в семь цветов изображенный на рис. 4.18 флаг?

Рис. 4.18. Пример флага

17. Соседние области флага должны иметь различные цвета. Сколькими способами можно раскрасить в qцветов флаг на рис. 4.19?

Рис. 4.19. Пример флага

27. Найти число раскрасок граней куба, при которых соседние грани имеют различные цвета. Число цветов не превосходит 7.

3. Построить рекуррентное соотношение для хроматических многочленов и найти эти многочлены.

4. Найти хроматическое число графа, полученного удалением одного ребра из полного графа K_n . Двух ребер. Трех ребер, составляющих треугольник.

Ответ: n-1, n-1, n-2.

Деревья

18. Является ли дерево двудольным графом?

19. Код Прюфера нумерованного дерева с nвершинами состоит из последовательностиn-2чисел, принимающих значения от1доn.Упаковка. Код Прюфера нумерованного дерева сnвершинами строится следующим образом. В цикле находится висячая вершина с наименьшим номером. Номер вершины смежной с найденной записывается в последовательность. Цикл повторяетсяn2раза.Распаковка. Выписываем множествоB={1, 2, 3, ∙ ∙ ∙, n}, гдеnравно длине кода плюс два. Устанавливаем начальное множество ребер дереваT= . Далее выполняются действия:

for (i=1; i<n1; i++)

{

b= min { kB: ka_j  j ≥ i} ;

добавить к T ребро {b,a_i} ;

B = B \ {b} ;

}

Распаковать и упаковать следующие коды:

1. 4445577

2. 24446

3. 77321

4. 12579213

20. Найти число максимальных поддеревьев графа K₄.

21. Найти все максимальные поддеревья графа, полученного удалением одного ребра из графа K₄ . Ответ приведен на рис.4.20.

Рис. 4.20. Максимальные поддеревья графаK₄

5. Конечные частично упорядоченные множества

5.1. Диаграмма Хассе частично упорядоченного множества

Напомним, что ориентированным графом называется пара (V,A), состоящая из множестваVи подмножестваAVV. Элементы изAназываются стрелками, а изV– вершинами. Для стрелки(u,v)вершинаuназывается началом, а изv– концом.

Пусть (X,) – частично упорядоченное множество. Множество]x,y[ = {vX: x<v<y}называется открытым интервалом с концамиxиy.

Определение 1. Диаграммой Хассеназывается ориентированный граф(V,A)сV=XиA={(u,v): u<vи]u,v[ = }.