eSci.Ru logo
Данный ресурс создан для поддержания извечного стремления человека к сияющим вершинам разума
Главная > Задачи > Вузовские контрольные > МГУ, ВМиК, 2 семестр, дискретная математика, к/р 2 (графы)
МГУ, ВМиК, 2 семестр, дискретная математика, к/р 2 (графы)

Задача 1

Построить все попарно неизоморфные графы G, у которых n_1 \left( G \right) = n_2 \left( G \right) = n_3 \left( G \right) = 2 и \forall i > 3:n_i  = 0.


Задача 2

Определить, планарен ли изображенный граф. Если да, правильно реализовать его на плоскости, если нет, то обосновать это, используя теорему Понтрягина-Куратовского. Найти хроматическое число и хроматический индекс этого графа. Дать обоснование нижней оценке хроматического числа и хроматического индекса. Если реальные значения больше, то это надо доказать перебором или другим способом.


Задача 3

Все вершины дерева имеют степени ≤4, при этом висячих вершин ровно 92, а n_3  = n_4. Сколько в дереве n_3?


Задача 4

Заменив прочерки в наборе (0__010__11_1) на 0 и 1, получить все возможные коды укладок корневых деревьев на плоскости. Изобразить их.


Задача 5

Построить все попарно неизоморфные орграфы, содержащие 3 вершины и 3 дуги.

Копирование материалов сайта допускается только с указанием ссылки