И

Иерархия вложенных альтов(Nested set of alts)
- множество нетривиальных альтов A = {H[_i]} управляющего графа таких, что для любых двух альтов либо их пересечение пусто, либо один целиком содержится в другом.
Альт H[_i] [include] A непосредственно вложен в альт H[_j] [include] A относительно A, если H[_i] [subset] H[_j] и в A не существует такого альта H[_k], что H[_i] [subset] H[_k] [subset] H[_j]. Альт H[_i] [include] A называется внутренним альтом относительно A, если в A не существует альтов, непосредственно вложенных в H[_i], и внешним альтом относительно A, если в A не существует альта, в который H[_i] непосредственно вложен.
Последовательность уграфов G[_0], G[_1], ..., G[_r] называется представлением уграфа G в виде иерархии вложенных альтов A (A-граф, A-представление уграфа G), если G[_0] = G, G[_r] - тривиальный уграф и для любого i уграф G[_i] получается из G[_i-1] стягиванием в вершины всех внешних альтов относительно [bigcup] {A[_j] : 1 [geq] j [geq] i }, где A[_j] - множество всех внутренних альтов относительно A \ [bigcup] {A[_s]: 1 [leq] s < ; j}.
Литература:[Касьянов]

Иерархия вложенных зон(Nested set of zones)
- множество зон {S[_i]} управляющего графа, таких, что для любых двух зон либо их пересечение пусто, либо одна целиком содержится в другой. Частным случаем является иерархия вложенных контуров.
Литература:[Евстигнеев], [Касьянов]

Изолированная вершина - см. Вершина изолированная.

Изоморфизм графов(Graph isomorphism)
- биекция [phi]: V(G) [rarr] V(H) множества вершин графа G на множество вершин графа H, сохраняющая отношение смежности; другими словами, для любых вершин u и v графа G их образы [phi](u) и [phi](v) смежны в H тогда и только тогда, когда u и v смежны в G.
Отношение изоморфизма графов является эквивалентностью, т.е. оно симметрично, транзитивно и рефлексивно. Следовательно, множество всех графов разбивается на классы так, что графы из одного класса изоморфны, а графы из разных классов не изоморфны. Задача установления изоморфизма графов есть NP-полная проблема.
Литература:[Лекции], [Зыков]

