Таблицы Брадиса

Число п называется длиной пути.

Число п называется длиной пути.

Элементы математики в задачах - Г. А. Мерзон

Определение 4. Путем в графе называется конечная последователь­ность вершин и соединяющих их ребер, то есть последовательность вида и0е1 и1е2и2...епип, где иі — вершины графа, а ребро еі соединяет вершины иі—1 и иі. Число п называется длиной пути. Циклом называ­ется путь, в котором первая и последняя вершины совпадают.

Теория графов 1

В графе без кратных ребер (а в этом листке изучаются толь­ко такие графы) путь однозначно восстанавливается по последова­тельности своих вершин, поэтому обычно выписывают именно эту последовательность. Однако технически удобнее включать ребра в определение.

Ш Понятие пути является математическим аналогом инструкции по проезду из одного пункта в другой по сети дорог: такая инструкция должна говорить, через какие промежуточные пункты и по каким дорогам следует ехать.

Определение 5. Граф Г называется гамильтоновым, если в нем су­ществует путь, содержащий каждую вершину ровно один раз.

Задача 10. Докажите, что графы додекаэдра и икосаэдра гамильто­новы.

Ответ. На рисунке изображены графы додекаэдра и икосаэдра.

 

 

-е-

 

Ш Додекаэдр (двенадцатигранник) и икосаэдр (двадцатигранник) являются двумя из пяти возможных правильных многогранников (то есть многогранников у которых все грани равны). Удивительно, но факт: можно доказать, что в пространстве существует всего пять типов правильных многогранников, в то время как на плоскости существует бесконечно много правильных многоугольников. Дока­зывать это утверждение мы сейчас не будем, а ограничимся лишь тем, что перечислим все правильные многогранники: тетраэдр (или треугольная пирамида, или правильный четырехгранник), гексаэдр (или куб, или правильный шестигранник), октаэдр (или правильный восьмигранник), додекаэдр (или правильный двенадцатигранник), икосаэдр (или правильный двадцатигранник).