Страница 44 номер 62, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Перечислите все цепи, связывающие вершины \(M\) и \(N\), в графе, изображённом на рисунке 26.
Рисунок 26
Цепь — путь без повторяющихся вершин. Перебор ведём по первому ребру цепи, выходящему из вершины \(M\), отбрасывая на каждом шаге рёбра в уже пройденные вершины.
а) Рёбра графа: \(MA\), \(MQ\), \(MT\), \(AQ\), \(BC\), \(BW\), \(UW\), \(QN\), \(NT\). Из вершины \(M\) выходят три ребра — \(MA\), \(MQ\), \(MT\).
С ребра \(MA\): кроме \(M\), вершина \(A\) соединена только с \(Q\), а из \(Q\) непройденной остаётся только \(N\) — цепь \(MAQN\).
С ребра \(MQ\): шаг в \(N\) даёт цепь \(MQN\); шаг в \(A\) даёт \(MQA\), но из \(A\) рёбра ведут только в пройденные \(M\) и \(Q\), и до \(N\) такая цепь не доходит.
С ребра \(MT\): кроме \(M\), вершина \(T\) соединена только с \(N\) — цепь \(MTN\).
Вершины \(B\), \(C\), \(U\), \(W\) лежат в другой компоненте связности, а \(K\), \(P\), \(F\) изолированы, поэтому в цепь из \(M\) в \(N\) они попасть не могут. Цепей ровно три: \(MAQN\), \(MQN\), \(MTN\).
б) Рёбра графа: \(MG\), \(AU\), \(PK\), \(PT\), \(WG\), \(WB\), \(WN\), \(GN\), \(KR\), \(BN\), \(TR\). Из вершины \(M\) выходит единственное ребро \(MG\).
Из \(G\) непройденными остаются \(W\) и \(N\): шаг в \(N\) даёт цепь \(MGN\).
Шаг в \(W\) даёт \(MGW\); из \(W\) шаг в \(N\) даёт цепь \(MGWN\), а шаг в \(B\) даёт \(MGWB\), откуда единственное продолжение — в \(N\): цепь \(MGWBN\).
Цепей ровно три: \(MGN\), \(MGWN\), \(MGWBN\).
Ответ: а) \(MAQN\), \(MQN\), \(MTN\); б) \(MGN\), \(MGWN\), \(MGWBN\).
Перечислите все цепи, связывающие вершины \(M\) и \(N\), в графе, изображённом на рисунке 26.
Рисунок 26
Цепь — это путь без повторяющихся вершин. Значит, нужно перечислить все последовательности вершин, которые начинаются в \(M\), заканчиваются в \(N\), в которых каждые две соседние вершины соединены ребром и ни одна вершина не повторяется.
Чтобы перебор был полным, разберём случаи по первому ребру цепи: каждая цепь начинается с одного из рёбер, выходящих из вершины \(M\). Дальше на каждом шаге проверяем все рёбра, выходящие из текущей вершины, и отбрасываем те, что ведут в уже пройденную вершину. На рисунке два графа, разберём каждый.
а) Рёбра графа: \(MA\), \(MQ\), \(MT\), \(AQ\), \(BC\), \(BW\), \(UW\), \(QN\), \(NT\). Из вершины \(M\) выходят три ребра — \(MA\), \(MQ\) и \(MT\).
Цепь начинается с \(MA\). Кроме \(M\), вершина \(A\) соединена только с \(Q\), поэтому продолжение единственное: \(MAQ\). Из \(Q\) выходят рёбра в \(M\), \(A\) и \(N\); вершины \(M\) и \(A\) уже пройдены, остаётся \(N\). Получилась цепь \(MAQN\).
Цепь начинается с \(MQ\). Из \(Q\) выходят рёбра в \(A\) и в \(N\) (ребро в \(M\) ведёт в пройденную вершину). Шаг в \(N\) даёт цепь \(MQN\). Шаг в \(A\) даёт \(MQA\), но из \(A\) выходят рёбра только в \(M\) и \(Q\) — обе вершины пройдены, и до \(N\) такая цепь не доходит.
Цепь начинается с \(MT\). Кроме \(M\), вершина \(T\) соединена только с \(N\): получается цепь \(MTN\).
Вершины \(B\), \(C\), \(U\), \(W\) лежат в другой компоненте связности, а \(K\), \(P\), \(F\) изолированы, поэтому ни в одну цепь из \(M\) в \(N\) они попасть не могут. Значит, цепей ровно три: \(MAQN\), \(MQN\), \(MTN\).
б) Рёбра графа: \(MG\), \(AU\), \(PK\), \(PT\), \(WG\), \(WB\), \(WN\), \(GN\), \(KR\), \(BN\), \(TR\). Из вершины \(M\) выходит единственное ребро \(MG\), поэтому всякая цепь начинается с него.
Из \(G\) выходят рёбра в \(M\), \(W\) и \(N\); вершина \(M\) пройдена. Шаг в \(N\) даёт цепь \(MGN\).
Шаг в \(W\) даёт \(MGW\). Из \(W\) выходят рёбра в \(G\) (пройдена), \(B\) и \(N\). Шаг в \(N\) даёт цепь \(MGWN\). Шаг в \(B\) даёт \(MGWB\), а из \(B\) выходят рёбра в \(W\) (пройдена) и в \(N\) — получается цепь \(MGWBN\).
Значит, цепей ровно три: \(MGN\), \(MGWN\), \(MGWBN\).
Ответ: а) \(MAQN\), \(MQN\), \(MTN\); б) \(MGN\), \(MGWN\), \(MGWBN\).
