Е

Евклидова задача Штейнера(Steiner's problem in Euclid plane)
- соединить точки множества P на плоскости прямыми линиями так, чтобы минимизировать суммарную длину отрезков. Если не допускаются пересечения любых двух линий в точках вне заданного множества P, то задача сводится к одной из задач определения кратчайшей связывающей сети эквивалентного графа на |P| вершинах с матрицей весов, вычисленных как евклидово расстояние между точками множества P. Если допускается на плоскости введение дополнительных "искусственных" вершин (называемых точками Штейнера), то вес (длину) кратчайшей связывающей сети можно уменьшить соответствующим подбором точек. Таким образом, для решения задачи Штейнера можно добавить в любых местах плоскости столько точек Штейнера, сколько необходимо для построения наикратчайшего дерева, стягивающего множество из P точек. Получающееся наикратчайшее дерево называют наикратчайшим деревом Штейнера.
Литература:[Кристофидес]

Емкостная сложность алгоритма (Space complexity of a algorithm)
- один из параметров, характеризующих алгоритм; определяется величиной объема памяти, использованного алгоритмом, как функцией размерности задачи. См. временная сложность.
Литература:[Ахо-Хопкрофт-Ульман], [Липский]

Емкость графа (Graph capacity)
параметр графа, выражемый формулой

[Formula-8]
где G[^k] - сильная степень графа. Введен К.Шенноном в связи с задачами из теории информации.
Литература:[Лекции], [Берж]}