Страница 45 номер 65, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Гамильтоновым путём в графе называется цепь, проходящая ровно по одному разу через каждую вершину. Рассмотрите рисунок 28 и постройте гамильтонов путь в графе: а) тетраэдра; б) куба; в) октаэдра.
Гамильтонов путь — цепь, проходящая ровно по одному разу через каждую вершину: все вершины перечислены в таком порядке, что каждые две соседние соединены ребром и ни одна не повторяется.
а) Граф тетраэдра — полный граф на вершинах \(A\), \(B\), \(C\), \(D\) с 6 рёбрами, любые две вершины соединены. Годится \(ABCD\): \(AB\), \(BC\), \(CD\) — рёбра графа, вершины различны, и это все вершины.
б) У графа куба восемь вершин и 12 рёбер: четырёхугольник \(AB\), \(BC\), \(CD\), \(DA\), четырёхугольник \(KL\), \(LM\), \(MN\), \(NK\) и связывающие их рёбра \(AK\), \(BL\), \(CM\), \(DN\). Годится \(ABCDNKLM\): соседние пары \(AB\), \(BC\), \(CD\), \(DN\), \(NK\), \(KL\), \(LM\) — рёбра графа, все восемь вершин различны.
в) У графа октаэдра шесть вершин и 12 рёбер: \(MA\), \(MB\), \(MC\), \(MD\), \(NA\), \(NB\), \(NC\), \(ND\) и рёбра четырёхугольника \(AB\), \(BC\), \(CD\), \(DA\). Годится \(ABMCDN\): соседние пары \(AB\), \(BM\), \(MC\), \(CD\), \(DN\) — рёбра графа, все шесть вершин различны.
Ответ: гамильтоновым путём является, например, а) \(ABCD\); б) \(ABCDNKLM\); в) \(ABMCDN\).
Гамильтоновым путём в графе называется цепь, проходящая ровно по одному разу через каждую вершину. Рассмотрите рисунок 28 и постройте гамильтонов путь в графе: а) тетраэдра; б) куба; в) октаэдра.
Гамильтонов путь — это цепь, проходящая ровно по одному разу через каждую вершину. Значит, надо перечислить все вершины графа в таком порядке, чтобы каждые две соседние в этом списке были соединены ребром и ни одна вершина не повторилась.
а) Граф тетраэдра — полный граф на четырёх вершинах \(A\), \(B\), \(C\), \(D\): любые две вершины соединены ребром, всего рёбер 6. Поэтому годится любой порядок вершин, например \(ABCD\). Проверим: \(AB\), \(BC\), \(CD\) — рёбра графа; вершины \(A\), \(B\), \(C\), \(D\) различны, и это все вершины графа. Значит, \(ABCD\) — гамильтонов путь.
б) У графа куба восемь вершин. Рёбра \(AB\), \(BC\), \(CD\), \(DA\) образуют один четырёхугольник, рёбра \(KL\), \(LM\), \(MN\), \(NK\) — другой, а рёбра \(AK\), \(BL\), \(CM\), \(DN\) связывают эти четырёхугольники попарно; всего рёбер 12.
Обойдём сначала первый четырёхугольник: \(A\), \(B\), \(C\), \(D\) — рёбра \(AB\), \(BC\), \(CD\) в графе есть. Из вершины \(D\) перейдём по ребру \(DN\) ко второму четырёхугольнику и обойдём его: \(N\), \(K\), \(L\), \(M\) — рёбра \(NK\), \(KL\), \(LM\) в графе есть. Получилась последовательность \(ABCDNKLM\): каждые две соседние вершины соединены ребром, все восемь вершин различны, и это все вершины графа. Значит, \(ABCDNKLM\) — гамильтонов путь.
в) У графа октаэдра шесть вершин и 12 рёбер: \(MA\), \(MB\), \(MC\), \(MD\), \(NA\), \(NB\), \(NC\), \(ND\) и рёбра четырёхугольника \(AB\), \(BC\), \(CD\), \(DA\). Не соединены только пары \(M\) и \(N\), \(A\) и \(C\), \(B\) и \(D\).
Возьмём последовательность \(ABMCDN\). Соседние пары в ней — \(AB\), \(BM\), \(MC\), \(CD\), \(DN\), и все пять являются рёбрами графа. Вершины \(A\), \(B\), \(M\), \(C\), \(D\), \(N\) различны, и это все шесть вершин графа. Значит, \(ABMCDN\) — гамильтонов путь.
Выделим найденные пути на чертежах.
Ответ: гамильтоновым путём является, например, а) \(ABCD\); б) \(ABCDNKLM\); в) \(ABMCDN\).
