Ответ:
Считая цепями последовательности смежных рёбер, в которых допускается повторное прохождение ребра, получаем 39.
Подсчитаем число таких последовательностей по длине. Для каждого шага суммируем числа способов прийти в вершину за предыдущий шаг по всем входящим рёбрам. Параллельные рёбра считаются отдельно, петля в E даёт один способ остаться в E.
Числа способов прийти в вершины A, B, C, D, E, G соответственно:
- за 0 рёбер: 1, 0, 0, 0, 0, 0;
- за 1 ребро: 0, 1, 1, 1, 0, 0;
- за 2 ребра: 3, 0, 3, 3, 1, 1;
- за 3 ребра: 6, 4, 12, 13, 2, 4;
- за 4 ребра: 29, 8, 45, 46, 10, 15.
За пятое ребро в B можно попасть из A по ребру AB или из E по ребру EB. Значит, число цепей равно 29 + 10 = 39.
Если в используемом учебнике цепью называют последовательность без повторения рёбер, подсчёт будет другим; здесь использовано значение, допускающее повторное прохождение рёбер.
Считая цепями последовательности смежных рёбер, в которых допускается повторное прохождение ребра, получаем 39.
Подсчитаем число таких последовательностей по длине. Для каждого шага суммируем числа способов прийти в вершину за предыдущий шаг по всем входящим рёбрам. Параллельные рёбра считаются отдельно, петля в E даёт один способ остаться в E.
Числа способов прийти в вершины A, B, C, D, E, G соответственно:
- за 0 рёбер: 1, 0, 0, 0, 0, 0;
- за 1 ребро: 0, 1, 1, 1, 0, 0;
- за 2 ребра: 3, 0, 3, 3, 1, 1;
- за 3 ребра: 6, 4, 12, 13, 2, 4;
- за 4 ребра: 29, 8, 45, 46, 10, 15.
За пятое ребро в B можно попасть из A по ребру AB или из E по ребру EB. Значит, число цепей равно 29 + 10 = 39.
Если в используемом учебнике цепью называют последовательность без повторения рёбер, подсчёт будет другим; здесь использовано значение, допускающее повторное прохождение рёбер.
