| Conversely, every median graph G may be represented in this way as the solution set to a 2-satisfiability instance. | И наоборот, любой медианный граф G можно представить в виде множества решений экземпляра задачи 2-выполнимости. |
| A semantic Web, Web 3.0, giant global graph - we're kind of trying out what we want to call this thing. | Семантический веб, веб 3.0, гигантский глобальный граф - всё это попытки дать разные названия одному и тому же. |
| Therefore, the road coloring problem can be stated briefly as: Every finite strongly connected directed aperiodic graph of uniform out-degree has a synchronizing coloring. | Таким образом, задачу о раскраске дорог можно сформулировать коротко следующим образом: Любой конечный сильно связанный апериодичный ориентированный граф с постоянной полустепенью исхода имеет синхронизирующую раскраску. |
| If r = 2, the graph is linear since order-2 domain nodes generate no reflections. | Если г = 2, граф линеен, поскольку узлы порядка 2 не образуют отражений. |
| For k = 2, the unique forbidden minor is the 4-vertex complete graph K4. | Для к = 2 единственным запрещённым минором является полный граф K 4 с 4 вершинами. |
| The strong Papadimitriou-Ratajczak conjecture, that every polyhedral graph has a planar greedy embedding in which all faces are convex, remains unproven. | Строгая гипотеза Пападимитру - Ратайджака, что любой полиэдральный граф имеет планарное жадное вложение, в котором все грани выпуклы, остаётся недоказанной. |
| The following result is due to Herbert Robbins (1939): A graph is 2-edge-connected if and only if it has an ear decomposition. | Следующий результат принадлежит Герберту Робинсону: Граф рёберно 2-связен тогда и только тогда, когда для него существует ушная декомпозиция. |
| In one direction, suppose one is given as input a graph G, and must test whether G is triangle-free. | Для доказательства эквивалентности в одном направлении, предположим, что задан граф G и нужно проверить, есть ли в нём треугольники. |
| A graph is said to be k-factor-critical if every subset of n - k vertices has a perfect matching. | Говорят, что граф к-фактор критический, если любое подмножество из n - k вершин имеет совершенное паросочетание. |
| In this case, the result of applying the Hajós construction is the Moser spindle, a seven-vertex unit distance graph that requires four colors. | В этом случае результатом применения построения Хайоша будет веретено Мозера, граф единичных расстояний с семью вершинами, требующий для раскраски четыре цвета. |
| This auxiliary graph is 1-planar, from which it follows that Ringel's vertex-face coloring problem may also be solved with six colors. | Вспомогательный граф является 1-планарным, откуда следует, что задача Рингеля раскраски вершин и граней может быть решена с использованием шести цветов. |
| So we have the programs and the sporting events and the commercials, and all of the link structures that tie them together make a content graph. | Значит, у нас есть программы, спортивные события и рекламные ролики вместе со всей структурой связей между ними, образующие граф содержания. |
| If a graph can be colored with four colors, then its incidence poset has order dimension at most four (Schnyder 1989). | Если граф можно раскрасить в четыре цвета, то его частично упорядоченное множество инцидентности вершин имеет порядковую размерность, не превосходящую четырёх (Schnyder 1989). |
| Testing whether a given graph has a crossing-free arc diagram of this type (or equivalently, whether it has pagenumber two) is NP-complete. | Проверка, имеет ли данный граф дуговую диаграмму без пересечений этого типа (или, эквивалентно, книжная толщина графа равна двум), является NP-полной задачей. |
| Another result also sometimes known as Wagner's theorem states that a four-connected graph is planar if and only if it has no K5 minor. | Другой результат, который иногда также называют теоремой Вагнера, утверждает, что вершинно 4-связный граф планарен тогда и только тогда, когда он не содержит K5 в качестве минора. |
| Any ten-vertex Hamiltonian 3-regular graph consists of a ten-vertex cycle C plus five chords. | Любой гамильтонов З-регулярный граф с десятью вершинами состоит из цикла с десятью вершинами цикла С, плюс пять хорд. |
| By a result analogous to Fáry's theorem, any toroidal graph may be drawn with straight edges in a rectangle with periodic boundary conditions. | По аналогии с теоремой Фари, любой тороидальный граф можно нарисовать с рёбрами в виде отрезков в прямоугольнике с периодическими границами (то есть противоположные границы квадрата отождествляются). |
| It has been proven that every cycle graph other than C4 has a thrackle embedding, which shows that the conjecture is sharp. | Было доказано, что любой циклический граф, отличный от C4, имеет вложение в виде трекла, что показывает, что гипотеза строга в том смысле, что имеются треклы, в которых число вершин равно числу рёбер. |
| As they showed, when the base graph is biconnected, a graph constructed in this way is planar if and only if its base graph is outerplanar and the matching forms a dihedral permutation of its outer cycle. | Как они показали, если базовый граф двусвязен, граф, полученный из него описанным способом, планарен тогда и только тогда, когда базовый граф внешнепланарен и паросочетание образует диэдральные перестановки внешнего цикла. |
| By using dynamic programming on the SPQR tree of a given graph, it is possible to test whether it is outer-1-planar in linear time. | При помощи динамического программирования на SPQR-дереве заданного графа можно проверить, не является ли граф внешне 1-планарным, за линейное время. |
| It can be constructed as the incidence graph of the partial linear space which is the unique triple cover with no 8-gons of the generalized quadrangle GQ(2,2). | Граф можно построить как граф инциденций частично линейного пространства, которое является единственным тройным накрытием без восьмиугольников обобщённых четырёхугольников GQ (2,2). |
| After this sorting step, parallel edges between the same two vertices will be adjacent to each other in the sorted list and can be split off into a P-node of the eventual SPQR tree, leaving the remaining graph simple. | После этого параллельные рёбра будут стоять рядом в сортированном списке и могут быть отделены в Р-узел конечного SPQR-дерева, что делает оставшийся граф простым. |
| However, an undirected graph may have an exponentially large set of simple cycles, so it would be computationally infeasible to generate and test all such cycles. | Однако неориентированный граф может иметь экспоненциально много простых циклов, так что получить и проверить все эти циклы становится невыполнимой задачей. |
| Every ternary operation on a finite set that satisfies these three properties (but that does not necessarily have 0 and 1 elements) gives rise in the same way to a median graph. | Любая тернарная операция на конечном множестве, удовлетворяющая этим трём свойствам (но не обязательно имеющая элементы 0 и 1) порождает медианный граф. |
| If a connected graph is 2k-regular and has an even number of edges it may also be k-factored, by choosing each of the two factors to be an alternating subset of the edges of an Euler tour. | Если связный граф является 2k-регулярным и имеет чётное число рёбер, он также может быть k-факторизуем путём выбора двух факторов, являющихся чередующимися рёбрами эйлерова цикла. |