С

Самодополнительный граф(Self-complementary graph)
- граф, изоморфный своему дополнению.
Самодополнительными графами являются, например, 4-вершинная простая цепь и 5-вершинный простой цикл.
Литература:[Лекции], [Харари-Палмер]

Самонегативный граф(Self-negational signed graph)
- граф, ребрам которого сопоставлены плюсы и минусы и который изоморфен графу, получаемому из него заменой плюсов на минусы и, наоборот, минусов на плюсы.
Литература:[Харари-Палмер]

Самообратный орграф(Self-opposite directed graph)
- орграф, изоморфный обратному орграфу.
Литература:[Харари]

Сбалансированный гиперграф(Balanced hypergraph)
- гиперграф, в котором каждый цикл нечетной длины сбалансирован.
Литература:[Lov\'{a}sz]

Сбалансированный граф(Balanced signed graph)
- граф, ребрам которого сопоставлены плюсы и минусы и который не содержит циклов с нечетным числом отрицательных ребер.
Литература:[Харари-Палмер]

Сбалансированный тотально гиперграф - см. Тотально сбалансированный гиперграф.

Сбалансированный цикл(Balanced circuit)
- цикл (x[_1] , E[_1] , x[_2] , E[_2] , ..., x[_k] , E[_k] , x[_1]) в гиперграфе такой, что либо k = 2, либо существует инцидентность
x[_i] [include] E[_j], где j [neq] i, i-1 и (i,j) [neq] (1,k).
Литература:[Lov\'{a}sz]

Свободное дерево(Free tree)
- дерево, в котором не выделен корень.
Литература:[Евстигнеев-Касьянов]

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

Сводимый уграф - см. Сводимый управляющий граф.

Y-сводимый маршрут(Y-reduced sequence)
- для реберного покрытия Y такой маршрут, у которого концевые ребра принадлежат Y, а концевые вершины инцидентны тем ребрам из Y, которые не являются концевыми ребрами этого маршрута. Очевидно, что любое наименьшее реберное покрытие не содержит сводимых маршрутов.
Литература:[Харари]

Сводимый управляющий граф(Reducible control flow graph)
- уграф, предельный уграф которого является тривиальным. Свойство сводимости уграфа эквивалентно свойству его регуляризуемости.
Литература:[Касьянов],[Евстигнеев-Касьянов]

Свойство Хелли(Helly property)
- семейство подмножеств [ee] = {E[_i] | i [include] I} (например ребра гиперграфа) обладает свойством Хелли,
если из J [subseteq] I и E[_i] [cap] E[_j] [neq] [zero] для всех i,j [include] J следует, что [Formula-14] E[_j] [neq] [zero].
Литература:[Welsh]

Свойство Шпернера(Sperner property)
- свойство конечного ранжируемого частично упорядоченного множества, состоящее в том, что мощность наибольшего независимого множества равна наибольшей мощности уровня max{w[_i] | i [geq] 0}, где w[_i] = |W[_i]|
и W[_i] - все точки x ранга r(x) = i.
Литература:[Welch]

Свойство Черча-Россера - см. Система переписывания термов.

Связанное множество вершин(Connected set of vertices)
- множество вершин, в котором хотя бы одна пара вершин соединена ребром.
Литература:[Оре]

Связанные вершины(Connected verticies)
- вершины, между которыми существует простая цепь.
Литература:[Уилсон]

Связность(Connectivity)
- наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.
Другое название - вершинная связность.
Литература:[Лекции], [Харари-Палмер]

Связная компонента гиперграфа(Connected component of a hypergraph)
- подгиперграф, порожденный областью связности гиперграфа, под которой понимается класс эквивалентности отношения связанности вершин гиперграфа.
Литература:[Лекции], [Lov\'{a}sz]

Связная компонента графа(Connected component of a graph)
- всякий максимальный связный подграф графа; множество вершин связной компоненты называется
областью связности графа.
Литература:[Лекции], [Lov\'{a}sz]

Связность вершинная - см. Вершинная связность.

Связность реберная - см. Реберная связность.

Связный гиперграф(Connected hypergraph)
- гиперграф, имеющий единственную компоненту связности.
Литература:[Лекции], [Lov\'{a}sz]

Связный граф(Connected graph)
- граф, (вершинная) связность которого больше нуля, т.е. граф, любая пара вершин которого связанная.
Литература:[Лекции], [Харари-Палмер]

k-связный граф(k-connected graph)
- граф, (вершинная) связность которого не меньше k.
Литература:[Лекции], [Харари-Палмер]

Сепаратор(Separator)
- для данных вершин a и b множество вершин S, после удаления которых вершины a и b оказываются в разных компонентах связности.
Литература:[Лекции], [Lov\'{a}sz]

Сеть(Net, network)
- орграф, в котором допускаются и петли и кратные дуги и который используется как модель системы, процесса и пр. Обычно в сети выделяются некоторые вершины - полюсы сети, играющие роль входов и выходов сети. Часто под сетью понимается транспортная сеть.
Литература:[Уилсон]

Сеть транспортная - см. Транспортная сеть.

Сечение(Cutting set, cutset, separating set)
- множество вершин, удаление которых из графа увеличивает число компонент связности.
Литература:[Лекции]

Сильная компонента - то же, что и Бикомпонента.

Сильная степень графа - см. Емкость графа.

Сильная укладка - см. Укладка уграфа.

Сильно ветвящееся дерево(m-ary tree)
- выровненное дерево поиска, у которого каждая вершина имеет не более m и не менее (кроме корня и висячих вершин) m/2 потомков и корень, если он не является висячей вершиной, имеет не менее двух потомков (m-арные деревья).
Литература:[Евстигнеев-Касьянов]

Сильно ориентированно-циклически замкнутый граф(Strongly cyclically closed graph)
- пусть e[_0] - некоторая дуга в орграфе G. Часть графа, состоящая из дуг, сильно ориентированно-циклически-реберно связанных с e[_0], называется (ориентированным) блоком G(M) с множеством вершин M(e[_0]). Блок сильно ориентированно-циклически замкнут, если любой простой контур C, имеющий хотя бы две общие с M(e[_0]) вершины, целиком содержится в G(M). Граф сильно ориентированно-циклически замкнут, если G = G(M) для некоторого M(e[_0]).
Литература:[Оре]

Сильно ориентированно-циклически-реберно связный граф(Strongly cyclic edge connected graph)
- орграф, в котором для любых двух дуг e[_1] и e[_2] существует последовательность контуров C[_1] , ..., C[_k] такая,
что e[_1] [include] C[_1] , e[_2] [include] C[_k] и любая пара контуров C[_i] , C[_i+1]) имеет по крайней мере одну общую дугу (сильно ориентированно-циклически-реберно связанные дуги).
Литература:[Оре]

Сильно плотные деревья(Strongly dense tree)
- (m-1)-плотные m-арные деревья.
Литература:[Евстигнеев-Касьянов]

Сильно связанные вершины - то же, что и Бисвязные вершины.

Сильно связная компонента - то же, что и Бикомпонента.

Сильно связная область - то же, что и Бикомпонента.

Сильно связный орграф(Strongly connected graph)
- орграф, у которого любая пара вершин сильно связана.
Литература:[Лекции]

Сильно транзитивный граф(Strongly transitive graph)
- транзитивный антисимметрический граф Бержа (X,Г) (орграф), не содержащий таких троек вершин
x, y, z [include] X, для которых выполнено условие

z [include] Г x [wedge] z [include] Г y [wedge] x [nin] Г y [wedge] y [nin] Г x.
Литература:[Зыков]

Сильно циклически замкнутый граф(Strongly circuit closed graph)
- граф, у которого любые два ребра сильно циклически связаны.
Другое название - двусвязный граф.
Литература:[Оре]

Сильно циклически связанные вершины(Strongly circuit connected vertices)
- вершины, расположенные на одном простом цикле.
Литература:[Оре]

Сильно циклически связанные ребра(Strongly circuit connected edges)
- ребра, расположенные на одном простом цикле.
Литература:[Оре]

Сильно циклически связный граф - то же, что и Двусвязный граф.

Сильное B-дерево(Strong B-tree)
- вариант (a,b)-дерева, у которого b [geq] 2a и число m' потомков корня удовлетворяет неравенству
min(2,t) [leq] m' [leq] b.
    Алгоритмы работы с этими деревьями практически те же, что и для B-дерева, но для них существует больше вариантов проведения преобразований восстановления структуры дерева.
Литература:[Евстигнеев-Касьянов]

Симметрическая группа графа(Symmetrical group of a graph)
- группа автоморфизмов, включающая в себя n! автоморфизмов графа.
Литература:[Алгоритмы]

Симметрическая разность графов(Symmetrical difference of graphs)
- для графов G[_1] и G[_2] граф, определяемый формулой G[_1] [oplus] G[_2] = G[_1] [cup] G[_2] \ G[_1] [cap] G[_2].
Литература:[Алгоритмы]

Симметрический граф(Symmetrical graph)
- граф, группа автоморфизмов которого действует транзитивно как на вершинах, так и на ребрах.
Литература:[Алгоритмы]

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

Симметричное ребро(Symmetric edge)
- ребро дерева, концевые вершины которого подобны.
Литература:[Харари-Палмер]

Симметричное бинарное дерево(Symmetric binary tree)
- (a,b)-дерево для a = 2 и b = 4; частный случай слабого B-дерева.
Литература:[Евстигнеев-Касьянов]

Сингулярная реберная замена(Singular edge exchange)
- операция добавления ребра, приводящая к появлению максимального сингулярного графа.
Литература:[Оре]

Сингулярно связанные графы(Singulary related graphs)
- графы, получаемые один из другого при помощи ряда сингулярных реберных замен.
Литература:[Оре]

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

Синтаксический анализ(Syntax analys (parsing))
- одна из основных частей процесса трансляции, связанная с построением по предложению языка его дерева разбора.
Литература:[Касьянов-Поттосин]

Система переписывания термов(Term-rewriting system)
- конечное множество правил переписывания R, определяющее на множестве термов бинарное
отношение [RightLeftArrow][_R], называемое отношением редукции. Сокращенное название - СПТ.
    R называется нетеровой (или конечно завершаемой), если не существует бесконечной цепочки редукций

t[_1] [RightLeftArrow][_R] t[_2] [RightLeftArrow][_R] t[_3] [RightLeftArrow][_R] ... .
    R порождает на множестве термов отношение эквивалентности =[_R], являющееся транзитивно-рефлексивно-симметричным замыканием отношения редукции.
    Следующие два свойства R являются эквивалентными:
    R обладает свойством Черча-Россера, если для любых термов t[_1] и t[_2] выполняется t[_1] =[^*_R] t[_2] тогда и только тогда, когда существует такой терм t[_3], что t[_1] [RightLeftArrow][^*_R] t[_3] и t[_2] [RightLeftArrow][^*_R] t[_3];
    R называется конфлюэнтной, если для любых термов t[_1], t[_2] и t[_3] таких, что t[_1] [RightLeftArrow][^*_R] t[_2] и t[_1] [RightLeftArrow][^*_R] t[_3], найдется терм t[_4], для которого t[_2] [RightLeftArrow][^*_R] t[_4] и t[_3] [RightLeftArrow][^*_R] t[_4].
    Нетеровая и конфлюэнтная СПТ называется полной (конвергентной, канонической).
    В случае полной СПТ нормальная форма любого терма всегда существует и единственна. Отношение =[^*_R] в этом случае разрешимо: для эквивалентности двух термов необходимо совпадение их нормальных форм.
    R называется локально-конфлюэнтной, если для любых термов t[_1], t[_2] и t[_3] таких, что
t[_1] [RightLeftArrow][_R] t[_2] и t[_1] [RightLeftArrow][_R] t[_3], найдется терм t[_4], для которого t[_2] [RightLeftArrow][^*_R] t[_4] и t[_3] [RightLeftArrow][^*_R] t[_4].
    Теорема Ньюмена. Для нетеровой СПТ свойства конфлюэнтности и локальной конфлюэнтности эквивалентны.
Литература:[Евстигнеев-Касьянов]

Система различных представителей - то же, что и Трансверсаль.

Скелет - то же, что и Каркас.

Слабая укладка - см. Укладка уграфа.

Слабо плотное дерево(Weakly dense tree)
- 1-плотное m-арное дерево.
Литература:[Евстигнеев-Касьянов]

Слабо связный граф(Weakly connected graph)
- орграф, у которого любые две вершины соединены цепью (полупутем).
Другое название - Слабый орграф.
Литература:[Лекции]

Слабое B-дерево(Weak B-tree)
- (a,b)-дерево, у которого b [geq] a. Этот класс деревьев эффективен для представления списков с указателями и для реализации операции объединения множеств.
Литература:[Евстигнеев-Касьянов]

Слабый орграф - то же, что и Слабо связный граф.

Сливаемое дерево(Mergeable heap)
- структура данных, допускающая операции ВСТАВИТЬ, УДАЛИТЬ, ОБЪЕДИНИТЬ, MIN. Использование 2-3-деревьев обеспечивает выполнение n операций за время [Ou](n log n).
Литература:[Ахо-Хопкрофт-Ульман], [Евстигнеев-Касьянов]

Слияние двух вершин - см. Разборный граф.

Слияние двух ребер(Two edge merging)
- операция, обратная операции подразбиения ребер; состоит в замене двух ребер (a,b) и (b,c), инцидентных вершине b степени два, одним ребром (a,c).
Литература:[Зыков]

Сложность алгоритма - то же, что и Временная сложность.

Случайный граф(Random graph)
- случайная величина, значениями которой являются графы.
Литература:[Алгоритмы]

Смежные вершины(Adjacent vertices, joined vertices)
- вершины a и b, соединенные ребром (в графе), соединенные дугой (a,b) (в орграфе), принадлежащие одному ребру (в гиперграфе).
Литература:[Лекции]

Смежные грани(Adjacent faces)
- в плоском графе две грани, имеющие общее ребро.
Литература:[Берж]

Смежные дуги(Adjacent arcs)
- дуги, имеющие общую вершину.
Литература:[Берж]

Смежные ребра(Adjacent edges)
- ребра, имеющие общую вершину (в графе) или имеющие непустое пересечение (в гиперграфе).
Литература:[Лекции]

Смежность(Adjacency)
- бинарное отношение Ad на множестве вершин (ребер) графа такое, что a Ad b тогда и только тогда, когда a и b соединены дугой или ребром (имеют общую вершину).
Литература:[Лекции]

Смешанный граф(Mixed graph)
- граф, содержащий как дуги, так и ребра.
Литература:[Лекции]

Совершенное паросочетание(Perfect matching)
- паросочетание такое, что любая вершина графа инцидентна некоторому ребру этого паросочетания; другими словами, паросочетание, являющееся одновременно реберным покрытием вершин.
Литература:[Лекции]

Совершенный граф(Perfect graph)
- граф, обладающий тем свойством, что хроматическое число и плотность равны не только у самого графа, но и у каждого его подграфа (порожденного подграфа). См. также Гипотеза Бержа.
Литература:[Лекции], [Golumbic]

Совершенный маршрут(Perfect sequence)
- для паросочетания M альтернирующий маршрут, концы которого не инцидентны ни одному ребру из M.
Литература:[Харари]

Соединение графов(Graphs union)
- для графов G[_1] и G[_2] с непересекающимися множествами вершин V[_1] и V[_2] и ребер граф
G[_1] + G[_2] = G[_1] [cup] G[_2] [cup] K(V[_1] ,V[_2]), где K(V[_1] ,V[_2]) - полный двудольный граф с множествами вершин V[_1] и V[_2] в долях.
Литература:[Алгоритмы]

Соединимость вершин - то же, что и Достижимость.

Соединяющая вершина(Vertex of attachment)
- для некоторой части H графа G вершина, инцидентная ребрам как в H, так и в G - H.
Литература:[Оре]

Соединяющее ребро(Edge of attachment)
- для некоторого подмножества A множества вершин графа ребро с одной вершиной в A, а другой в [A^~].
Литература:[Оре]

Соединяющий граф(Attachment graph)
- для некоторого подмножества вершин графа двудольный граф, порожденный соединяющими ребрами.
Литература:[Оре]

Соотнесенный неориентированный граф(Associated undirected graph)
- для данного орграфа неориентированный граф, получаемый из исходного орграфа заменой дуг ребрами.
Литература:[Оре]

Соседние вершины(Neighbouring verticies)
- вершины ордерева, расположенные на одном уровне, но не братья.
Литература:[Евстигнеев-Касьянов]

Составной гамак - см. Гамак.

Составной граф(Compound graph)
- граф, который представим в виде декартова произведения двух нетривиальных графов.
Литература:[Харари]

Соцветные вершины(Equally coloured vertices)
- вершины, которые окрашены в один цвет в некоторой заданной раскраске.
Литература:[Ершов], [Лекции]

Спектр графа(Spectrum of a graph)
- спектр матрицы смежности графа, т.е. совокупность корней характеристического многочлена с учетом их кратности.
Литература:[Лекции], [Lov\'{a}sz]

Список ребер(Edge list)
- способ задания графа (гиперграфа), состоящий в перечислении всех ребер графа (гиперграфа).
Литература:[Ахо-Хопкрофт-Ульман]

Список смежности(Adjacency list)
- для заданной вершины v список вершин, смежных с v; любой граф может быть представлен с помощью n списков смежности, по одному для каждой вершины.
Литература:[Ахо-Хопкрофт-Ульман]

Сравнимые вершины(Comparable verticies)
- пусть < ; есть отношение частичного порядка, порождаемое орграфом G; тогда вершины a и b сравнимы в G, если выполняется хотя бы одно из соотношений b < ; a или a < ; b.
Литература:[Оре]

Средний диаметр(Mean diameter)
- сумма кратчайших расстояний между всеми парами вершин графа, деленная на число пар вершин.
Литература:[Алгоритмы]

Стабильное множество вершин(Stable vertex set)
- подмножество X' [subseteq] X вершин графа L = (X,U) такое, что любая вершина y [include] X \ X' либо смежна со всеми вершинами из X', либо не смежна ни с одной из них.
Литература:[Зыков]

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

Степенная последовательность(Degree sequence)
- список степеней вершин графа с кратностями.
См. Графическое разбиение числа.
Литература:[Лекции]

Степень вершины(Degree of a vertex, valency of a vertex)
- в графе - число инцидентных вершине ребер; в орграфе - число инцидентных дуг, т.е. сумма полустепеней захода и исхода.
Литература:[Лекции]

Степень графа(Degree of a graph)
- раибольшая из степеней вершин графа.
Другое название - Максимальная степень.
Литература:[Лекции]

Степень группы графа(Degree of a graph group)
- мощность множества вершин графа G, на котором действует группа Aut (G).
Литература:[Алгоритмы]

Степень ребра(Degree of an edge)
- для ребра (u,v) пара (s[_1] , s[_2]), где s[_1] - степень вершины u, а s[_2] - степень вершины v.
Литература:[Харари]

Степень ребра гиперграфа(Degree of a hypergraph edge)
- мощность множества вершин данного ребра.
Литература:[Лекции]

Сток орграфа - то же, что и Выход.

Строго квазибисвязный граф(Strongly quasibiconnected graph)
- орграф, в котором каждая пара вершин соединена путем только в одном направлении.
Литература:[Зыков]

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

Строго односторонний орграф(Strongly unilateral digraph)
- односторонний, но не сильный орграф.
Литература:[Харари]

Строго слабый орграф(Strongly weak digraph)
- слабый и неодносторонний орграф.
Литература:[Харари]

Структурный граф - то же, что и Диаграмма Хассе.

Стягиваемый граф(Tightened graph)
- граф G называется стягиваемым к H, если H может быть получен из G с помощью некоторой последовательности стягиваний ребер.
Литература:[Уилсон]

Стягивание графа(Contraction of a graph)
- преобразование графа путем последовательного применения операции стягивания ребра.
Литература:[Лекции], [Lov\'{a}sz]

Стягивание ребра(Contraction of an edge)
- для данного ребра (u,v) слияние его концов u и v и удаление образовавшейся петли.
Литература:[Лекции], [Lov\'{a}sz]

Стягивающее дерево - то же, что и Каркас.

Субдоминирующее множество вершин - то же, что и Внешне устойчивое множество.

Субмодулярная функция (матроида)(Submodular function (of a matroid))
- неотрицательная целочисленная функция, определенная на подмножествах основного множества S(M) матроида M, для которой справедливы субмодулярные неравенства.
Литература:[Welsh]

Субмодулярное неравенство(Submodular inequality)
- для матроида M = (S, [ii]) и любых подмножеств A, B [subseteq] S неравенство для ранговой функции [rho]:

.[rho] (A [cup] B) + [rho] (A [cap] B) [leq] [rho](A) + [rho](B).

Литература:[Welsh]

Суграф(Spanning subgraph)
- часть графа, имеющая то же множество вершин, что и сам граф.
См. Каркас, Остовный подграф.
Литература:[Зыков], [Алгоритмы]

Сумма графов - то же, что и Соединение графов.

Суперпозиция графов(Superposition of graphs)
- пусть

G[_1] , G[_2] , ..., G[_m]

- m графов, каждый из которых имеет одно и то же множество вершин, содержащее n элементов, и пусть ребра графа G[_i], 1 [leq] i [leq] m, окрашены в цвет i; тогда суперпозиция этих графов есть граф на том же множестве вершин, что и исходные графы, и две вершины смежны по ребру i, если они смежны в графе G[_i].
Литература:[Харари-Палмер]

Существенная дуга(Essential arc)
- дуга информационного графа, которая имеет некоторый подтверждающий ее маршрут.
Литература:[Касьянов]

Схема Мартынюка - то же, что и Управляющий граф.

Счетный граф(Countable graph)
- граф, у которого и множество вершин, и множество ребер счетны; это определение исключает случаи, когда счетно лишь множество вершин (конечный граф с бесконечным числом изолированных вершин) или ребер (конечный мультиграф с бесконечным числом петель и кратных ребер).
Литература:[Уилсон]

Сын(Son)
- конец w дуги (v,w) в ордереве.
Литература:[Ахо-Хопкрофт-Ульман]