Укладка графа на плоскости

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Граф обладает укладкой в пространстве [math]L[/math], если он изоморфен графу, вершинами которого являются некоторые точки пространства, а ребрами — жордановы кривые, соединяющие соответствующие вершины, причем


1) кривая, являющаяся ребром не проходит через другие вершины графа, кроме вершин, которые она соединяет;
2) две кривые, являющиеся ребрами, пересекаются лишь в вершинах, инцидентных одновременно обоим этим ребрам.


Соответствующий граф, составленный из точек пространства и жордановых кривых из [math]L[/math], называют укладкой исходного графа.


Определение:
Граф называется планарным, если он обладает укладкой на плоскости. Всевозможные укладки планарных графов на плоскости будем называть плоскими графами.


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


Литература

  • Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы