| If G is a tree, then G itself is the universal covering graph of G. For any other finite connected graph G, the universal covering graph of G is a countably infinite (but locally finite) tree. | Если граф G является деревом, то G сам по себе является графом универсального накрытия графа G. Для любого другого конечного связного графа G граф универсального накрытия графа G является счётно бесконечным (но локально конечным) деревом. |
| For instance, the Levi graph of the Fano plane gives rise to the Heawood graph, a bipartite graph with seven vertices on each side, 21 edges, and no 4-cycles, showing that z(7; 2) >= 21. | Например, граф Леви плоскости Фано даёт граф Хивуда, двудольный граф с семью вершинами в каждой доле, с 21 рёбрами и не имеющий 4-циклов, что показывает, что z(7; 2) >= 21. |
| They defined somewhere dense graph classes as those classes of graphs for which there exists a threshold t such that every complete graph appears as a t-subdivision in a subgraph of a graph in the class. | Они определили местами плотные классы графов как классы, для которых существует такой порог t, что любой полный граф появляется как t-подраздел в подграфе графов класса. |
| With more efficiency, and greater complication, one can test whether a graph is claw-free by checking, for each vertex of the graph, that the complement graph of its neighbors does not contain a triangle. | Несколько эффективнее, но сложнее, можно проверить, что граф не имеет клешней путём проверки для каждой вершины графа, что дополнение графа соседей вершины не содержит треугольника. |
| It follows that every optimal 1-planar graph is Eulerian (all of its vertices have even degree), that the minimum degree in such a graph is six, and that every optimal 1-planar graph has at least eight vertices of degree exactly six. | Отсюда следует, что любой оптимальный 1-планарный граф является эйлеровым (все его вершины имеют чётную степень), что наименьшая степень в таких графах - 6, и что любой оптимальный 1-планарный граф имеет по меньшей мере восемь вершин со степенью в точности шесть. |
| For partial 3-trees there are four forbidden minors: the complete graph on five vertices, the octahedral graph with six vertices, the eight-vertex Wagner graph, and the pentagonal prism with ten vertices. | Для частичных З-деревьев имеется четыре запрещённых минора - полный граф с пятью вершинами, октаэдральный граф с шестью вершинами, Граф Вагнера с восемью вершинами и граф пятигольной призмы с десятью вершинами. |
| Alternatively, every graph that requires k colors may be formed by combining the Hajós construction, the operation of identifying any two nonadjacent vertices, and the operations of adding a vertex or edge to the given graph, starting from the complete graph Kk. | Альтернативно, любой граф, требующий к цветов, может быть образован комбинированием построения Хайоша, операциями объединения двух несмежных вершин и операциями добавления вершин или рёбер к заданному графу, начав с полного графа Кк. |
| As with higher dimensional unit disk graphs, it is possible to transform a set of points into their indifference graph, or a set of unit intervals into their unit interval graph, in linear time as measured in terms of the size of the output graph. | Как и с многомерными графами единичных дисков, можно преобразовать множество точек в их индифферентный граф или множество единичных отрезков в их граф единичных отрезков за линейное время, если измерять в терминах размера выходного графа. |
| In particular, if we choose a k-coloring for every finite subgraph of an infinite graph G, then there is a k-coloring of G in which each finite graph has a larger supergraph whose coloring agrees with the coloring of the whole graph. | В частности, если мы выбираем к-раскраску для любого конечного подграфа бесконечного графа G, тогда существует k-раскраска графа G, в которой каждый конечный граф имеет больший суперграф, раскраска которого согласуется с раскраской всего графа. |
| It makes use of the following theorem: Theorem: For an undirected graph, G, the following properties are equivalent: Graph G is triangulated. | Для этого используется следующая теорема: Теорема: Для неориентированного графа G следующие свойства эквивалентны: Граф G триангулирован. |
| In 1986, Heiko Harborth presented the graph that would bear his name, the Harborth Graph. | В 1986 году Хейко Харборт представил граф, который получил его имя - граф Харборта. |
| Graph theory Complex network Scale-free network Random graph Structural cut-off Barabási, A.-L. and R. Albert, Science 286,509 (1999). | Теория графов Комплексные сети Безмасштабная сеть Случайный граф Структурный срез Barabási, A.-L. and R. Albert, Science 286,509 (1999). |
| It is NP-hard, and more specifically complete for the existential theory of the reals, to test whether a given graph is a unit distance graph, or is a strict unit distance graph (Schaefer 2013). | Является NP-трудной задачей, точнее полной для теории существования вещественных чисел, проверить, является ли данный граф графом единичных расстояний или строгим графом единичных расстояний (Schaefer 2013). |
| The first few graphs in this sequence are the graph M2 = K2 with two vertices connected by an edge, the cycle graph M3 = C5, and the Grötzsch graph M4 with 11 vertices and 20 edges. | Несколько первых графов в этой последовательности - это графы M2 = K2 с двумя вершинами, соединёнными ребром, цикл M3 = C5 и граф Грёча с 11 вершинами и 20 рёбрами. |
| The node, and the graph associated with it, may have one of four types, given the initials SPQR: In an S node, the associated graph is a cycle graph with three or more vertices and edges. | Узел и граф, ассоциированный с ним, могут быть одного из четырёх типов, дающих аббревиатуру SPQR: Узел типа S (series = последовательное соединение), ассоциированный граф является циклом с тремя и более вершинами и рёбрами. |
| Since the graph is invariant, its structure is "cached" in main memory by the QPOP application, so as to avoid unnecessary and inefficient repeated accesses to the database. | Поскольку граф является инвариантным, его структура "кэшируется" в основной памяти программой ОВ во избежание ненужных и неэффективных повторяющихся запросов к базе данных. |
| On the other hand, except for these two points, no graph can have a chromatic root at a real number smaller than or equal to 32/27. | С другой стороны, за исключением этих двух случаев, никакой граф не может иметь в качестве хроматического корня вещественное число, меньшее либо равное 32/27. |
| A chordal graph in which all maximal cliques and all minimal clique separators have the same size is a k-tree, and Apollonian networks are examples of 3-trees. | Хордальный граф, в котором все максимальные клики и все минимальные кликовые сепараторы имеют один и тот же размер, является к-деревом, а графы Аполлония являются примерами З-деревьев. |
| If a circle graph has girth at least five (that is, it is triangle-free and has no four-vertex cycles) it can be colored with at most three colors. | Если круговой граф имеет обхват по меньшей мере пять (то есть в нём нет треугольников и циклов с четырьмя вершинами), его можно раскрасить, уложившись в три цвета. |
| On the other hand, if there exists a module in which one of these two subsets is empty, then the graph is disconnected or co-disconnected and again (with the three simple exceptions) it has a skew cutset. | С другой стороны, если существует модуль, в котором одно из этих двух подмножеств пусто, то граф несвязен или ко-несвязен и снова (за исключением трёх простых случаев) он имеет косое сечение. |
| A nontrivial graph is a cactus if and only if every block is either a simple cycle or a single edge. | Нетривиальный граф является кактусом тогда и только тогда, когда любой его блок либо является простым циклом, либо одиночным ребром. |
| The r = 2 case can be rephrased as stating that every complete graph with an even number of vertices has an edge coloring whose number of colors equals its degree, or equivalently that its edges may be partitioned into perfect matchings. | Случай г = 2 можно переформулировать как утверждение, что любой полный граф с чётным числом вершин имеет рёберную раскраску, число цветов которой равно его степени, или, эквивалентно, что рёбра могут быть разбиты на совершенные паросочетания. |
| However, an edge-transitive graph need not be symmetric, since a-b might map to c-d, but not to d-c. | Однако рёберно-транзитивный граф не обязательно симметричен, поскольку а-Ь может быть переведён в c-d, но не в d-c. |
| Among them: A cograph is a graph which does not contain the path P4 on 4 vertices (and hence of length 3) as an induced subgraph. | Среди них: Кограф - это граф, не содержащий путь P4 с 4 вершинами (то есть длины 3) в качестве порождённого подграфа. |
| If a graph has a skew partition, so does its complement. | Если граф имеет косое разбиение, имеет такое разбиение и его дополнение. |