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

UptoLike

ВУЗ: 

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

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

Рубрика: 

104
11
Рис. 5.10. Проецирование плоского графа на сферу
Возьмем какойнибудь плоский граф. Например, если взять неплос
кий граф типа А и исключить из него одно ребро, он станет плоским
(рис. 5.9, a).
Не меняя обозначений вершин и связей между ними, можно добить
ся того, чтобы все ребра стали прямыми (рис. 5.9, b).
Любой плоский граф может быть спроецирован на сферу.
Для проецирования плоского графа на сферу возьмем плоскость и
на ней изобразим плоский граф G. Примерно в центре этого графа ус
тановим сферу и соединим все вершины плоского графа G с северным
полюсом сферы N (рис. 5.10).
Отметим точки пересечения этих линий со сферой и соединим их
между собой. Получим граф на сфере. Если через выделенные точки
провести плоскости, мы получим некоторую объемную фигуру, вписан
ную в сферу. Таким образом, каждому плоскому графу будет соответ
ствовать некоторый многогранник. Обратным проецированием мы
каждому многограннику, вписанному в сферу, можем сопоставить не
который плоский граф. Последняя процедура используется в карто
графии.
5.15. Теорема Эйлера о соотношении числа вершин,
ребер и граней плоского графа
Рассмотрим некоторый плоский граф (рис. 5.11).
Назовем замкнутую область плоского графа, ограниченную ребра
ми и не имеющую внутри себя никаких фрагментов графа, гранью. Гра
a) b)
Рис. 5.9. Пояснение к теореме о прямых ребрах плоского графа

Страницы