Контрольная работа №2 по дисциплине: Дискретная математика. Онлайн

1. Граф G=(X, U) задан матрицей смежности R.
Выделите в грфе G=(X, U) гамильтонов цикл M.

2. Выделите все подмножества независимых вершин в графе G=(I, U), представленного на рисунке, которым можно при правильной раскраске с минимальным количеством цветов присвоить один и тот же цвет.

3. В графе G (см. рисунок) определите, какой маршрут Mj связывающий вершины 3, 2, не является простой цепью.

4. Выделите в графе L=(I, U) (см. рисунок) все максимальные внутренне устойчивые множества вершин.

5. Для графа L=(I, U) (см. рисунок) укажите значение кардинального числа Q наименьшего множества, входящего в семейство максимальных внутренне устойчивых, вершинам которого нельзя присваивать один и тот же цвет.
Q=6
Q=4
Q=5
Q=2

6. Определите количество компонент связности графа L=(I, U), если после полного выполнения процедуры попарного склеивания вершин его матрица смежности R стала иметь вид следующей таблицы
R 1 2
1 0 2
2 2 1
5
4
1

7. Для графа L=(I, U) (см. рисунок) укажите значение кардинального числа Q наибольшего множества, вершинам которого при условии правильной раскраски можно присваивать один и тот же цвет.
Q=5
Q=4
Q=3
Q=2

8. Как изменится номер № k-ой вершины после склеивания i-ой и j-ой вершин, если №(k) < №(i) и №(k) < №(j)?
Увеличится на 1
Не изменится
Уменьшится на 2
Уменьшится на 1

9. Запишите минимальную форму для выражения П, подмножества вершин которого порождают все максимальные пустые подграфы графа G=(I, U), представленного на рисунке

10. В графе G (см. рисунок) определите максимальный пустой подграф с наименьшим количеством вершин.
Вершины {2, 7}
Вершины {3, 6}
Вершины {5, 2, 4}
Вершины {5, 6}
Вершины {1, 3, 4}

11. Укажите наибольшее подмножество вершин графа L=(I, U) (см. рисунок), которые можно раскрасить одним цветом.
{1368}
{1456}
{24, 27
{1452}

12. Гамильтонов граф в теории графов - это граф, содержащий:
только гамильтонов цикл
только гамильтонову цепь
гамильтонову цепь или гамильтонов цикл
и гамильтонову цепь, и гамильтонов цикл

13. Для графа L=(I, U) (см. рисунок) определите минимальное количество цветов K для правильной раскраски его вершин
K=2
K=3
K=6
K=4

14. Для графа L=(I, U) (см. рисунок) определите минимальное количество цветов K для правильной раскраски его вершин
K=4
K=2
K=3
K=8

Оценка: Зачет

Помогу с вашим вариантом, другой работой или дисциплиной.
E-mail: sneroy20@gmail.com