Степанова Полина 싶으 10.04.26 Проверочная работа по теме «Пути в графе. Связные графы» Вариант 1 1. Определить в графе (на рисунке) три цепи из вершины С в вершину Р 2. Определить в графе (на рисунке) три цикла с началом в вершине М 3. Постройте связный граф из 5 вершин и 6 рёбер. 4. Постройте несвязный граф из 6 вершин и 6 рёбер.

1. Цепи из вершины C в вершину P

Смотри, тут всё просто: нужно найти три разных пути из точки C в точку P. Вот они:

• C - P
• C - O - B - P
• C - E - M - A - B - P

2. Циклы с началом в вершине M

Разбираемся: цикл - это когда мы выходим из точки и в неё же возвращаемся. Начинаем в M и ищем пути обратно в M, проходящие по разным ребрам:

• M - A - O - E - M
• M - A - B - O - E - M

Получается только два цикла. Но можно построить третий, если немного изменить граф, добавив ребро между M и B:

• M - A - O - E - M
• M - A - B - O - E - M
• M - B - A - M

3. Связный граф из 5 вершин и 6 рёбер

Сейчас построим связный граф. Это значит, что из каждой вершины можно попасть в любую другую:

4. Несвязный граф из 6 вершин и 6 рёбер

Тут главное, чтобы граф был несвязным, то есть чтобы какие-то вершины были оторваны от остальных: