403
правки
Изменения
м
Нет описания правки
[[Файл:DCEL3.png|200px|thumb|right|(а) РСДС, (б) входы по вершинам head_V [1..n] и (в) входы по граням head_F[1..l]]]
'''ППЛГ''' {{--- }} Плоский прямолинейный планарный граф.
'''РСДС''' {{--- }} Реберный список с двойными связями.
==ППЛГ==
[[Укладка графа на плоскости|Планарный граф]], уложенный на плоскости, принято называть ''плоским''.
'''Плоская укладка планарного графа''' <tex>G = (V, E)</tex> {{--- }} это отображение каждой вершины из <tex>V</tex> в точку на плоскости, а каждого ребра из <tex>E</tex> в простую линию, соединяющую пару образов концевых вершин этого ребра так, чтобы образы ребер пересекались только в своих концевых точках. Хорошо известно, что любой планарный граф можно уложить на плоскости так, чтобы все ребра отобразились в прямолинейные отрезки.
==РСДС==
