ГДЗ 132 Рассмотрите граф на рисунке 31. Запишите какие-нибудь три цепи, ведущие из вершины A в вершину B. Цепь — это ...
132 Рассмотрите граф на рисунке 31. Запишите какие-нибудь три цепи, ведущие из вершины A в вершину B.
Цепь — это путь в графе, проходящий через различные вершины, в котором рёбра не повторяются. На рисунке 31 можно выделить следующие цепи от вершины \(A\) к вершине \(B\):
- Прямой путь через нижнюю вершину \(F\): A — F — B.
- Путь через верхние вершины \(C\), \(D\) и нижнюю \(F\): A — C — D — F — B.
- Путь по верхнему контуру через вершины \(C\), \(D\), \(E\): A — C — D — E — B.
Ответ:
1) A — F — B; 2) A — C — D — F — B; 3) A — C — D — E — B.
133 Найдите на рисунке 31 три разных цикла.
Цикл — это замкнутый путь, в котором начало и конец совпадают, а промежуточные вершины не повторяются. На рисунке 31 можно найти следующие циклы:
- Левый замкнутый контур: A — C — D — F — A.
- Центральный треугольник: D — E — F — D.
- Правый треугольник: E — B — F — E.
Ответ:
1) A — C — D — F — A; 2) D — E — F — D; 3) E — B — F — E.
ГЛАВА IV. ГРАФЫ