К

Кактус(Cactus)
- связный граф, в котором нет ребер, лежащих более чем на одном простом цикле; кактус, у которого каждое ребро принадлежит треугольнику, называется треугольным кактусом.
Другое название - дерево Хусими.
Литература:[Харари-Палмер]

Каноническая СПТ - то же, что и Полная СПТ.

Каркас(Spanning tree)
- для данного неориентированного графа суграф в виде дерева. Другие названия - остов, остовное дерево, скелет, стягивающее дерево.
Литература:[Лекции]

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

Карта плоская - см. Плоская карта.

Карта k-раскрашиваемая - см. k-раскрашиваемая карта.

Квадрат графа(Square of a graph)
- граф с тем же множеством вершин, что и исходный, но в котором две вершины смежны, если расстояние между ними в исходном графе не превосходит 2.
Литература:[Харари]

Квадратный корень из графа(Square radical from a graph)
- для данного графа G граф, квадрат которого равен G.
Литература:[Харари]

Квазисильно связный граф(Quasistrongly connected graph)
- орграф, для любой пары вершин v[_1] и v[_2] которого существует вершина v[_3], из которой достижимы v[_1] и v[_2].
Литература:[Свами-Тхуласираман]

Класс цветной - см. Цветной класс.

Клика(Clique)
- подмножество V' графа G, в котором любые две вершины смежны, т.е. порожденный ими подграф G(V') является полным.
Литература:[Лекции]

Кликовое число(Clique number)
- число [phi](G) вершин в наибольшей клике.
Другие названия - густота, плотность.
Литература:[Лекции]

Ключ - см. Информационное множество.

Кобаза матроида(Cobase of a matroid)
- дополнение [B^~] = E \ B базы B [include] [bbb] матроида M = (E,[bbb]).
Литература:[Лекции]

Кограница графа(Coboundary of a graph)
- кограница некоторой его 0-цепи; кограница набора вершин U есть множество всех ребер, соединяющих вершины из U с вершинами, не входящими в U. Очевидно, что каждая кограница есть разрез. Всякий коцикл является минимальной ненулевой кограницей. Множество всех кограниц графа называется пространством коциклов графа.
Литература:[Харари]

Кограничный оператор(Coboundary operator)
- оператор [delta], относящий 0-цепям 1-цепи в соответствии с правилами
а) [delta] - линейный оператор;
б) если v - вершина графа, то [delta]v = [summa][epsilon] [_i]x[_i], где [epsilon][_i] = 1, если только ребро x[_i] инцидентно v.
Литература:[Харари]

Код дерева(Code of a tree)
- слово в некотором алфавите, сформированное согласно заданному порядку обхода вершин дерева и составленное по определенному правилу из количественных характеристик и признаков вершин, а также ограничителей. Различают коды с дублированием номеров вершин, коды, свободные от повторений, коды с использованием ограничителей, уровневые коды, ротационные коды бинарных деревьев, коды Закса, Ли, Прюфера, Гапта и др.
Литература:[Евстигнеев-Касьянов]

Кодерево(Cotree)
- а) для заданного каркаса T - суграф в G, содержащий только те ребра графа G, которые не принадлежат T; б) для данного графа G кодерево некоторого каркаса T.
Литература:[Харари]

Козависимое множество матроида(Codependent set of a matroid)
- для заданного матроида зависимое множество двойственного матроида.
Литература:[Лекции]

Колесо(Wheel)
- граф, определяемый как W[_n] = K[_1] + C[_n][_-] [_1], т.е. n-вершинный граф, у которого n-1 вершин принадлежат простому циклу C[_n]C[_-] C[_1] и одна вершина (вне этого цикла) смежна со всеми остальными. Термин введен Таттом.
Литература:[Харари]

Колода графа(Pack of a graph)
- набор подграфов вида G[_v] = G \ v, где v пробегает множество вершин графа. См. гипотеза Келли-Улама.
Литература:[Лекции]

Комбинаторно двойственный граф(Combinatoricaly dual graph)
- для данного графа G граф G[^*] такой, что существует взаимно однозначное соответствие между их множествами ребер, при котором для любых соответствующих подмножеств ребер Y и Y[^*] коциклический ранг графа G \ Y) равен коциклическому рангу G минус циклический ранг части < ;Y[^*]> графа G[^*], порожденной множеством ребер Y[^*].
Литература:[Харари]

Композиция графов - см. Граф-композиция.

Компонента двусвязности - см. Блок.

Компонента линейная - см. Линейная компонента.

Компонента нечетная - см. Нечетная компонента.

Компонента односторонняя - см. Односторонняя компонента.

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

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

Компонента сильная - см. Бикомпонента.

Компонента сильной связности - см. Бикомпонента.

Компонента слабая - см. Компонента слабой связности.

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

Конвергентая СПТ - то же, что и Полная СПТ.

Конденсация - см. Граф Герца.

Конезависимое множество матроида(Coindependent set of a matroid)
- для данного матроида независимое множество двойственного матроида.
Литература:[Лекции]

Конечная вершина (ребра)(Terminal vertex (of an edge))
- вершина, инцидентная ребру.
Литература:[Оре]

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

Конец дуги - см. Дуга.

Конечно-автоматная диаграмма(State transition diagram)
- представление конечного автомата в виде помеченного орграфа, вершинами которого являются состояния автомата, а дуги помечены входными символами, переводящими автомат из одного состояния в другое.
Литература:[Касьянов-Поттосин]

