65 Гамильтоновым путём в графе называется цепь, проходящая по одному разу через каждую вершину. Рассмотрите рисунок 28 Гамильтонов путь в графе: а) тетраэдра; б) куба; в) октаэдра

Решение:

Гамильтонов путь — это путь в графе, который проходит через каждую вершину ровно один раз.

а) Тетраэдр: У тетраэдра 4 вершины. Можно построить гамильтонов путь, например, пройдя по рёбрам, соединяющим вершины последовательно. Пример пути: A → B → C → D.

б) Куб: У куба 8 вершин. Гамильтонов путь существует. Пример пути: можно обойти все вершины по периметру, затем перейти на следующий слой и обойти его, а затем соединить два слоя.

в) Октаэдр: У октаэдра 6 вершин. Гамильтонов путь существует. Пример пути: можно обойти вершины правильным образом, например, начав с вершины, пройдя по двум смежным, затем через центральную вершину и так далее, посетив каждую вершину один раз.

Ответ: Гамильтонов путь существует для графа тетраэдра, куба и октаэдра.