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

Связными являются все графы, встречающиеся

Связными являются все графы, встречающиеся

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

Сделаем еще одно интересное наблюдение: если соединить сере­дины соседних граней тетраэдра, то снова получим тетраэдр. Про та­кие многогранники говорят, что они являются самодвойственными.

Если соединить середины соседних граней куба, то получим окта­эдр. И наоборот: если соединить середины соседних граней октаэдра, то получим куб. Про такие многогранники говорят, что они являются

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

двойственными друг другу. Оказывается, что додекаэдр и икосаэдр также являются двойственными друг другу.

Полезно также обсудить граф футбольного мяча. В частности, вы­яснить, является ли футбольный мяч правильным многогранником, понять, какие у него грани и т. д.

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

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

Если граф не является связным, то его можно разбить на так называемые компоненты связности, то есть на связные подграфы, между которыми нет ребер. Для этого можно взять вершину графа и посмотреть, до каких вершин можно из нее добраться по ребрам — это и будет компонента связности этой вершины. Формализовать эту конструкцию можно с помощью понятия отношения эквивалент­ности.

Задача 11. Какие из графов задач 1, 2 и 3 связны?

Ответ. Связными являются все графы, встречающиеся в первой за­даче. Во второй задаче связными являются все графы, кроме графов без ребер и следующих: