Учебник «Вероятность и статистика. 7–9 классы», часть 1, с. 87, §20
№132. Рассмотрите граф на рисунке 31. Запишите какие-нибудь три цепи, ведущие из вершины A в вершину B.
Дано:
граф на рисунке 31: вершины A, B, C, D, E, F
Найти:
три цепи из вершины A в вершину B
Цепь (простой путь) — это путь, в котором вершины и рёбра не повторяются (п. 20). Рёбра графа на рисунке 31: AC, CD, DE, AF, FB, DF, EB, а также «диагонали» AD и FE. Будем идти из A в B по рёбрам и записывать вершины по порядку, следя, чтобы ни одна вершина не встретилась дважды.
1) Самый короткий путь: из A по ребру AF в F, затем по ребру FB в B. Цепь AFB.
2) Пойдём по диагонали: A → D (ребро AD), D → F (ребро DF), F → E (ребро FE), E → B (ребро EB). Цепь ADFEB.
3) Пойдём через верхнюю сторону: A → C, C → D, D → E, E → B. Цепь ACDEB.
Во всех трёх цепях вершины не повторяются, а каждые две соседние буквы соединены ребром графа. Значит, это цепи. Ответ не единственный: всего в этом графе 11 цепей из A в B (это можно проверить перебором), например ADEB или ACDFB.
Ответ: Например, AFB, ADFEB, ACDEB.
