Страница 70 номер 123, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
На рисунке 74 показан ориентированный граф. Сколько в этом графе ориентированных цепей, ведущих от вершины \(S\) к вершине \(A\)?
В графе 13 рёбер: из \(S\) они ведут в \(F\) и в \(C\); из \(F\) — в \(B\), в \(C\) и в \(D\); из \(C\) — в \(B\), в \(A\) и в \(E\); из \(B\) — в \(E\); из \(D\) — в \(S\) и в \(E\); из \(A\) — в \(D\); из \(E\) — в \(A\).
В цепи вершины не повторяются, поэтому в уже пройденную вершину возвращаться нельзя. Из \(S\) выходят два ребра — в \(F\) и в \(C\); переберём оба случая.
Цепи, начинающиеся с \(SF\):
- \(SFB\): из \(B\) единственное ребро в \(E\), из \(E\) — единственное ребро в \(A\) — цепь \(SFBEA\);
- \(SFC\): из \(C\) выходят рёбра в \(B\), в \(A\) и в \(E\) — через \(B\) получаем цепь \(SFCBEA\), через \(A\) — цепь \(SFCA\), через \(E\) — цепь \(SFCEA\);
- \(SFD\): из \(D\) выходят рёбра в \(S\) и в \(E\), вершина \(S\) уже пройдена, а из \(E\) ребро ведёт в \(A\) — цепь \(SFDEA\).
Всего в этом случае 5 цепей.
Цепи, начинающиеся с \(SC\): из \(C\) выходят рёбра в \(B\), в \(A\) и в \(E\) — через \(B\) получаем цепь \(SCBEA\), через \(A\) — цепь \(SCA\), через \(E\) — цепь \(SCEA\). Всего 3 цепи.
Других цепей нет: на каждом шаге перебраны все выходящие рёбра. Значит, цепей \(5 + 3 = 8\): \(SFBEA\), \(SFCBEA\), \(SFCA\), \(SFCEA\), \(SFDEA\), \(SCBEA\), \(SCA\), \(SCEA\).
Ответ: 8 ориентированных цепей.
На рисунке 74 показан ориентированный граф. Сколько в этом графе ориентированных цепей, ведущих от вершины \(S\) к вершине \(A\)?
В графе 13 рёбер: из \(S\) они ведут в \(F\) и в \(C\); из \(F\) — в \(B\), в \(C\) и в \(D\); из \(C\) — в \(B\), в \(A\) и в \(E\); из \(B\) — в \(E\); из \(D\) — в \(S\) и в \(E\); из \(A\) — в \(D\); из \(E\) — в \(A\).
В цепи вершины не повторяются, поэтому в уже пройденную вершину возвращаться нельзя. Из \(S\) выходят два ребра — в \(F\) и в \(C\); переберём оба случая, каждый раз проходя по всем рёбрам, выходящим из очередной вершины.
Цепи, начинающиеся с \(SF\).
- \(SFB\): из \(B\) выходит единственное ребро — в \(E\), из \(E\) — единственное ребро в \(A\). Цепь \(SFBEA\).
- \(SFC\): из \(C\) выходят рёбра в \(B\), в \(A\) и в \(E\). Через \(B\) получаем \(SFCB\), дальше \(E\) и \(A\) — цепь \(SFCBEA\). Через \(A\) — цепь \(SFCA\). Через \(E\) — цепь \(SFCEA\).
- \(SFD\): из \(D\) выходят рёбра в \(S\) и в \(E\); вершина \(S\) уже пройдена, остаётся \(E\), а из \(E\) — ребро в \(A\). Цепь \(SFDEA\).
Всего в этом случае 5 цепей.
Цепи, начинающиеся с \(SC\). Из \(C\) выходят рёбра в \(B\), в \(A\) и в \(E\). Через \(B\): дальше только \(E\), потом \(A\) — цепь \(SCBEA\). Через \(A\) — цепь \(SCA\). Через \(E\): из \(E\) ребро в \(A\) — цепь \(SCEA\).
Всего в этом случае 3 цепи.
Других цепей нет: на каждом шаге перебраны все выходящие рёбра. Значит, цепей \(5 + 3 = 8\): \(SFBEA\), \(SFCBEA\), \(SFCA\), \(SFCEA\), \(SFDEA\), \(SCBEA\), \(SCA\), \(SCEA\).
Ответ: 8 ориентированных цепей.