Конечное дерево(Finite tree)
- дерево с конечным числом вершин.
Литература:[Берж]

Конечный граф(Finite graph)
- граф с конечным числом ребер.
Литература:[Оре]

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

Г[^-1] конечный граф[^-1]-finite graph)
орграф, у которого во всякую вершину заходит конечное число дуг.
Литература:[Берж]

Контекстно-свободная грамматика - см. Порождающая грамматика.

Контрадостижимое множество(Reaching set)
- множество вершин Q(x[_i]) такое, что из любой вершины этого множества можно достигнуть вершину x[_i].
Литература:[Кристофидес]

Контур(Cycle)
- замкнутый путь в орграфе; контур называется простым или элементарным, если ни одна вершина в нем не встречается дважды.
Литература:[Лекции]

Контур гамильтонов - см. Гамильтонов контур.

Контур простой - см. Контур.

Контур эйлеров - см. Эйлеров контур.

Контур элементарный - см. Контур.

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

Концевая вершина - то же, что и Висячая вершина.

Концевое ребро(End edge)
- ребро, инцидентное концевой (висячей) вершине.
Другое название - висячее ребро.
Литература:[Лекции]

Конъюнкция графов(Conjunction of graphs)
- граф G[_1] [wedge] G[_2] с множеством вершин V[_1] [times] V[_2], у которого вершины u = (u[_1],u[_2]) и v = (v[_1],v[_2]) смежны тогда и только тогда, когда u[_1] смежна с v[_1] и u[_2] смежна с v[_2].
Литература:[Харари]

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

Коранговая функция матроида(Corank function of a matroid)
- ранговая функция двойственного матроида.
Литература:[Лекции]

Корректная разметка - см. Задача анализа свойств состояний.

Корень(Root)
- некоторая выделенная вершина в графе (чаще в дереве).
Литература:[Харари]

Корневое дерево(Rooted tree)
- дерево с выделенной вершиной - корнем.
Литература:[Харари]

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

Корневой граф(Rooted graph)
- граф с одной выделенной вершиной - корнем.
Литература:[Харари-Палмер]

Корона графов(Crown of graphs)
- граф G[_1] [circ] G[_2], получаемый из графов G[_1] и G[_2] следующим образом: берем одну копию графа G[_1] с n[_1] вершинами и n[_1] копий графа G[_2] и последовательно соединяем i-ю вершину графа G[_1] с каждой вершиной i-й копии графа G[_2].
Литература:[Харари]

Коспектральные графы(Cospectral graphs)
- неизоморфные графы с равными характеристическими полиномами.
Литература:[Лекции]

Коцикл(Cocycle)
- для данного матроида M цикл двойственного матроида M[^*]; для графа - минимальный разрез.
Литература:[Лекции], [Харари]

Коциклический матроид - то же, что и Матроид разрезов.

Коцикломатический ранг графа(Cocyclic rank of a graph)
- число [nu]*(G) = |G| - k(G), где k(G) - количество компонент связности графа G, равное числу ребер любого каркаса графа. К.р. равен также числу коциклов в базисе пространства коциклов графа G.
Литература:[Лекции], [Харари]

Коцикломатическое число - то же, что и Коцикломатический ранг графа.

Кратность покрытия(Multiplicity of covering)
- число путей, составляющих покрытие.
Литература:[Евстигнеев]

Кратность ребра(Multiplicity of edge)
- число ребер в мультиграфе, соединяющих две данные вершины.
Литература:[Оре]

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

Кратные ребра(Multiple edges)
- в мультиграфе ребра, соединяющие одну и ту же пару вершин.
Литература:[Харари]

Кратчайшая связывающая сеть - то же, что и Кратчайший остов графа.

Кратчайший остов графа(Shortest spanning tree)
- каркас (остов) взвешенного графа с наименьшей суммой весов ребер.
Литература:[Кристофидес], [Евстигнеев-Касьянов]

Кратчайший путь(Shortest path)
- для двух фиксированных вершин путь наименьшей длины, соединяющий указанные вершины.
Литература:[Кристофидес]

Критерий Гавела - Хакими(Havel - Hakimi criterion)
- критерий графичности числовой последовательности.
Литература:[Лекции]

Критерий Эрдеша - Галлаи(Erd[os - Gallai criterion)
- критерий графичности числовой последовательности.
Литература:[Лекции]

Критическая вершина - см. Вершина критическая.

Критический граф(Critical graph)
- граф, каждая вершина которого критическая относительно данного свойства P.
Литература:[Харари]

Критический путь(Critical path)
- в бесконтурном орграфе с входом s и выходом t путь наибольшей длины из s в t.
Литература:[Кристофидес], [Евстигнеев]

Критическое ребро(Critical edge)
- (относительно некоторого свойства P) ребро графа, обладающего свойством P, удаление которого приводит к графу, не обладающему этим свойством.
Литература:[Харари]

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

КС-грамматика - см. Порождающая грамматика.

Куб n-мерный(n-cube graph)
- граф, вершины которого можно представить (0,1)-векторами длины n таким образом, что две вершины будут смежны тогда и только тогда, когда соответствующие векторы различаются ровно в одной координате. Для n = 2 имеем цикл длины 4, для n = 3 - граф куба. Подграфы n-мерного куба называются кубовыми графами (cubical graphs).
Литература:[Лекции]

Кубический граф(Cubic graph)
- регулярный граф степени 3.
Литература:[Лекции]

Кубовой граф - см. Куб n-мерный.