Н

Надграф(Supergraph)
- граф по отношению к любому его подграфу.
Литература:[Харари]

Наибольший общий унификатор - см. Задача унификации.

Наибольший поток(Maximum flow)
- поток, величина которого наибольшая среди всех потоков по данной сети. По теореме Форда-Фалкерсона она равна пропускной способности минимального разреза.
Литература:[Берж], [Кристофидес], [Липский]

Наикратчайшее дерево Штейнера(Shortest Steiner's tree)
- дерево наименьшего веса, дающее решение евклидовой задачи Штейнера.
Литература:[Кристофидес]

Накрывающий граф - то же, что и Надграф.

Накрывающее множество вершин(Covering vertex set)
- множество вершин такое, что каждое ребро имеет в нем хотя бы один конец.
Литература:[Оре]

Направленный граф - то же, что и Ориентированный граф.

Наследственное свойство графа(Hereditary property of a graph)
- свойство P графа G такое, что каждый подграф графа G также обладает этим свойством. Примерами наследственных свойств служат несвязность, ацикличность, двудольность, планарность.
Литература:[Харари]

Насыщающая разметка(Acceptable assignment)
- такая стационарная разметка R, что B [sqin] R для любой стационарной разметки B.
Литература:[Касьянов]

Начало дуги - см. Дуга.

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

Недревесность графа(Anarboricity of a graph)
- наибольшее число попарно реберно-непересекающихся подграфов графа G, которые содержат циклы и дают после объединения весь граф G. Наряду с древесностью недревесность образует пару инвариантов: инвариант покрытия (древесность) и инвариант упаковки (недревесность).
Литература:[Харари-Палмер]

Независимое множество вершин - то же, что и Внутренне устойчивое множество.

Независимое множество вершин гиперграфа(Independent vertex set of a hypergraph)
- множество вершин гиперграфа, не содержащее ребер.
Литература:[Лекции]

Независимое множество ребер графа - то же, что и Паросочетание.

Независимые множества матроида(Independent sets of a matroid)
- семейство [ii] подмножеств элементов из E, удовлетворяющих следующим аксиомам:
(I0) [zero] [include] [ii];
(I1) если X [include] [ii] и Y [subseteq] X, то Y [include] [ii];
(I2) если X, Y - элементы из [ii] такие, что |X| = |Y| + 1, то существует x [include] X \ Y такой, что Y [cup] {x} [include] [ii].
Подмножество из E, не принадлежащее [ii], называется зависимым.
Так как (I0) следует из (I1), то в качестве системы аксиом можно взять (I1) (I2). Кроме того, существуют варианты аксиомы (I'2), (I''2), эквивалентные (I2):
(I'2) Если X, Y [include] [ii] и |Y| < ; |X|, то в X \ Y существует элемент x такой, что Y [cup] {x} [include] [ii].
(I''2) Если X, Y [include] [ii] и |Y| < ; |X|, то в X существует такое подмножество Z, что Y [cup] Z [include] [ii] и |Y [cup] Z| = |X|.
Литература:[Лекции], [Welsh]

Независимые циклы(Independent circuits)
- циклы, соответствующие вектор-циклы которых линейно независимы.
Литература:[Берж]

Неориентированное дерево - см. Дерево.

Неориентированный граф - см. Граф.

Неплотность графа(Undensity)
- число [alpha][_0](G) ([epsilon](G)) вершин в наибольшем внутренне устойчивом (независимом) множестве.
Другие названия - число независимости, число внутренней устойчивости.
Литература:[Лекции]

Неподвижная вершина(Immovable (fixed)
- vertex) вершина, не подобная ни одной другой вершине графа.
Литература:[Харари]

Непомеченный граф - то же, что и Абстрактный граф.

Непосредственный доминатор - то же, что и Непосредственный обязательный предшественник.

Непосредственный обязательный предшественник(Immediate dominator)
- для некоторой вершины a такой ее обязательный предшественник b, что a [neq] b и b - ближайший к a (в смысле порядка вхождений в простой путь из начальной вершины управляющего графа до a) из обязательных ее предшественников.
Другое название - непосредственный доминатор.
Литература:[Ахо-Хопкрофт-Ульман], [Касьянов], [Евстигнеев-Касьянов]

Непосредственный обязательный преемник(Immediate postdominator)
- для некоторой вершины a такой ее обязательный преемник b, что a [neq] b и b - ближайший к a (в смысле порядка вхождений в простой путь из a до конечной вершины управляющего графа) из обязательных ее преемников.
Другое название - непосредственный доминатор.
Литература:[Ахо-Хопкрофт-Ульман], [Касьянов], [Евстигнеев-Касьянов]

Непосредственный постдоминатор - то же, что и Непосредственный обязательный преемник.

Неразделимый граф(Non-separable graph)
- связный, непустой, не имеющий точек сочленения граф.
См. Блок.
Литература:[Харари]

Неразложимый граф - то же, что и Неразделимый граф.

Несводимый граф(Irreducible graph)
- двудольный граф с множеством вершин V = S [cup] T, имеющий в точности два наименьших вершинных покрытия M[_1] , M[_2], причем или M[_1] [cap] S и M[_2] [cap] T пусты, или M[_1] [cap] T и M[_2] [cap] T пусты.
Литература:[Харари]

Несвязный орграф(Unconnected directed graph)
- орграф, не обладающий даже свойством слабой связности.
Литература:[Харари]

Несепарабельный граф - то же, что и Неразделимый граф.

Несравнимые вершины(Incomparable vertices)
- вершины v и w графа G такие, что ни v < ; w, ни w < ; v относительно частичного порядка, порождаемого графом G.
Литература:[Берж]

Нечетная компонента(Odd component)
- (1) Компонента связности графа с нечетным числом вершин. (2) Пусть множество вершин графа G разбивается на подмножества S, T и U. Рассмотрим компоненту C подграфа G[U], индуцированного множеством U. Пусть f - функция из множества V(G) вершин графа в множество неотрицательных целых чисел. Компоненту C будем называть нечетной (или четной) в соответствии с нечетностью (четностью) индекса четности

[Formula-9]
где [lambda](T,b) есть число ребер, соединяющих вершину b с вершинами множества T. Для T = [zero] и частного случая f [equiv] 1 на всех вершинах понятия нечетной компоненты (1) и (2) совпадают.
Литература:[Харари], [Tutte]

Нетеровая СПТ - см. Система переписывания термов.

Нумерация вершин(Numbering)
- биекция F множества вершин V, |V| = n, на множество [1 : n].
Литература:[Касьянов],[Евстигнеев-Касьянов]}

Нумерация вершин базисная - см. Базисная нумерация вершин.

Нумерация допустимая - см. Допустимая нумерация.

Нумерация линейная - см. Линейная нумерация.

Нумерация обратная - то же, что и N-нумерация.

Нумерация плоская - см. Плоская нумерация.

Нумерация правильная - см. Правильная нумерация.

Нумерация прямая - то же, что и M-нумерация.

Нумерация разумная - см. Разумная нумерация.

K-нумерация(K-numbering)
- нумерация вершин уграфаG, которая определяется как последний член K[_scn] (n - число вершин в G) последовательности нумераций K[_sc1] , K[_sc2] , ... , K[_scn] , в которой K[_sc1] - обратная нумерация G и для любых i [include] [1,n) и вершин p,q справедливы два свойства: если K[_sci] (p) [include] [1,i), то K[_sci+1] (p) = K[_sci] (p); если K[_sci] (p), K[_sci] (q) [include] [i,n], то K[_sci+1] (p) < ; K[_sci+1] (q) тогда и только тогда, когда либо p [include] K[_sci] [i] и q [nin] K[_sci] [i], либо K[_sci] (p) < ; K[_sci] (q) и {p,q} [subseteq] K[_sci] [i] или {p,q} [cap] K[_sci] [i] = [zero].
Относительно обозначений см. F-область.
Литература:[Касьянов], [Евстигнеев-Касьянов]

L-нумерация(L-numbering)
- нумерация вершин уграфаG, которая определяется как последний член L[_sc0] последовательности нумераций L[_scn] , L[_scn-1] , ... , L[_sc0] , в которой L[_scn] - есть нумерация K и для любых вершин p,q и номера i справедливы следующие два свойства: если L[_sci] (p) < ; i или L[_sci] (p) > i+|L[_sci] [i]|, то L[_sci-1] (p) = L[_sci] (p); если L[_sci] (p), L[_sci] (q) [include] [i,i+|L[_sci] [i]|), то L[_sci-1] (p) < ; L[_sci-1] (q) тогда и только тогда, когда либо p и q имеют один и тот же L[_sci] -ранг в [i,i+|L[_sci] [i]|) и L[_sci] (p) < ; L[_sci] (q), либо L[_sci] -ранг вершины q превышает L[_sci] -ранг вершины p в [i,i+|L[_sci] [i]|).
Относительно обозначений см. F-область.
Литература:[Касьянов], [Евстигнеев-Касьянов]

M-нумерация(M-numbering)
- нумерация вершин в порядке их обхода при поиске в глубину.
Другое название - прямая нумерация.
Литература:[Касьянов], [Евстигнеев-Касьянов]

N-нумерация(N-numbering)
- для данной нумерации M такая нумерация N вершин, что для любых вершин a и b неравенство N(a) < ; N(b) выполняется тогда и только тогда, когда либо вершина b является M-достижимой из a, либо M(b) < ; M(a) и вершина a не является M-достижимой из b.
Другое название - обратная нумерация.
Литература:[Касьянов], [Евстигнеев-Касьянов]}

T-нумерация(T-numbering)
- такая нумерация вершин уграфа, что для некоторой фиксированной его обратной нумерации N справедливы следующие свойства: для любых бивершин p и q: T(p) < ; T(q) тогда и только тогда, когда N(p) < ; N(q); T-номера вершин N-области N[p] вершины p образуют отрезок [T(p),T(p)+|N[p]| - 1].
Литература:[Касьянов], [Евстигнеев-Касьянов]}