ГДЗ Проверочная работа по теме «Пути в графе. Связные графы» Вариант 1 1. Определить в графе (на рисунке) три цепи из...

Вариант 1

1. Определить в графе (на рисунке) три цепи из вершины C в вершину P.

Цепь — это путь, в котором все рёбра различны. Исходя из представленного графа, можно выделить следующие цепи:

1. C — P (прямой путь по ребру)
2. C — B — P (путь через вершину B)
3. C — B — O — E — P (путь через вершины B, O и E)

2. Определить в графе (на рисунке) три цикла с началом в вершине M.

Цикл — это замкнутая цепь, которая начинается и заканчивается в одной и той же вершине.

1. M — A — B — O — M (цикл через вершины A, B, O)
2. M — E — O — M (треугольный цикл через вершины E и O)
3. M — A — O — M (треугольный цикл через вершины A и O)

3. Постройте связный граф из 5 вершин и 6 рёбер.

Чтобы граф был связным, между любыми двумя его вершинами должен существовать путь. Минимальное количество рёбер для связности 5 вершин — 4 (дерево). Нам нужно 6 рёбер, что добавит в граф циклы.

Пример построения:
Возьмём 5 вершин: 1, 2, 3, 4, 5.
Соединим их последовательно в кольцо (5 рёбер): (1-2), (2-3), (3-4), (4-5), (5-1).
Добавим шестое ребро между любыми двумя несмежными вершинами, например: (1-3).

Список рёбер итогового графа:

1. (1, 2)
2. (2, 3)
3. (3, 4)
4. (4, 5)
5. (5, 1)
6. (1, 3)