Конспект лекции. Def. Говорят, что граф вкладывается в данное пространство, если все вершины и ребра которого состоят из точек данного пространства

Планарные графы

Def. Говорят, что граф вкладывается в данное пространство, если все вершины и ребра которого состоят из точек данного пространства, причем кривые, изображающие ребра, не пересекаются.

Def. Граф называется планарным, если он может быть уложен на плоскости.

Def. Геометрическая фигура, являющаяся изображением планарного графа, называется плоским графом.

Например, пирамида является планарным графом.

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

Теорема 1. Для всякого связного плоского -графа с f гранями справедливо равенство (формула Эйлера): .

Раскраски графов

Def. Раскраска вершин графа G называется правильной, если любые две смежные вершины окрашены в разные цвета.

Дата добавления: 2014-01-20