Дискретная математика. Ерош И.Л - 106 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

106
5.16. Правильные многогранники
Для любого плоского графа число ребер можно сосчитать третьим
способом – учитывая число ребер, ограничивающих каждую грань.
Пусть j (k) – количество граней степени k. Под гранью степени k
будем понимать грань, ограниченную ровно k ребрами. Тогда число ре
бер графа можно определить по формуле
P = 1/2(j(2)·2 + j(3)·3 + j(4)·4 + j(5)· 5 + …). (5.4)
Так, для графа рис. 5.11 j(3) = 2; j(4) = 2; j(5) = 2; j(6) = 0; j(7) = 0;
j(8) = 1; j(9) = 0;… Поэтому P = 1/2(2·3+2·4+2·5+1·8) = 16. Прямой
пересчет дает это же значение.
Формула (5.4) пригодна и для графов с кратными ребрами и вложен
ными петлями. Так, для графа рис. 5.12 получаем: j(1) = 2; j(2) = 5;
j(3) = 2; j(4) = 1; j(8) = 1. Тогда P = 1/2(2·1+5·2+2·3+1·4+1·8) = 15.
Возьмем произвольный плоский граф G и будем строить двойствен
ный ему граф G
*
по следующему правилу. В центре каждой грани плос
кого графа G выберем точку и назовем ее вершиной двойственного гра
фа G
*
. Соединим все новые вершины ребрами так, чтобы каждое ребро
двойственного графа G
*
пересекало в точности одно ребро (общее для
двух граней) исходного графа G.
Результаты сравнения характеристик исходного графа G и двой
ственного ему графа G
*
поместим в табл. 5.16.
Определение 1. Граф G, у которого все степени вершин равны r, на+
зывается однородным.
Определение 2. Однородный
граф G, у которого двойствен+
ный ему граф G
*
тоже одноро+
ден, называется правильным
графом. Правильным графам
соответствуют правильные
многогранники.
Рассмотрение свойств пра
вильных графов и, соответствен
но, правильных многогранников
приводит к табл. 5.17.
Поскольку каждому много
граннику соответствует плос
кий граф и каждый плоский
граф может быть нарисован на
плоскости так, чтобы все его
ребра были прямыми, приведем
Таблица 5.17
rr*
BPГ
огоньливарппиТ
акиннаргогонм
33464 рдэартеТ
348 216 буK
35 020321рдэакедоД
436 218 рдэаткО
53 210302рдэасокИ
ыртемараП
афарг
йындохсИ
фарг G
йынневтсйовД
фарг G*
нишреволсиЧBГ=*B
реберолсиЧPP=*P
йенарголсиЧГB=*Г
Таблица 5.16

Страницы