Л

Левостороннее дерево(Left linear tree)
- бинарное дерево, определяемое рекурсивно следующим образом:
а) одновершинное дерево есть Л.Д.;
б) бинарное дерево, у которого правое поддерево является пустым, а левое - Л.Д., есть также Л.Д.
Литература:[Евстигнеев-Касьянов]

Лемма о рукопожатиях(Handshake's lemma)
- Сумма степеней всех вершин графа - четное число, равное удвоенному числу ребер.
Свое название лемма получила из-за следующей интерпретации: поскольку в каждом рукопожатии участвуют две руки, то при любом числе рукопожатий общее число пожатых рук (при этом каждая рука учитывается столько раз, во скольких рукопожатиях она участвовала). Лемма справедлива также для мульти- и псевдографов.
Литература:[Лекции]

Лес(Forest)
- неориентированный граф без циклов. Компонентами связности леса являются деревья.
Литература:[Лекции]

Лес обхода(Round forest)
- для данного обхода H графа G = (X,U) такая его часть (X,Z), что Z содержит каждое такое ребро u [include] U, что среди вершин, расположенных в H между вершинами p = H(i) и q = H(j), где i [leq] j и u = (p,q), нет вершин, соединенных ребром с вершиной H(j).
Литература:[Евстигнеев-Касьянов]

Лес ориентированный - см. Ориентированный лес.

Лес ориентированный покрывающий - см. Лес-каркас.

Лес стягивающий - то же, что и Лес-каркас.

Лес-каркас(Spanning forest)
- часть орграфа в виде ориентированного леса (быть может, с одновершинными компонентами), содержащая все вершины исходного орграфа.
Литература:[Евстигнеев-Касьянов]

Линейная компонента(Linear component)
- гамак C управляющего графа G, обладающий следующими свойствами: начальная и конечная (если она есть) вершины C принадлежат каждому пути из входа G в его выход; из конечной вершины гамака C не достижима в G начальная вершина гамака C; C не содержит собственного подграфа, который был бы гамаком и обладал первыми двумя свойствами.
Литература:[Касьянов], [Евстигнеев-Касьянов]

Линейное дерево(Linear tree)
- дерево с двумя концевыми вершинами, т.е. дерево в виде простой цепи.
Литература:[Свами-Тхуласираман]

Линейный подграф графа(Linear subgraph of a graph)
- линейный подграф орграфа, получаемого из исходного графа заменой каждого ребра парой противоположно ориентированных дуг.
Литература:[Харари]

Линейный подграф орграфа(Linear subgraph of a directed graph)
- суграф орграфа G, в котором у каждой вершины полустепень исхода и полустепень захода равны 1; таким образом, такой подграф содержит непересекающийся остовный набор простых контуров.
Литература:[Харари]

Линейный участок(Basic block)
- простой путь P = (p[_1], ... , p[_r]), r [geq] 1, в управляющем графе такой, что полустепени исхода всех вершин, кроме p[_r], и полустепени захода всех вершин, кроме p[_1], равны 1.
Литература:[Касьянов], [Евстигнеев-Касьянов]

F-линия(F-line)
- для данных нумерации F и отрезка [i,j] множество тех вершин подграфа, порожденного всеми вершинами, F-номера которых принадлежат [i,j], из которых в подграфе F-достижимы его выходные вершины.
Литература:[Касьянов], [Евстигнеев-Касьянов]

Лист(Leaf)
- 1. Максимальный связный подграф, не содержащий мостов. 2. Висячая вершина выходящего ордерева.
Литература:[Лекции], [Евстигнеев-Касьянов]

Локально конечный граф(Locally finite graph)
- орграф, у которого каждая вершина имеет конечные полустепени захода и исхода.
Литература:[Берж]

Локально конфлюентная СПТ - см. Система переписывания термов.

Локально ограниченный граф(Locally restricted graph)
- граф с заданной степенной последовательностью.
Литература:[Харари-Палмер]

Локально счетный граф(Locally countable graph)
- бесконечный граф, все вершины которого имеют счетную степень.
Литература:[Уилсон]

Луч - то же, что и Линейный участок.

F-луч(F-ray)
- для данной нумерации F управляющего графа G луч (p[_1], ... , p[_r]), r [geq] 1, для которого справедливо соотношение F(p[_i]) = F(p[_i][_+] [_1]) - 1.
Литература:[Касьянов], [Евстигнеев-Касьянов]