Concise English-Russian dictionary on graph theory

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.

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 зона, сильно связная область