Укладка графа на плоскости — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Добавлены категории)
Строка 17: Строка 17:
 
==Литература==
 
==Литература==
 
*  Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы
 
*  Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Укладки графов ]]

Версия 09:28, 21 октября 2010

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


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


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


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


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


Литература

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