| This results in a disconnected graph on 4n vertices with 3n edges (Ai - Bi, Ai - Ci and Ai - Di for 1 <= i <= n). | Результатом будет несвязный граф с 4n вершинами и 3n рёбрами (Ai-Bi, Ai-Ci и Ai-Di для 1<=i<=n). |
| If the integers are the first q positive integers, where q is the number of edges, the graph and the labelling are called supermagic. | Если метки - первые q целых положительных чисел, где q - число рёбер, то граф и его разметка называются супермагическими. |
| Barnette's conjecture, a still-open combination of Tait's and Tutte's conjecture, states that every bicubic polyhedral graph is Hamiltonian. | Гипотеза Барнетта - не опровергнутая и не доказанная комбинация гипотез Тэта и Татта - утверждает, что любой бикубический граф многогранника является гамильтоновым. |
| It produces as output a circle packing whose tangencies represent the given graph, and for which the circles representing the external vertices have the radii specified in the input. | Алгоритм даёт упаковку кругов, точки касания которых представляют заданный граф и для которого круги, представляющие внешние вершины, имеют заданный во входе радиус. |
| A graph is called domination perfect if it has a minimum dominating set that is independent, and if the same property holds in all of its induced subgraphs. | Граф называется совершенным графом доминирования, если он имеет минимальное доминирующее множество, являющееся независимым множеством вершин, и если тем же самым свойством обладают все порождённые подграфы. |
| The Hajnal-Szemerédi theorem on equitable coloring states that any graph has a (Δ + 1)-coloring in which the sizes of any two color classes differ by at most one. | Теорема Хайналя - Семереди о равномерной раскраске утверждает, что любой граф имеет (Δ + 1)-цветную раскраску, при которой число вершин двух различных цветов отличается максимум на единицу. |
| The Gray graph can be constructed (Bouwer 1972) from the 27 points of a 3× 3× 3 grid and the 27 axis-parallel lines through these points. | Граф Грея можно построить из 27 точек решётки размером 3×3×3 и 27 прямых, параллельных осям и проходящих через эти точки. |
| Like beta-skeletons, and unlike Delaunay triangulations, it is not a geometric spanner: for some point sets, distances within the Gabriel graph can be much larger than the Euclidean distances between points (Bose et al. 2006). | Подобно бета-скелетам и в отличие от триангуляции Делоне данный граф не является геометрическим стягивающим деревом - для некоторых множеств точек расстояния в графе Габриэля могут быть много больше евклидовых расстояний между точками. |
| Outerplanar graphs have treewidth at most two, which implies that many graph optimization problems that are NP-complete for arbitrary graphs may be solved in polynomial time by dynamic programming when the input is outerplanar. | Внешнепланарные графы имеют древесную ширину, не превосходящую 2, откуда следует, что много задач оптимизации на графах, которые NP-полны для графов общего вида, могут быть решены за полиномиальное время с помощью динамического программирования, если входом служит внешнепланарный граф. |
| Bipartite graphs may be recognized in polynomial time but, for any k > 2 it is NP-complete, given an uncolored graph, to test whether it is k-partite. | Распознавание двудольных графов может быть выполнено за полиномиальное время, но для любого к > 2 задача определения, является ли данный неокрашенный граф k-дольным, становится NP-полной. |
| A graph formed from a collection of equal-radius circles, in which two circles are connected by an edge if one circle contains the centre of the other circle. | Граф, сформированный из набора окружностей одинакового радиуса, в котором два круга соединены ребром, если центр одной окружности находится внутри другой. |
| There are only finitely many graphs that are neither apex graphs nor have another non-apex graph as a minor. | Существует лишь конечное число графов, которые не являются верхушечными графами и не содержат в качестве минора другой граф, не являющийся верхушечным. |
| A class of orderings somewhat more general than series-parallel partial orders is provided by PQ trees, data structures that have been applied in algorithms for testing whether a graph is planar and recognizing interval graphs. | Класс упорядочений, несколько более общий понятию последовательно-параллельных частичных порядков, задаётся PQ-деревьями, структурами данных, применяемых в алгоритмах для проверки, является ли граф планарным, и распознавания интервальных графов. |
| At the integer points k = 3, 4, ... {\displaystyle k=3,4,\dots}, the corresponding decision problem of deciding if a given graph can be k-colored is NP-hard. | В целых точках к = З, 4, ... {\displaystyle k=3,4,\dots} соответствующая задача разрешимости определения, может ли данный граф быть раскрашен в k цветов, NP-трудна. |
| In 1973, Stefan Burr and Paul Erdős made the following conjecture: For every integer p there exists a constant cp so that any p-degenerate graph G on n vertices has Ramsey number at most cp n. | В 1973 году Пол Эрдёш и Стефан Бур высказали следующую гипотезу: Для любого целого p существует константа cp, такая, что любой p-вырожденный граф G на n вершинах имеет число Рамсея, не превышающее cp n. |
| One way to do this is to test all 2k + 1 choices of which subset of Y is to be removed from the cover and reintroduced back into the graph. | Один из способов сделать это - тестируем все 2 k + 1 {\displaystyle 2^{k+1}} вариантов, какими множество Y удаляется из покрытия и вставляется обратно в граф. |
| Schnyder's theorem states that a graph G is planar if and only if the order dimension of P(G) is at most three. | Теорема Шнайдера утверждает, что граф G является планарным тогда и только тогда, когда порядковая размерность P (G) {\displaystyle P(G)} не превосходит трёх. |
| This is because the colluding participants Adam and Charlie effectively "split" the secret sharing graph into two separate disconnected components, one containing only Bob, the other containing all other honest participants. | Такой эффект возникает по причине того, что сговорившиеся участники, Адам и Чарли, «раскололи» граф общего доступа на два независимых разрозненных компонента, один из которых состоит только из Боба, другой - из всех остальных честных участников. |
| If a 3-regular graph on a surface is 3-edge-colored, its dual graph forms a triangulation of the surface which is also edge colored (although not, in general, properly edge colored) in such a way that every triangle has one edge of each color. | Если З-регулярный граф на поверхности рёберно З-раскрашиваем, его двойственный граф образует триангуляцию поверхности, которая также рёберно раскрашиваема (хотя, в общем случае, рёберная раскраска неправильна) в том смысле, что каждый треугольник раскрашен в три цвета - по ребру на цвет. |
| In geometry, a Coxeter-Dynkin diagram (or Coxeter diagram, Coxeter graph) is a graph with numerically labeled edges (called branches) representing the spatial relations between a collection of mirrors (or reflecting hyperplanes). | Диаграмма Коксетера - Дынкина (или диаграмма Коксетера, граф Коксетера, схема Коксетера) - это граф с помеченными числами рёбрами (называемыми ветвями), представляющими пространственные связи между набором зеркальных симметрий (или гиперплоскостей зеркальных отражений). |
| For instance, the 11-vertex graph formed by removing a vertex from the regular icosahedron (the graph of the gyroelongated pentagonal pyramid) is both 2-connected and claw-free, so it is factor-critical. | Например, граф с 11 вершинами, образованный вершинами правильного икосаэдра (граф скрученно удлинённой пятиугольной пирамиды), является как 2-связным, так и свободным от клешней, так что он является фактор-критическим. |
| This graph is formed by removing a Hamiltonian cycle (connecting consecutive numbers) from a complete bipartite graph (connecting all pairs of numbers with different parity), and so it has a number of matchings equal to a ménage number. | Этот граф образуется удалением гамильтонова цикла (соединяющего последовательные числа) из полного двудольного графа (соединяющего пары чисел с различной чётностью). |
| As with any bipartite graph, there are no odd-length cycles, and there are also no cycles of four or six vertices, so the girth of the Gray graph is 8. | Как и у любой другой двудольный граф, граф Грея не содержит циклов нечётной длины, а также не содержит циклов с четырьмя или шестью вершинами, так что обхват графа Грея равен 8. |
| For instance, a complete graph on an uncountable set of vertices does not have one: a normal spanning tree in a complete graph can only be a path, but a path has only a countable number of vertices. | Например, полный граф на несчётном множестве вершин не имеет нормального остовного дерева - такое дерево в полном графе может быть только путём, но путь имеет лишь счётное число вершин. |
| Every maximum parsimony evolutionary tree embeds into the Buneman graph, in the sense that tree edges follow paths in the graph and the number of characteristic value changes on the tree edge is the same as the number in the corresponding path. | Любое эволюционное дерево максимального правдоподобия можно вложить в граф Бунемана, в том смысле, что рёбра дерева идут по путям в графе и число изменений характеризующих значений на ребре дерева равно числу соответствующих путей. |