1. Необходимые определения и формулировки теорем.

   1. *В чем состоит задача о раскраске вершин графа?

   2. *Каков алгоритм решения задачи о раскраске графа?

   3. *В чем состоит задача о раскраске ребер графа?

   4. *Что Вы знаете о хроматическом индексе?

2. Задачи для усвоения материала.

1. Для каждого из предложенных графов найдите правильные раскраски рёбер и вершин.

]

К практическому занятию 16

Итоговое повторение раздела 3. Контрольная работа № 3.

1. Основные вопросы.

1. Что такое матрица смежности орграфа и каким свойством обладает матрица смежности неориентированного графа?

2. Что называется деревом, ордеревом и как они связаны между собой?

3. Что такое бинарное ордерево и как оно применяется к кодам Шеннона-Фано?

4. Как строится префиксный код бинарного ордерева?

5. Как строится код Харари?

6. Как строится код Прюфера?

7. Какие три способа обхода бинарного ордерева Вы знаете (с примером)?

8. Что называется атомом, списком и как связаны деревья со списками?

2. Контрольная работа.

Вариант 0

1. Пронумеровав произвольным образом вершины и дуги, найти матрицы смежности и инцидентности графа.

2. Определить, является ли число 357 кодом Харари.

3. Построить префиксный код бинарного ордерева

4. Построить код Прюфера

5. Обойти бинарное ордерево тремя способами.

6. Вопрос по теории 3-го раздела.

К практическому занятию 17 Итоговое повторение материала семестра. Анализ наиболее типичных ошибок контрольных работ 1, 2, 3.

1. Анализ контрольной работы.

2. Основные вопросы.

1. Что называется объединением, пересечением, разностью, симметрической разностью множеств, дополнением множества?

2. Что такое инъективное, сюръективное, биективное отображение (с примерами)?

3. Что Вы знаете о мощности множества двоичных наборов и о мощности множества всех подмножеств данного множества?

4. Что такое правило произведения (с примером)?

5. Что такое перестановки и что Вы знаете о числе перестановок (с примером)?

6. Что такое сочетания и что Вы знаете о числе сочетаний (с примером)?

7. Что такое размещения и что Вы знаете о числе размещений (с примером)?

8. Что такое перестановки с повторениями и что Вы знаете об их числе (с примером)?

9.Что такое рефлексивное, симметричное, транзитивное отношение, отношение эквивалентности и каково его основное свойство?

10. Что такое рефлексивное, симметричное, транзитивное отношение, отношение эквивалентности и каково его основное свойство?

11. Что такое отношение нестрогого порядка, строгого порядка?

12. Что такое орграф, граф, вершина, дуга, ребро, путь, цепь, контур, цикл?

13. Каков алгоритм решения задачи о кратчайшем пути в невзвешенном графе?

14. Каков алгоритм решения задачи о кратчайшем пути во взвешенном графе?

15. Что такое эйлерова цепь (цикл), у каких графов они существуют?

16. В чем состоит формула Эйлера и для каких объектов она верна?

17. Как выглядят непланарные графы № 1, № 2, типов 1, 2 и в чем состоит теорема Куратовского-Понтрягина?

18. Что такое матрица смежности орграфа и каким свойством обладает матрица смежности неориентированного графа?

19. Что называется деревом, ордеревом и как они связаны между собой?

20. Что такое бинарное ордерево и как оно применяется к кодам Шеннона-Фано?

21. Как строится префиксный код бинарного ордерева?

22. Как строится код Харари?

23. Как строится код Прюфера?

24. Какие три способа обхода бинарного ордерева Вы знаете (с примером)?

25. Что называется атомом, списком и как связаны деревья со списками?