АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. B) Отрицательное число.
  2. I Функция
  3. I. Случайные величины с дискретным законом распределения (т.е. у случайных величин конечное или счетное число значений)
  4. II. Умножение матрицы на число
  5. III. ОСНОВНЫЕ АКСИОМЫ ЧИСЛА (ЧИСЛО КАК СУЖДЕНИЕ)
  6. III. Умножение вектора на число
  7. IV. ФУНКЦИЯ И СОСЕДНИЕ КАТЕГОРИИ (ЧИСЛО КАК СУЖДЕНИЕ, УМОЗАКЛЮЧЕНИЕ, ДОКАЗАТЕЛbСТВО И ВЫРАЖЕНИЕ)
  8. IX. ПАДЕНИЕ И СМЕРТЬ ГРАФА РОБЕРТА
  9. N – число измерений.
  10. n – число хромосом, с – число ДНК
  11. N- число ступеней изменения концентраций
  12. Ni – число абонентских номеров для i- ой ТС.

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

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

19. Булев куб Bn размерности n состоит из вершин (e1 , e2 , × × ×, en), ei Î{0, 1}, где две вершины смежны если они отличаются одной компонентой ei. Найти хроматическое число графа Bn.

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

Рис. 4.16. Граф An

 

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

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

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

Ответ: f(q) = q5 – 5q4 + 10q3 – 10q2 + 4q.

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

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

 

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

 

   
   

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

 

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

 

     
 
 

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

 

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

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

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

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


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)