Изоморфные графы(Isomorphic graphs)
- графы, между которыми установлено отношение изоморфизма; другими словами, графы G и H изоморфны (G [cong] H), если существует изоморфизм графа G на граф H (и, следовательно, H на G.
Литература:[Зыков], [Лекции]

Изоморфные матроиды(Isomorphic matroids)
- матроиды M[_1] = (E[_1], [ii][_1]) и M[_2] = (E[_2], [ii][_2]) такие, что между множествами E[_1] и E[_2] существует биекция [phi], сохраняющая независимость, или, другими словами, если множество I [subset] E[_1] независимо в M[_1], то соответствующее множество [phi](I) [subset] E[_2] независимо в M[_2].
Литература:[Лекции]

Изоморфные орграфы(Isomorphic directed graphs)
- орграфы такие, что между их основаниями существует изоморфизм, сохраняющий порядок вершин на каждой дуге.
Литература:[Лекции]

Изоморфные помеченные графы(Isomorphic labeled graphs)
- графы, для которых существует изоморфизм, сохраняющий распределение меток в этих графах.
Литература:[Лекции]

Инвариант (графа)(Invariant (of a graph)
- число, связанное с графом G (функция f(G), определенная на множестве всех графов), которое принимает одно и то же значение на любом графе, изоморфном G. К инвариантам относятся, например, число вершин в графе, число ребер, плотность, хроматическое число, число Хадвигера и др. В качестве инварианта графа можно рассматривать не одно число, а систему чисел, в частности вектор или кортеж.
Литература:[Зыков, а]

Индекс компонент(Component index)
- (относительно простой цепи L) число компонент связности в графе G \ L, получающимся из исходного графа G удалением всех вершин цепи L и всех инцидентных им ребер. И.к. относительно множества вершин A - это число компонент связности в графе, получаемом из исходного удалением вершин из множества A и всех инцидентных им ребер.
Литература:[Оре]

Индекс связности вершины(Connective index)
- число i(v) компонент связности в графе, получаемом из исходного графа удалением вершины v и всех инцидентных ей ребер.
Литература:[Оре]

Индекс хроматический - см. Хроматический индекс.

Индуктивный граф(Inductive graph)
- орграф, в котором каждый путь [mu] = [x[_1], x[_2], ... ] допускает мажоранту, т.е. если для каждого пути [mu] существует такая вершина z, что z [geq] x[_i], x[_i] [include] [mu].
Литература:[Берж]

Интервал(Interval)
- альт управляющего графа, в котором начальная вершина (вершина, в которую заходит дуга извне альта) принадлежит каждому его контуру. В силу своего строения интервал допускает аранжировку и, следовательно, сводим.
Литература:[Касьянов], [Евстигнеев]

Инфиксный порядок обхода дерева - то же, что и Внутренний порядок обхода дерева.

Информационное множество(Data set)
- множество, элементам которого ставятся во взаимно однозначное соответствие так называемые ключи - информационные элементы без внутренней структуры. Замена прямого поиска по элементу поиском элемента по ключу, имеющему более простую природу и связанному определенными отношениями с другими ключами, позволяет сделать поиск (и другие операции над множеством) более эффективным. Другая причина введения такого понятия как ключ состоит в том, что содержательная трактовка элементов И.м. (в силу сложной их природы) может зависеть от характера работы с И.м., и иногда возникает необходимость в зависимости от трактовки сопоставлять элементам различные системы ключей. Как правило, ключи в И.м. вводятся таким образом, что имеется простая процедура порождения ключа по информационному элементу (например, в качестве ключей могут рассматриваться некоторые части информационных элементов).
По типу отношений между ключам И.м. распадаются на две группы. К первой относятся И.м. с линейной упорядоченностью ключей, и этот тип порождает такие структуры, как упорядоченный массив, поисковое дерево и взвешенный массив. Вторая группа связана с разбиением всей совокупности ключей на классы эквивалентных, и этот тип порождает такие структуры, как таблицы с оглавлением и перемешанные таблицы.
Литература:[Касьянов-Поттосин]

Информационный граф(Information graph)
- орграф информационных связей в программе; вершины его суть операнды (полюса) - входы (аргументы) и выходы (результаты) операторов, дуги соединяют полюса r и a, если в управляющем графе между оператором с выходом r и оператором с входом a существует маршрут, который реализует (подтверждает) информационную связь между r и a.
Литература:[Ершов], [Касьянов]

Инцидентность(Incidenty)
- отношение между ребром (дугой) и его концевыми вершинами, т.е. ребро e = (a,b) инцидентно вершинам a и b и вершины a, b инцидентны ребру e = (a,b). См. также Инцидентор, Матрица инцидентности.
Литература:[Лекции]

Инцидентор(Incidentor)
- 1. Предикат P(v,w,e) такой, что P = 1 тогда и только тогда, когда e = (v,w). Используется, например, при задании графа списком его ребер, сопоставляя каждому ребру пару вершин - концов ребра. 2. Пара элементов (v,e) такая, что вершина v инцидентна ребру e.
Литература:[Зыков]

Искаженность графа(Skewness of a graph)
- наименьшее число sk(G) ребер, удаление которых приводит к планарному графу.
Литература:[Лекции]

Источник(Source)
- 1. То же, что и вход орграфа. 2. Вершина орграфа, из которой можно достичь все остальные вершины. 3. В теории потоков на сетях вершина, из которой потока выходит больше, чем заходит.
Литература:[Берж]

Исходящая дуга(Outcoming arc)
- дуга, начало которой есть рассматриваемая вершина или оно принадлежит рассматриваемому множеству (в последнем случае говорят о дуге, исходящей из данного множества).
Литература:[Лекции]