| Russian | English |
| альтернативный граф | alternative graph (ориентированный граф, из каждой вершины которого исходит не более двух дуг) |
| ациклический граф | acyclic graph (структурирование графических данных, описывающих изображение) |
| биориентированный граф | bidirected graph (граф, в котором дуги могут иметь либо начало и конец, либо два начала, либо два конца) |
| блок в графе | lobe graph (часть графа, образованная множеством всех рёбер, сильно циклически связанных с данным ребром) |
| вершина графа | highway |
| вырожденный граф | trivial graph (граф, содержащий только одну вершину) |
| граф без «3-звезды» | claw-free graph |
| граф группы | group graph (вершины представляют элементы группы, рёбра — результаты выполнения операций с использованием генераторов группы, графы строятся для конечных групп) |
| граф пересечений | circular-arc graph (отрезков прямых линий) |
| граф смежности областей | region adjacency graph (зон) |
| двудольный граф | bipartite graph (граф, в котором множество вершин распадается на два непересекающихся подмножества так, что каждое ребро соединяет вершину из одного подмножества с вершиной из другого подмножества) |
| двусвязный граф для любой тройки узлов v, w, а графа существует путь между v и w, не содержащий а biconnectivity двусвязность | biconnected graph (свойство графа) |
| Дезаргов граф | Arguesian graph (граф, являющийся дополнением графа Петерсона, т.е. однородного графа третьей степени и десятого порядка) |
| дополнительный граф | complement graph (граф H дополняет граф G, если множества вершин у них совпадают, а в графе H рёбрами соединены только те вершины, которые не были соединены в графе G) |
| древовидность графа | arboricity of a graph |
| задача о раскраске графа тремя цветами | graph 3-colorability problem |
| корневой граф | rooted graph (граф, в котором существует такой его узел, из которого существуют пути в каждый другой узел графа) |
| критический граф | critical graph (граф, удаление из которого любой вершины с её рёбрами уменьшает его хроматическое число) |
| минимальный граф сети минимального времени вещания | minimum broadcast graph (граф, описывающий структуру (топологию) сети минимального времени вещания, которая имеет минимально возможное число линий связи) |
| насыщенный граф | dense graph (граф, в котором мощность множества рёбер близка к квадрату мощности множества вершин) |
| неориентированный граф | undirected graph (граф с неориентированными рёбрами) |
| несвязный граф | disconnected graph (состоящий из нескольких компонент, каждая из которых представляет собой связный граф) |
| однородный граф | regular graph (граф называется однородным, если локальные степени во всех его вершинах одинаковы) |
| планарный граф | planar graph (граф, который можно нарисовать на плоскости так, чтобы никакие его два ребра не пересекались) |
| плоский граф | planar graph (граф, который можно нарисовать на плоскости так, чтобы никакие его два ребра не пересекались) |
| разреженный граф | sparse graph (граф, в котором мощность множества рёбер много меньше квадрата мощности множества его вершин) |
| раскрашиваемость графа в три цвета | 3-colorability |
| раскрашиваемый граф | colorable graph (граф G называется к-раскрашиваемым, если существует такое приписывание узлам графа целых чисел от 1 до к, называемых цветами, что никаким двум смежным узлам не приписан один и тот же цвет) |
| распределение запросов на основе древовидного графа | tree-based demand assignment (метод предоставления ресурсов по требованию) |
| рёберный или хордовый граф | chordal graph (граф, в котором все его циклы длины четыре или более имеют хорду) |
| связный граф | connected graph (граф, в котором любая пара вершин связана, т.е. соединена маршрутом) |
| сечение графа | cut set (минимальное множество элементов связного графа) |
| сильно связный граф | strongly connected graph (граф, имеющий только одну сильно связную компоненту) |
| слабо связный граф | weakly connected graph (ориентированный граф, который становится связным только в тех случаях, когда ориентация каждой его дуги снимается) |
| узел a графа G | articulation point (если узлы v, w и а различны, и всякий путь между v и w содержит узел а) |
| управляющий граф | control flow graph (модель программы) |
| хроматический граф | chromatic graph (граф называется k-хроматическим, если наименьшее число классов в его возможной раскраске равно к) |
