Concise English-Russian dictionary on graph theory
- Authors: Voblyi V.A.1, Arkhipova N.A.1
-
Affiliations:
- Всероссийский институт научной и технической информации Российской академии наук
- Issue: Vol 233 (2024)
- Pages: 127-153
- Section: Статьи
- URL: https://journals.rcsi.science/2782-4438/article/view/257149
- DOI: https://doi.org/10.36535/2782-4438-2024-233-127-153
- ID: 257149
Cite item
Full Text
Abstract
The proposed "Concise English-Russian Dictionary of Graph Theory" contains about 1,200 terms on graph theory and its applications to physics, chemistry and engineering. It will be useful to all translators of English texts related to graph theory and its applications to natural sciences, economics, and engineering.
Keywords
Full Text
ПРЕДИСЛОВИЕ
Переводчики с английского языка научно-технической литературы, связанной с теорией графов и их приложениями, знают "Русско-английский и англо-русский словарь по графам в информатике" В. А. Евстигнеева и В. Н. Касьянова, изданный в Новосибирске ООО "Сибирское Научное Издательство" в 2011 г. Словарь содержит около 2500 терминов в англо-русской части и находится в свободном доступе в интернете:
https://www.iis.nsk.su/files/book/file/evst_kas_2011_ver2.pdf
К сожалению, целый ряд терминов теории графов, относящихся к ее приложениям в физике, химии, экономике и технике не вошли в этот словарь. Кроме того, бурное развитие дискретной математики и вычислительной техники приводит к постоянному появлению новых терминов в теории графов.
Предлагаемый "Краткий англо-русский словарь по теории графов" создан на основе словаря В. А. Евстигнеева и В. Н. Касьянова. Большое количество малоупотребительных терминов этого словаря не включены в краткий словарь. Новый словарь пополнен более 500 терминами, отсутствующими в словаре В. А. Евстигнеева и В. Н. Касьянова. При этом основным источником новых терминов служили рефераты из раздела "Теория графов" в Реферативном журнале "Математика" и БД "Математика" ВИНИТИ РАН. Объем словаря около 1200 терминов.
A
absorbant number число поглощения
absorbent set, absorbing set, absorbant set поглощающее множество
acceptable assignment насыщающая разметка
accordion аккордеон (граф)
acyclic graph ациклический граф
acquisition number число приобретения
adjacency matrix матрица смежности
adjacent vertices смежные вершины
adjoint digraph сопряженный орграф
alphabet overlap graph граф алфавитного перекрытия
alt альт, альтернативный фрагмент, закрытый фрагмент
altermatic number альтерматическое число
alternating group знакопеременная группа
alternating chain чередующаяся (альтернирующая) цепь
amalgamation амальгамирование, слияние
amallamorphic graphs амалламорфные графы
amount of a flow величина потока
ancestor of a vertex предок вершинs
Andrasfai graph граф Андрашфаи
animal полимино
annihilating-ideal graph граф аннулирующих идеалов
annihilation number число аннигиляции
annihilator graph аннуляторный граф
anti-adjacency matrix матрица антисмежности
anti-Kekule number антикекулево число
antiprism graph граф антипризмы
anti-Ramsey number антирамсеево число
anti-triangle антитреугольник, дополнение треугольника
apex graph апексный граф
arachnoid graph арахноидальный граф
arank number аранговое число
arbitrarily traceable graph произвольно вычерчиваемый граф
arbitrarily traverseable graph произвольно проходимый граф
arborable graph разветвляемый граф
arboreal hypergraph древесный гиперграф
arborescence ориентированное дерево
arboricity древесность
arc дуга
arc-transitive graph дуготранзитивный граф
Archimedean graph архимедов граф
arithmetic graph арифметический граф
arrangeable graph упорядочиваемый граф
arrangement graph граф расположения
arrow стрела (граф)
articulation point точка сочленения
assignment problem задача о назначениях
assortativity ассортативность
atom-bond connectivity index индекс связности атомного соединения
attachment vertex вершина присоединения
augmented adjacency matrix расширенная матрица смежности
augmenting chain увеличивающая цепь
automaton graph автоматный граф
automorphism group группа автоморфизмов
B
backbone хребет
backbone coloring хребтовая раскраска
back-edge обратная дуга
backward arc обратная дуга
balanced graph сбалансированный граф
ball number шаровое число (графа)
bandwidth ширина полосы, пропускная способность
banner флаг, баннер (граф)
barbell гантель (граф)
barier барьер
base digraph базовый орграф
base of a directed graph база орграфа, основание орграфа
basic cycle базисный цикл
basis number базисное число
basis graph of matroid граф баз матроида
bend number число изгиба
Beraha number число Бераха
Berge graph граф Бержа
Bertz index индекс Берца
Bethe tree дерево Бете
betweeness промежуточность
bi-arc graph двухдуговой граф
biased graph смещенный граф
biclique биклика
biclique graph граф биклик
bicolored 2-раскрашенный граф
biconnected component компонента двусвязности, блок
Bidiakis cube куб Бидиакиса
bidirectional arcs двунаправленные дуги
Biggs-Smith graph граф Биггса-Смита
bigraph биграф
binary tree бинарное дерево
binding number число связи
Binet-Caushy theorem теорема Бине-Коши
bipartite graph двудольный граф
bipartiteness двудольность
bipartition разделение (графа) на две части, биразделение
biregular graph бирегулярный граф
bishop graph граф слона
Blanusa snark снарк Блануши
block блок
block-cactus graph (полно)блочно-кактусный граф
block graph граф блоков
block-cutpoint graph граф блоков и точек сочленения
blossom tree цветущее дерево
blow-up lemma лемма о раздутии
bluff graph блефовый граф
body-hinge graph телошарнирный граф
Bollobas graph граф Боллобаша
bond бонд
bond percolation просачивание по ребрам
bondage number число зависимости
book graph книжный граф
borderenergetic graph граничноэнергетический граф
boron tree двоичное дерево
bottleneck узкое место
bouquet букет (граф)
bowtie галстук-бабочка (граф)
boxity ящичность.
brace брекет (скоба)(граф)
bracelet браслет (граф)
bramble ежевика, колючка (граф)
bramble number терновое число
branch ветвь
branch vertex вершина ветвления
branchwidth ширина ветвления
BFS (breadth first search) поиск в ширину
brick брикет, брусок (граф)
bridge мост
bridged graph, bridge graph граф с мостами
bridgeless graph граф без мостов
broadcast graph граф широковещания
broom метла (граф)
Brouwer-Haemers graph граф Брауэра-Хемерса
Bruhat graph граф Брюа
brush number щеточное число
bubble-sort graph граф пузырьковой сортировки
bug жук (граф)
bull бык (граф)
bull’s head graph граф головы быка (граф)
bundle расслоение
bunkbed conjecture гипотеза о двухъярусной кровати
burning number число горения
burnt pancake graph граф подгоревших блинов
Burnside lemma лемма Бернсайда
butterfly бабочка (граф)
C
cactus кактус (граф)
cage клетка
cage graph клеточный граф
call graph граф [вызова] процедур
capacity of a cut-set пропускная способность разреза
carambola карамбола (граф)
Cartesian product of graphs декартово произведение графов
carving нарезка (графа)
caterpillar гусеница (граф)
cathedral купол
Cayley graph граф Кэли
center центр
centipede сороконожка (граф)
centroid центроид
chain цепь
chain graph цепной граф
chair кресло (граф)
chamber graph камерный граф
Chang graph граф Чана
character degree graph граф степеней характеров
Cheeger constant константа Чигера
cherry черри (граф)
child потомок, порожденный, дочерний
chip-firing поджигание
chiral graph хиральный граф
choice number число выбора
choosability выбираемость
chord хорда
chordal graph хордальный граф
chromatic number хроматическое число
chromatically unique graph хроматически единственный граф
Chvatal graph граф Хватала
circle graph круговой граф
circuit цикл
circuit connected циклически связный
circuit rank цикломатический ранг, цикломатическое число
circuitless graph граф без циклов
circulant graph циркулянтный граф
circular-arc graph граф дуг окружности
circular coloring круговая раскраска
circumference окружение
claw лапа, клешня
claw-free graph граф без лап
claw-heavy graph граф с тяжелыми лапами
clean graph чистый граф
Clebsh graph граф Клебша
clique клика
clique cover кликовое покрытие
clique graph граф клик
clique number кликовое число
clique-width кликовая ширина
closure замыкание
cluster кластер
clustered graph кластерный граф
clutter клаттер, беспорядок
coalescing срастание
coarseness крупность, зернистость, шероховатость
Coates graph граф Коутса
cocktail party graph граф коктейльной вечеринки
cocycle коцикл
cohesion сцепление
coin graph монетный граф
collapsible graph сжимаемый, стягиваемый граф
color-blind index индекс дальтонизма
colored graph раскрашенный граф
coloring раскраска
coloured class цветной класс
comb graph гребешковый граф
comet комета (граф)
commuting graph граф коммутирования
comparability graph граф сравнимости
comparable vertices сравнимые вершины
competition graph граф конкуренции
complement of a graph, complementary graph дополнение графа
complete graph полный граф
complete multipartite graph полный многодольный граф
complete tree завершенное дерево
NP-complete problem NP-полная задача
complex unit gain graph граф усиления с комплексной единицей
component of a graph компонента графа
composition of graphs композиция графов
compound graph составной граф
condensation конденсация
conference graph конференсный граф
congestion скопление
conjunction of graphs конъюнкция графов
connected component компонента связности
connected graph связный граф
connecter соединитель
connectivity связность
constellation созвездие (граф)
contact graph контактный граф
containment graph граф включений
contraction of an edge стягивание ребра
control flow graph граф потока управления
converse digraph обратный орграф
convex dominating set выпуклое доминирующее множество
convex domination number число выпуклого доминирования
co-occurrence graph граф совместного появления
Cops and Robbers game игра полицейские и воры
cop-win graph граф выигрыша полицейского
cordial graph сердечный граф
core ядро, сердцевина
coreness ядерность
coritivity коритивность
corona корона (графов)
correspondence coloring соответствующая раскраска
coset graph граф смежных классов
cospectral graphs коспектральные графы
cotree кодерево
covering graph покрывающий граф, накрывающий граф
countable graph счетный граф
coupon coloring купонная раскраска
Coxeter graph граф Коксетера
CPM (critical path method) метод критического пути
crossing number число скрещиваний, число пересечений
crown graph граф короны
crumby coloring рассыпчатая раскраска
cube graph граф куба
cubic graph кубический граф
cubicity кубичность
curling number число завихрения
current ток
curvature кривизна
cut of a layout разрез укладки
cut-edge ребро-разрез, мост
cutpoint точка сочленения, шарнир
cutpoint graph граф точек сочленения
cutset разрез, сечение
cutwidth of a layout ширина разреза укладки
cyclability циклируемость
cycle цикл
cycle matrix матрица циклов
cyclic sequence циклический маршрут
cyclomatic number цикломатическое число, цикломатический ранг
D
DAG (directed acyclic graph) ациклический орграф
dart дротик (граф)
de Bruijn graph граф де Брёйна
decision problem задача принятия решения
decidable problem (алгоритмически) разрешимая задача
decision tree дерево решений
deck колода (графа)
decomposable graph разложимый граф
decomposition разложение, декомпозиция
decycling number число дециклирования
deer олень (граф)
defensive alliance оборонительный союз
deficiency дефицит
defining set определяющее множество
degree of a vertex степень вершины
degree sequence степенная последовательность
Dejter graph граф Дейтера
demand graph граф заказов
demigenus полурод
dense graph плотный граф
density плотность
depth of a tree глубина дерева
DFS (depth-first search) поиск в глубину
derangement graph граф беспорядков
derivation tree дерево вывода
derived graph производный граф
Desargues graph граф Дезарга
descendant потомок
descendance graph граф потомства
dessin d’enfant детский рисунок
detour обход
diameter диаметр
diamond алмаз (граф)
difference graph разностный граф
digon двуугольник
digraph орграф
Dijkstra algorithm алгоритм Дейкстры
Dilworth number число Дилуорса
Dinitz algorithm алгоритм Диница
dipole диполь (граф)
direct product прямое произведение (графов)
directed edge ориентированное ребро, дуга
directed graph ориентированный граф, орграф
directed sequence ориентированный маршрут
disc диск
disk graph дисковый граф
disconnected graph несвязный граф
disjoint paths непересекающиеся цепи
disjintness graph граф непересекаемости
disjunct union of graphs дизъюнктное объединение графов
dismantlable graph разборный граф
disorientation of an arc дезориентация дуги
dissection рассечение
dissociation number число диссоциации
distance расстояние
distance hereditary graph дистанционно-наследуемый граф
distance regular graph дистанционно-регулярный граф
distinguishing number отличительное число
ditree ордерево
domatic number доматическое число
dominance number, domination number число доминирования
dominant set, dominating set доминирующее множество
dominator обязательный предшественник, доминатор
dominator tree доминаторное дерево
dot product скалярное произведение
doublecross graph граф с двойным пересечением
double dominating set двойное доминирующее множество
double domination number число двойного доминирования
dragon graph драконов граф
drawing укладка (графа)
dual graph двойственный граф
dually chordal graph двойственно-хордальный граф
Dudeney set множество Дьюдене
dumbell graph гантельный граф
duplicate graph граф дублирования
Dürer graph граф Дюрера
dyadic graph двоичный граф
Dyck graph граф Дика
E
ear expansion колосковое разложение
ears of graphs уши графов
eccentricity эксцентриситет
edge ребро
edge adding добавление ребра
edge coloring реберная раскраска
edge connectivity реберная связность
edge cut, edge cut set разрез
eigenvalue собственное значение (графа)
elegant graph элегантный граф
Ellingham-Horton graph граф Эллингема-Хортона
embedding of a graph вложение графа
enclave анклав
endblock концевой блок, висячий блок
k-ended tree к-законченное дерево
endpoint, end-vertex висячая, концевая вершина
energy энергия (графа)
entire colouring целая, сплошная раскраска
entire Zagreb index полный загребский индекс
entry vertex стартовая вершина, входная вершина
equally coloured vertices соцветные вершины
equicoverable graph равнопокрываемый граф
equienergetic graph равноэнергетический граф
equimatchable равносогласуемый, равнопаросочетаемый
equipartite graph равнодольный граф
equitable partition справедливое разбиение
equivelar map эквивелярная карта
Erdös-Gyarfas conjecture гипотеза Эрдёша-Дьярфаша
Erdös-Renyi model модель Эрдёша-Реньи
Errera graph граф Эрреры
Estrada index индекс Эстрады
eternal coloring вечная раскраска
Euler-Poincare characteristic характеристика Эйлера-Пуанкаре
Eulerian graph, Euler graph эйлеров граф
even graph четный граф
excellent graph превосходный граф
exceptional graph исключительный граф
excess избыток
exchanged hypercube обмененный гиперкуб
exhaustive search перебор
expander расширитель
expansion graph граф расширения
exponent of a digraph экспонента орграфа
extendable graph расширяемый граф
exterior face внешняя грань
external stability set внешне устойчивое множество
external vertex висячая вершина
eye-free graph безглазый граф
F
face грань (графа)
factor-critical graph фактор-критический граф
factor фактор
factorable graph, factorizable graph факторизуемый граф
factorization факторизация
factor-graph фактор-граф
fair matching справедливое паросочетание
fall coloring падающая раскраска
fan веер (граф)
Farey graph граф Фарея
fasciagraph фасциаграф
fat graph толстый граф
father of a vertex отец (непосредственный предок) вершины
fault tolerance отказоустойчивость
feed back vertex вершина обратной связи
felicitous graph удачный граф
fibre слой
firecracker фейерверк (граф)
first-fit coloring первая подходящая (непосредственная) раскраска
fixatic number число закрепления
fixed vertex неподвижная вершина
fixity неподвижность
flag флаг (граф)
flip graph граф переворачиваний
flat graph плоский граф
flow augmenting path путь (цепь), увеличивающий поток
flow graph управляющий граф
flow-equivalent graphs потоко-эквивалентные графы
flower цветок (граф)
Floyd-Warshal algorithm алгоритм Флойда-Уоршалла
folded hypercube складной гиперкуб
Folkman graph граф Фолкмана
forbidden subgraph запрещенный подграф
forcing minor вынужденный минор
forcing number число форсинга
Ford-Fulkerson theorem теорема Форда-Фалкерсона
forest лес
fork вилка (граф)
forward arc прямая дуга, дуга вперед
four color theorem теорема о четырех красках
fractional coloring дробная раскраска
fragile graph хрупкий граф
frame фрейм
frame graph каркасный граф
friendship graph граф дружбы
friends-and-strangers graph граф друзей и незнакомцев
frieze group группа бордюра
Frucht graph граф Фрухта
frustration фрустрация
fulleren фуллерен
fuzzy graph нечеткий граф
G
gain graph граф усиления
galaxy галактика (граф)
gamburger гамбургер (граф)
game chromatic number игровое хроматическое число
game domination number число игрового доминирования
gap-planar graph разрывно-планарный граф
gear шестерня (граф)
gem драгоценный камень, гемма (граф)
general graph общий граф, граф общего вида
generating function производящая функция
genus род (графа)
geodesic геодезическая
geodetic graph геодезический граф
Gewirtz graph граф Гевирца
girth обхват
s-gonal tree s-угольное дерево
gonality гональность
Gordon-Scantlebury index индекс Гордона-Скантлбери
gossip graph граф распространения слухов
graceful graph грациозный граф
grafting пересадка, прививка
Graham-Houghton graph граф Грэхема-Хоутона
Graovac-Gorbani index индекс Граоваца-Горбани
graph bundle связка графов
graph chessboard таблица графа
graphlet графлет
graph of mapping граф отображения
graph of a partial order граф частичного порядка
graphon графон
graph pebbling фиширование графа, игра с фишками на графе
graph unfolding развертка графа
graph union объединение графов
graphic sequence графическая последовательность
graphoid графоид
greedoid гридоид
greedy algorithm жадный алгоритм
grid graph граф решетки
Grötzsch graph граф Грётша
group graph граф группы
groupie групи
growing tree растущее дерево
Gruenberg-Kegel graph граф Грюнберга-Кегеля
Grundy number число Гранди
guessing number число угадывания
Gupta scheme код Гапта
H
Hadamard graph граф Адамара
Hadwiger number число Хадвигера
Hajos graph граф Хайоша
half-edge полуребро
half graph полуграф
Halin graph граф Халина
Hall theorem теорема Холла
hammer молот (граф)
Hamiltonian circuit гамильтонов цикл
Hamiltonian connected graph гамильтоново-связный граф
Hamiltonian decomposable graph гамильтоново разложимый граф
Hamiltonian graph гамильтонов граф
Hamming graph граф Хэмминга
hammock гамак
handcuff наручники (граф)
handshake’s lemma лемма о рукопожатиях
Hawkes graph граф Хоукса
heap куча
Heawood graph граф Хивуда
hedgehog ёж (граф)
height of a tree высота дерева
Helly hypergraph гиперграф Хелли
helm штурвал (граф)
hereditary class of graphs наследственный класс графов
Herschel graph граф Хершеля
Hertz graph граф Герца
Higman-Sims graph граф Хигмана-Симса
hinge vertex шарнирная вершина
hole дыра
homeomorphical graphs гомеоморфные графы
homeomorphically irreducible graph гомеоморфно несводимый граф
homology гомология
honest graph честный граф
Hosoya index индекс Хосойа
host graph базовый граф
hourglass песочные часы (граф)
house дом (граф)
hub number центральное число
Hückel graph граф Хюккеля
hull number оболочечное число
hydra number число гидры
hyper de Bruijn graph гиперграф де Брёйна
hyper Petersen graph гиперграф Петерсена
hyper-Wiener index гипериндекс Винера
hypercube гиперкуб
hypergraph гиперграф
hypohamiltonian graph гипогамильтонов граф
hypermap гиперкарта
I
identical group тождественная группа
identity tree асимметрическое дерево
idomatic number идоматическое число
immediate dominator непосредственный обязательный предшественник
immediate postdominator непосредственный обязательный преемник
immersion погружение, иммерсия
immovable vertex неподвижная вершина
impropriety неправильность
incenter внутренний центр
incidence graph граф инцидентности
incidence matrix матрица инцидентности
incidentor coloring инцидентная раскраска
inclusion tree дерево вложенности
incomparable vertices несравнимые вершины
incompatibility graph граф несовместимости
indecomposable неразложимый
indegree, in-degree полустепень захода (вершины)
independence number число независимости
independent dominating number число независимого доминирования
independent set независимое множество
indicated coloring индикаторная раскраска
indifference graph индифферентный граф, граф безразличия
induced subgraph порожденный подграф
inflation инфляция
inheritance graph граф наследования
inhibitor arc ингибиторная дуга
initial node начальная вершина
in-neighborhood входящая окрестность
input arc заходящая дуга
inradius внутренний радиус
inset заходящее множество
integer distance graph граф целочисленных расстояний
integral graph целочисленный граф
integrity целостность (графа)
interchange graph граф замен
interlace polynomials многочлен сплетения
intersection graph граф пересечений
intersection of graphs пересечение графов
interval graph интервальный граф
intractable problem труднорешаемая задача
in-tree входящее ордерево
inverse arborescence обратная древесность
irreducible graph несводимый граф
irredundance неизбыточность
irreflexive relation антирефлексивное отношение
irregular graph неоднородный (нерегулярный) граф
irregularity strength степень нерегулярности
Isaaks graph граф Айзекса
isolation number изоляционное число
isoperimetric number число изопериметричности
isthmus перешеек, мост
J
Jahangir graph граф Джахангира
jellyfish graph медузный граф
jewel жемчужина (граф)
Johnson graph граф Джонсона
join соединение (графов)
judicious partition разумное разбиение
jump graph граф скачков
jump distance расстояние скачков
justified tree выровненное дерево
juxtaposition наложение, сопоставление
K
kaleidoscope калейдоскоп (граф)
Karp-Miller tree дерево Карпа-Миллера
Kautz digraph орграф Каутца
kayak paddle байдарка (граф)
kernel ядро
kernelization выделение ядра
keyring связка ключей (граф)
king король
king graph граф короля
kipas кипас (граф)
Kirchoff matrix матрица Кирхгофа
Kirszbraun graph граф Киршбрауна
kissing number поцелуйное число
kite воздушный змей (граф)
kite system змейковая система
Kittel graph граф Киттеля
Klein bottle бутылка Клейна
Kneser graph граф Кнезера
Knödel graph граф Кнёделя
knot узел
knowledge graph граф знаний
König’s theorem теорема Кёнига
Königsberg’s bridges problem задача о кенигсбергских мостах
Krausz dimension of a graph краусова размерность графа
Kronecker product кронекерово произведение
Kruskal’s algorithm алгоритм Краскала
L
labeled graph помеченный граф
labeling разметка
laceability связываемость
ladder лестница (граф)
Laman graph ламанов граф
lamplighter graph граф фонарщика
Lanzhou index индекс Ланьчжоу
Laplacian eigenvalues лапласово собственное значение
Laplacian matrix матрица Лапласа, лапласиан
lattice graph граф решётки
layout укладка, нумерация, схема
leaf лист
leaf number листовое число
leafage крона
leaf-connected листово связный
leapfrog fulleren скачкообразный фуллерен
left linear tree левостороннее дерево
left-sided balanced tree левостороннее балансированное дерево
letter graph буквенный граф
lettericity буквенность
level graph граф уровней
Levi graph граф Леви
liar’s domination доминирование лжеца
lifting graph граф поднятия
light edge легкое ребро
line graph реберный граф
line-independence number реберное число независимости
linear arboricity линейная древесность
linear arrangement линейное размещение
link звено, ребро
linkage соединение
linked graph связанный граф
list coloring предписанная раскраска
Ljubljana graph граф Любляны
lobe graph блок
lobster омар (граф)
locating chromatic number размещенное хроматическое число
locating total domination локализующе-тотальное доминирование
location number число размещения
lollypop graph леденцовый граф
loop петля, цикл
loop region циклический участок
loose cycle неплотный цикл
looseness несвязанность
lopsidependency graph граф односторонней зависимости
Loupekine snark снарк Лупекина
Lovacz lemma лемма Ловаса
M
magic labeling магическая разметка
magnitude of a flow мощность потока, величина потока
main eigenvalue главное собственное значение
majestic coloring грандиозная раскраска
majority domination number число мажоритарного доминирования
maker-breaker game игра созидатель-разрушитель
map карта
marked graph маркированный граф
marking разметка, маркировка
Mason graph граф Мэзона
matcher сопоставитель
matching паросочетание
matching equivalent эквивалентность по паросочетаниям
matching number число паросочетания
matching polynomial полином паросочетаний
matching preclusion number число препятствия для паросочетания
matchoid матчоид
matchstick graph спичечный граф
matrix-tree theorem матричная теорема о деревьях
matroid матроид
Matthews graph граф Мэтьюза
max-flow min-cut theorem теорема о наибольшем потоке и наименьшем разрезе
McGee graph граф МакГи
McLaughlin graph граф Маклафлина
mean graph средний граф
meander меандр
meanness серединность
median graph медианный граф
Menger’s theorem теорема Менгера
Meredith graph граф Мередита
mergeable heap сливаемое дерево
Meringer graph граф Мерингера
Merrifield-Simmons index индекс Меррифилда-Симмонса
mesh сеть
metric dimension метрическая размерность
metrized graph метризованный граф
middle graph серединный граф
minor минор (графа)
minor-closed class of graphs минорно замкнутый класс графов
minus domination number число минус-доминирования
mixed graph смешанный граф
Möbius ladder лестница Мёбиуса (граф)
Monge graph граф Монжа
monochromatic class (set) одноцветный класс
Moore graph граф Мура
Moser graph (spindle) граф (веретено) Мозера
Mostar index индекс Мостара
MC coloring MC раскраска, раскраска с монохроматической связью
multipartite graph многодольный граф
multiple domination кратное доминирование
multiway tree многоходовое дерево
Mycielskian of a graph мысельскиан графа
N
near perfect matching почти совершенное паросочетание
nearly regular graph почти однородный граф
necklace ожерелье(граф)
neighbourhood matrix матрица соседства
neighbourhood of a vertex окрестность вершины
neighbouring vertices соседние вершины
NEPS (noncomplete extended p-sum) неполная расширенная p–сумма
neutrosophic graph нейтрософный граф
network сеть
niche graph граф ниш
nilradical graph нильрадикальный граф
node узел, вершина
noncovered vertex свободная вершина
non-backtracking graph граф без возврата
noncursal vertex нонкурсальная вершина
nondecidable problem (алгоритмически) неразрешимая проблема
non-edge неребро, отсутствие ребра
non-separable graph неразделимый граф
Nordhaus-Gaddum boundary Нордхауза-Гаддума граница
nowhere-zero flow нигде не нулевой поток
NP-hard problem NP-трудная задача
null graph нуль-граф
nullity дефект
numbering нумерация (вершин графа)
nut graph ореховый граф
O
obstruction set препятствующее множество
occurence graph граф событий
octree октодерево, восьмеричное дререво
odd graph нечётный граф
offensive alliance наступательный союз
one-ended одноконцевой
one-to-one mapping взаимно однозначное отображение
order of a graph число вершин графа
ordered tree упорядоченное дерево
ordering упорядочение
oriented graph направленный граф
outcenter внешний центр
outcoming arc исходящая дуга
outdegree, out-degree полустепень исхода (вершины)
outerplanar graph внешнепланарный граф
out-neighbourhood исходящая окрестность
outradius внешний радиус
P
P=NP problem, P versus NP problem P=NP проблема
pack of a graph колода графа
page number книжное число
pair group парная группа
palette index индекс палитры
Paley graph граф Пэли
pan сковорода (граф)
pancyclic graph панциклический граф
pancake graph блинный граф
pants graph граф штанов
Pappus graph граф Паппа
paraglider параплан, параглайдер (граф)
Parikh mapping отображение Париха
parity coloring сравнимая раскраска
parse tree дерево разбора
parsimony distance экономное расстояние
partial edge частичное ребро
partially ordered set частично упорядоченное множество, посет
n-partite graph -дольный граф
partition of a graph разбиение графа
patch участок, блок
path путь, цепь
path connectivity цепная (путевая) связность
path covering путевое покрытие
path-distance width дистанционно-путевая ширина
pathos пафос (графа)
pathos clique graph пафосно-кликовый граф
pathos lict subdivision пафосное ликтовое подразбиение
pathwidth of a graph путевая ширина графа
paw лапа (граф)
pebbling фиширование
pebbling number фишечное число, число мощения
pegging number число привязки
pendant vertex висячая вершина, концевая вершина
peninsula полуостров
percolation просачивание, перколяция
perfect graph совершенный граф
perfect matching совершенное паросочетание
peripheral vertex периферийная вершина
permutation graph граф перестановки
permuton пермутон
petal graph лепестковый граф
Petersen graph граф Петерсена
Petri net сеть Петри
pfafian graph пфаффов граф
phylogeny graph филогенный граф
pineapple graph ананасный граф
piercing number число пирсинга
Pisot number число Пизо
pivot number поворотное число
plabic (planar+bicoloured) graph плабический граф
planar graph планарный граф
plane graph плоский граф
planted tree дерево с висячим корнем
Platonic graph платонов граф
platypus утконос (граф)
plex сплетение (сеть)
point точка, вершина (графа)
point-covering number число вершинного покрытия
point-line group вершинно-реберная группа
point-symmetric вершинно-симметричный
point visibility graph граф видимости точек
pointihedron острогранник
Polya enumeration theorem теорема перечисления Пойа
polytop graph граф многогранника
polyhedral graph полиэдральный граф
polyomino graph полиминный граф
Posa theorem теорема Поша
poset посет, частично упорядоченное множество
postdominator обязательный преемник, постдоминатор
Poussin graph граф Пуссена
power domination доминирование по мощности
predecessor of a vertex предок вершины
prefix graph префиксный граф
premap предкарта
preorder предпорядок
pretzel крендель (граф)
primal-dual прямо-двойственное (представление)
prime graph примитивный граф, элементарный граф
prism призма (граф)
product of graphs произведение графов
profinite graph проконечный граф
proper coloring собственная, правильная раскраска
proximity близость
Prüfer code код Прюфера
pruned tree обрезанное дерево
pseudograph псевдограф
Ptolemaic graph птолемеев граф
pumping lemmas леммы о возрастании
pumpkin тыква (граф)
pushable chromatic number выталкиваемое хроматическое число
pushdown graph магазинный граф
Q
quadrangulation квадрангуляция
quadrilateral четырехсторонник, четырехугольник
quadrilateral graph четырехугольный граф
quadtree кваддерево
queen graph граф ферзя
queue number число очередей
quipu кипу (граф)
quiver колчан (граф)
quorum coloring кворумная раскраска
R
radio number радио число, лучевое число
radius радиус (графа)
rainbow connection number число радужной связи
Ramanujan graph граф Рамануджана
Ramsey number число Рамсея
Randic index индекс Рандича
random graph случайный граф
random walk случайное блуждание
rank ранг (графа)
ranking number число ранжирования
Rauzy graph граф Рози
ray луч
reachability graph граф достижимости
reconfiguration graph граф реконфигурации
Reeb graph граф Риба
rectagraph ректаграф
regular graph регулярный (однородный) граф
reinforcement number число подкрепления
relation precedence отношение предшествования
removal of an edge удаление ребра
reproduction graph граф воспроизводства
resolving set разрешающее множество
restrained dominating set ограниченное доминирующее множество
restricted domination number число ограниченного доминирования
retraction ретракция (графа)
reverse arc обратная дуга
revised Szeged index дополненный сегедский индекс
ribbon graph ленточный граф
ridge graph хребтовый граф
right-linear tree правостороннее дерево
rigid circuit graph циклически жесткий граф, хордальный граф
rigid graph жесткий граф
rim обод (граф)
ring-sum кольцевая сумма (графов)
rising sun graph граф восходящего солнца
Roman domination римское доминирование
Roman domination number число римского доминирования
rook graph граф ладьи, ладейный граф
root корень
rooted graph корневой граф
rose graph граф розы
rotagraph ротаграф
roughness грубость
route обход, маршрут
routing маршрутизация
rubbling измельчение, рубка
rupture degree степень разрыва
Ryjachek closure замыкание Рыячека
S
Sachs graph граф Захса
safe number число безопасности
sandglass graph граф песочных часов
sandpile group критическая группа
satisfiability problem задача о выполнимости
saturated graph насыщенный граф
scattering number число рассеяния
Schrläfli graph граф Шлефли
Schrijver graph граф Схрейвера
Schultz index индекс Шульца
score счет (в турнире)
scorpion скорпион (граф)
scramble number число шифрования
security number число безопасности
Seidel switching переключатель Зейделя
self-centered graph самоцентрированный граф
self-complementary graph самодополнительный граф
self-converse graph самообратный граф
selfdual самодвойственный
semigraph полуграф
separable graph разделимый граф
separating set разделяющее множество, разрез
separator разделитель
sequence маршрут
sequence graph граф последовательности
serf крепостной (граф)
series-parallel graph последовательно-параллельный граф
sesquivalent полуторавалентный
set-graceful graph множественно-грациозный граф
set Ramsey number множественное число Рамсея
shadow graph теневой граф
shredder разделитель
Shrikhande graph граф Шрикханде
Sierpinski graph граф Серпинского
sign graph, sigraph знаковый граф
signed domination number число знакового доминирования
similar vertices подобные вершины
simple graph простой граф, обыкновенный граф
simplicial vertex симплициальная вершина
simply rooted однокорневой
singleton graph одноэлементный граф
sink выход, сток
sink-tree дерево источников
size of a graph число ребер графа
size Ramsey number реберное число Рамсея
skein моток
skeleton graph остов
skew energy асимметричная (косая) энергия
skewed tree дерево со скосом
skewness of a graph искаженность, асимметрия графа
skirting cycle крайний цикл
Slater number число Слейтера
small-world graph граф малого мира
Smarandachely graph граф Смарандаке
Smith graph граф Смита
smooth graph гладкий граф
snake graph граф змеи
snark снарк
snowflake снежинка (граф)
snub prism курносая призма
soccerball graph граф футбольного мяча
son of a vertex сын вершины
sorting tree дерево сортировки
source источник, начало дуги
Sousselier graph граф Сусилье
spanner стягиватель
spanning tree остов, каркас, скелет
sparse graph разреженный граф
spider паук
split graph расщепляемый граф
splitting of a vertice расщепление вершины
spoke спица
spread размах (спектра), спред
square квадрат
square graph квадратный граф
squared graph отквадрированный граф
squco (square-complementary) graph квадратично-дополнительный граф
stability number число стабильности
stable set устойчивое множество
stamen of a flower тычинка цветка (граф)
star звезда
star coloring звездная раскраска
starfish морская звезда (граф)
starlike tree звёздоподобный граф, звёздоподобное дерево
Steiner distance расстояние Штейнера
stem ствол, стебель
straight line graph граф с ребрами, являющимися отрезками прямых
stretcher носилки (граф)
string graph струнный граф
strong closure of a graph сильное замыкание графа
strong component of a digraph бикомпонента
strong dominating set строго доминирующее множество
strong orientation сильная ориентация
strong product of graphs сильное произведение графов
strongly chordal graph строго хордальный граф
strongly connected graph сильно связный граф
strongly regular graph сильно регулярный граф
Sturmian graph граф Штурма
subdivision graph граф подразбиений
subdivision of an edge подразбиение ребра
subgraph подграф
successive coloring последовательная раскраска
successor of a vertex преемник вершины
suffle cube перетасованный куб
sum graph граф сумм
sum hypergraph суммарный гиперграф
sum of graphs сумма графов
sun солнце (граф)
sunflower подсолнечник (граф)
sunlet graph солнечный граф
sunlike graph солнцеподобный граф
supergraph надграф
support опора (графа)
support vertex опорная вершина
swap graph граф замены
switch operation операция переключения
switch equivalent graphs графы, эквивалентные по переключению
switching переключение
Sylvester graph граф Сильвестра
Szeged index сегедский индекс
Szekeres snark снарк Секереша
T
tadpole головастик (граф)
tail конец (дуги)
tangle связка, сплетение, клубок
tanglegram танглграмма
target сток, конец дуги
tenacity прочность (графа)
tensegrity graph тенсегритный граф
terminal vertex концевая вершина, висячая вершина
Terwilliger graph граф Тервиллигера
tetrahedral graph тетраэдральный граф
tesselation замощение, мозаика
theta graph тэта-граф
thickness of a graph толщина графа
Thomsen graph граф Томсена
thorn graph колючий граф
thrackle трекл
threshold graph пороговый граф
throttling number число дросселирования
tiered graph многоярусный граф
Tietze graph граф Титце
tightened graph стягиваемый граф
tight graph плотный граф
tiling замощение
token фишка
token graph маркерный граф
tolerance graph граф толерантности
total chromatic number тотальное хроматическое число
total dominating number, total domination number число тотального доминирования
total graph тотальный граф
tough graph жесткий граф
toughness of a graph жесткость графа
tour маршрут, тур
tournament турнир
traceable number число вычерчиваемости
trail след, маршрут
trampoline трамполин, батут (граф)
transformation graph граф преобразований
transitive graph транзитивный граф
transmission трансмиссия
transversal трансверсаль
trap ловушка
TSP (traveling salesman problem) задача коммивояжера
traversal of a graph обход графа
tree дерево
tree dominating set древесное доминирующее множество
tree domination number число древесного доминирования
tree graph граф каркасов
tree traversal inorder внутренний порядок обхода дерева
tree-like graph древовидный граф
treewidth древесная ширина
triameter триаметр
triangle треугольник
triangle-free graph граф без треугольников
triangular graph треугольный граф
triangulated graph триангулированный граф
triconnected graph трехсвязный граф
trie префиксное дерево, нагруженное дерево
Trinajstic index индекс Тринайстича
tripod тренога (граф)
n-tuple domination -кратное доминирование
trunk ствол
tulgeity дремучесть
Turing machine машина Тьюринга
Tutte polynomial многочлен Татта
twin domination двойное доминирование
U
unavoidable graph неизбежный граф
unbounded face внешняя грань, бесконечная грань (плоского графа)
undecidable problem (алгоритмически) неразрешимая задача
undensity неплотность графа, число независимости, число внутренней устойчивости
underlying graph базовый граф, основной граф
undirected graph неориентированный граф
unicursal graph уникурсальный граф
unicyclic graph унициклический граф, одноциклический граф
uniform hypergraph однородный гиперграф
unigraph униграф
unigraphical (degree) sequence униграфическая (степенная) последовательность
unilateral connectivity односторонняя связность
union of graphs объединение графов
uniquely coloured graph однозначно раскрашиваемый граф
unit acquisition number число прибавления единицы
unit-disk graph единичнодисковый граф
unit distance graph граф единичных расстояний
univoque graph однотонный граф
unit gain graph граф единичного усиления
unknotting number число развязывания
urchin ёж (граф)
utility graph граф полезности
V
vague graph нечеткий граф
valency of a vertex валентность вершины, степень вершины
vertex (of a graph) вершина (графа)
vertex connected graph вершинно-связный граф
vertex connectivity вершинная связность
vertex-deleted вершинно-вычеркнутый
vertex disjoint graphs вершинно непересекающиеся графы
vertex weighted graph вершинно взвешенный граф
visibility graph граф видимости
voltage graph граф напряжения
volvox graph вольвоксовый граф
Voronoi diagram диаграмма Вороного
vulnerability уязвимость
W
walk маршрут
walk-regular graph маршрутно-регулярный граф
wallpaper group кристаллографическая группа
Watkins graph граф Уоткинса
wavelet tree вейвлетное дерево
web graph веб-граф, интернет-граф
weighted graph взвешенный граф
well-hued graph хорошо окрашенный граф
well-located graph хорошо размещенный граф
well-partitioned graph вполне разделенный граф
Wells graph граф Уэлса
Wenger graph граф Венгера
wheel колесо (граф)
Whitney number число Уитни
wide diameter широкий диаметр
width ширина
windmill ветряная мельница (граф)
Wiener-Araya graph граф Винера-Арайи
wirelength протяженность (графа)
witness rectangle graph граф привязочных прямоугольников
word-representable словесно-представимый (граф)
WORM coloring раскраска без радужных и монохроматических подграфов
wounded spider раненый паук (граф)
wreath product of graphs композиция графов (веночное произведение графов)
Y
Yanov schemata схемы Янова
Yutsis graph граф Юциса
Z
Zagreb index загребский индекс
zero-divisor graph граф делителей нуля
zero forcing number число нулевого форсинга
zip product сжатое произведение
Zhang-Zhang polynomial многочлен Чжан-Чжана
zig-zag graph зигзагообразный граф
zombie number число зомби
zone зона, сильно связная область
About the authors
V. A. Voblyi
Всероссийский институт научной и технической информацииРоссийской академии наук
Author for correspondence.
Email: vitvobl@yandex.ru
Russian Federation, Москва
N. A. Arkhipova
Всероссийский институт научной и технической информацииРоссийской академии наук
Email: nataar1956@mail.ru
Russian Federation, Москва
References
- Евстигнеев В. А., Касьянов В. Н. Толковый словарь по теории графов в информатике и программировании Новосибирск Наука 1999
- Евстигнеев В. А., Касьянов В. Н. Словарь по графам в информатике Новосибирск Сибирское Научное Издательство 2009
- Евстигнеев В. А., Касьянов В. Н. Русско-английский и англо-русский словарь по графам в информатике Новосибирск Сибирское Научное Издательство 2011