ГДЗ по вероятности и статистике, 10 класс, Высоцкий, номер 65: Графы и подграфы. Цепи, циклы и деревья

Тетраэдр (правильная треугольная пирамида) имеет 4 вершины. В полном графе K₄, которым является скелет тетраэдра, каждая вершина соединена с каждой другой. Обозначим вершины как A,B,C,D. Поскольку все вершины попарно связаны рёбрами, любой последовательный обход всех четырёх вершин без повторений будет являться допустимым путём.

Построим путь, начиная с вершины A. Перейдём в B, затем в C и завершим в D. Проверим наличие рёбер: (A,B), (B,C), (C,D) существуют в тетраэдре. Все вершины пройдены ровно по одному разу.

Ответ: Путь A→B→C→D.

Куб имеет 8 вершин. Для наглядности обозначим нижнее основание как A,B,C,D (по часовой стрелке), а верхнее основание как N,K,L,M, где N находится над A, K над B, L над C, M над D. Рёбра куба соединяют соседние вершины оснований и соответствующие вершины оснований между собой.

Нам нужно пройти через все 8 вершин. Попробуем «спиральный» или зигзагообразный маршрут. Начнём с A. Идём по нижнему основанию до B, затем поднимаемся вверх к K. Из K идём по верхнему основанию к L, затем спускаемся вниз к C. Из C идём по нижнему основанию к D, затем поднимаемся к M. Осталось попасть в N. Но из M есть ребро только в L (уже посещено) и в D (уже посещено). Такой простой ход не работает напрямую, если мы застрянем.

Попробуем другой вариант, опираясь на ключевую идею решения задачи о кубе. Часто используют путь, который чередует основания или идёт «змейкой». Рассмотрим путь: A→B→C→D→M→L→K→N. Проверим рёбра:

• A-B (ребро основания)
• B-C (ребро основания)
• C-D (ребро основания)
• D-M (вертикальное ребро? Нет, в стандартной нумерации D соединено с C,A и вертикально с M? Если M над D, то да. Допустим, M над D. Тогда D-M есть.)
• M-L (ребро верхнего основания)
• L-K (ребро верхнего основания)
• K-N (ребро верхнего основания)

Другой возможный путь, часто приводимый в примерах: A→B→F→E→H→G→C→D (при другой нумерации). Используем обозначения из условия ответа: A,B,C,D — низ, N,K,L,M — верх. Ответ ABCDNKLM предполагает переходы: A→B, B→C, C→D, D→N? В кубе D не соединено с N (если N над A). Значит, в ключе подразумевается другая нумерация или специфический путь. Давайте построим путь, который точно существует в любом кубе.
Рассмотрим путь: A→B→K→N→M→L→C→D. Проверка рёбер: 1. A-B (есть) 2. B-K (вертикальное, есть) 3. K-N (верхнее основание, есть) 4. N-M (верхнее основание, есть) 5. M-L (верхнее основание, есть) 6. L-C (вертикальное, есть) 7. C-D (нижнее основание, есть) Вершины: A,B,K,N,M,L,C,D. Все различны. Путь найден.

Ответ: Один из возможных путей: A→B→K→N→M→L→C→D.

Октаэдр имеет 6 вершин. Представим его как два основания-треугольника, соединённых боковыми гранями, или как квадратное основание с двумя вершинами сверху и снизу. Удобнее использовать модель: экваториальные вершины A,B,C,D (образуют квадрат) и две полюсные вершины E (верхняя) и F (нижняя). Каждая экваториальная вершина соединена с двумя соседними по квадрату и с обеими полюсными вершинами. Полюсные вершины E и F между собой не соединены.

Нужно обойти все 6 вершин. Начнём с A. Можно пойти в B, затем в C, затем в D. Теперь мы обошли квадрат. Откуда нам уйти дальше? Из D можно пойти в E или F. Допустим, пошли в E. Из E можно пойти только в A,B,C,D, но они уже посещены. Заходим в тупик, если не оставили свободную вершину.

Стратегия: чередовать полюса и экватор или проходить часть экватора, потом полюс, потом остаток. Попробуем путь: A→E→B→F→C→D. Проверка рёбер: 1. A-E (есть, ребро пирамиды) 2. E-B (есть) 3. B-F (есть) 4. F-C (есть) 5. C-D (есть, сторона квадрата) Вершины: A,E,B,F,C,D. Все 6 вершин уникальны. Путь существует.

Ещё один вариант, близкий к ключу ABMCDN (где M,N — полюса): A→B→M→C→D→N. Проверка: 1. A-B (есть) 2. B-M (есть, если M — верхний полюс) 3. M-C (есть) 4. C-D (есть) 5. D-N (есть, если N — нижний полюс) Вершины: A,B,M,C,D,N. Все различны. Этот путь также корректен.

Ответ: Один из возможных путей: A→B→M→C→D→N (где M,N — противоположные вершины).