| Spinrad (1994) gives an O(n2)-time algorithm that tests whether a given n-vertex undirected graph is a circle graph and, if it is, constructs a set of chords that represents it. | Спинрад представил алгоритм, работающий за время O(n2), который проверяет, является ли заданный неориентированный граф с n вершинами круговым, и если он круговой, строит множество хорд, которые дают круговой граф. |
| For instance there are three nonisomorphic 10-cages, each with 70 vertices: the Balaban 10-cage, the Harries graph and the Harries-Wong graph. | Например, существует три неизоморфных 10-клетки, каждая с 70 вершинами - 10-клетка Балабана, граф Харриса и граф Харриса - Вонга. |
| Heer, Bostock & Ogievetsky (2010) write that arc diagrams "may not convey the overall structure of the graph as effectively as a two-dimensional layout", but that their layout makes it easy to display multivariate data associated with the vertices of the graph. | Хир, Босток и Огиветски написал, что дуговые диаграммы «не могут выражать полной структуры графа так же эффективно, как это делает двумерное представление», но позволяет проще представить многомерные данные, связанные с вершинами графами. |
| There are n! different sequences of vertices that might be Hamiltonian paths in a given n-vertex graph (and are, in a complete graph), so a brute force search algorithm that tests all possible sequences would be very slow. | Есть n! различных последовательностей вершин, которые могут быть гамильтоновыми путями в заданном графе с n вершинами (и их столько в полном графе), так что алгоритм полного перебора, который перебирает все возможные последовательности, был бы очень медленным. |
| That is, for every 17-vertex graph G, either G or its complement contains W6 as a subgraph, while neither the 17-vertex Paley graph nor its complement contains a copy of K4. | Таким образом, для любого графа G с 17 вершинами либо сам G, либо его дополнение содержит W6 как подграф, в то время как ни граф Пэли, имеющий 17 вершин, ни его дополнение не содержат K4. |
| In the mathematical field of graph theory, the Tutte 12-cage or Benson graph is a 3-regular graph with 126 vertices and 189 edges named after W. T. Tutte. | 12-клетка Тата или граф Бенсона - это 3-регулярный граф с 126 вершинами и 189 рёбрами, названный в честь У. Т. Тата. |
| In 1979, Hatzel improves this result with a planar hypohamiltonian graph on 57 vertices: the Hatzel graph. | В 1979 Хатцель улучшил этот результат, найдя планарный гипогамильтонов граф с 57 вершинами - граф Хатцеля. |
| In particular the Grötzsch graph, an 11-vertex graph formed by repeated application of Mycielski's construction, is a triangle-free graph that cannot be colored with fewer than four colors, and is the smallest graph with this property. | В частности, граф Грёча, граф с 11 вершинами, образованный повторением конструкции Мычельского, является графом без треугольников, который нельзя раскрасить меньше чем четырьмя цветами, и является наименьшим графом с этими свойствами. |
| In the mathematical field of graph theory, the Balaban 11-cage or Balaban (3-11)-cage is a 3-regular graph with 112 vertices and 168 edges named after Alexandru T. Balaban. | 11-клетка Балабана или (3-11)-клетка Балабана - это 3-регулярный граф с 112 вершинами и 168 рёбрами, названные именем румынского химика Александру Т. Балабана. |
| The answer is provided in 1976 by Carsten Thomassen, who exhibits a 105-vertices construction, the 105-Thomassen graph. | Первый ответ дал в 1976 Карстен Томассен, который представил построение графа со 105 вершинами, 105-граф Томассена. |
| Goldberg & Karzanov (1996) generalized alternating path algorithms to show that the existence of a regular path between any two vertices of a skew-symmetric graph may be tested in linear time. | Голдберг и Карзанов обобщили алгоритмы чередующихся путей, чтобы показать, что существование регулярного пути между любыми двумя вершинами кососимметрического графа может быть проверено за линейное время. |
| If G is K5-free, then G can be obtained via 3-clique-sums from a list of planar graphs, and copies of one special non-planar graph having 8-vertices. | Если G свободен от K5, то G можно получить как 3-кликовые суммы списка планарных графов и копий некоторого специфичного непланарного графа с 8 вершинами. |
| In particular, a form of the birthday paradox implies that, in a random functional graph with n vertices, the path starting from a randomly selected vertex will typically loop back on itself to form a cycle within O(n) steps. | В частности, из одного из вариантов парадокса дней рождения следует, что в случайном функциональном графе с n вершинами путь, начинающийся со случайно выбранной вершины, обычно зацикливается после O(n) шагов. |
| 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). |
| Some properties of a uniquely k-total-colorable graph G with n vertices: χ'(G) = Δ(G) + 1 unless G = K2. | Некоторые свойства однозначно тотально к-раскрашиваемого графа G с n вершинами: χ'(G) = Δ(G) + 1 unless G = K2 Δ(G) <= 2 δ(G). |
| Using this idea, the K5-minor-free graphs may be characterized as the graphs that can be formed as combinations of planar graphs and the eight-vertex Wagner graph, glued together by clique-sum operations. | Если использовать эту идею, графы, не содержащие K5 в качестве минора, можно описать как графы, образованные комбинациями планарного графа и графа Вагнера с шестью вершинами, склеенные вместе посредством сумм по клике. |
| Note that the ability of the algorithm to contract blossoms is crucial here; the algorithm cannot find P in the original graph directly because only out-of-forest edges between vertices at even distances from the roots are considered on line B17 of the algorithm. | Алгоритм не может найти Р в исходном графе прямо, поскольку только рёбра не из леса между вершинами на чётном расстоянии от корня рассматриваются в строке B17 алгоритма. |
| Another equivalent definition of queue layouts involves embeddings of the given graph onto a cylinder, with the vertices placed on a line in the cylinder and with each edge wrapping once around the cylinder. | Другое эквивалентное определение макета очередей использует понятие вложения заданного графа в цилиндр с вершинами, расположенными на прямой, находящейся на поверхности цилиндра, а каждое ребро огибает цилиндр. |
| The number z(n, 2) asks for the maximum number of edges in a bipartite graph with n vertices on each side that has no 4-cycle (its girth is six or more). | Число z(n, 2) соответствует максимальному числу рёбер в двудольном графе с n вершинами в каждой доле, не имеющем циклов длины 4 (его обхват не меньше шести). |
| A 4-cycle C4 has domination number two: any single vertex only dominates itself and its two neighbors, but any pair of vertices dominates the whole graph. | Доминирующее число цикла с 4 вершинами C4 равно двум - любая отдельная вершина доминирует над собой и двумя соседями, но любая пара доминирует над полным графом. |
| Existence requires each of the 3-node subgraphs of this graph, (p q r), (p u s), (q t u), and (r s t), must correspond to a Schwarz triangle. | Для существования тетраэдра Гурса каждый из подграфов с З вершинами этого графа, (р q r), (p u s), (q t u) и (r s t), должны соответствовать треугольнику Шварца. |
| The two vertices u and v may be two vertices in the graph associated with an S node such that either u and v are not adjacent, or the edge uv is virtual. | Две вершины u и v могут быть двумя вершинами в графе, ассоциированном с S-узлом, не смежным либо u, либо v, или ребро uv является виртуальным. |
| To form the Desargues graph in this way, connect ten of the vertices into a regular decagon, and connect the other ten vertices into a ten-pointed star that connects pairs of vertices at distance three in a second decagon. | Для получения графа Дезарга этим способом соединяем десять вершин в правильный десятиугольник и соединяем оставшиеся десять вершин в звезду с десятью вершинами, соединяя пары вершин на расстоянии три. |
| The Desargues graph, a 20-vertex bipartite symmetric cubic graph, is so called because it can be interpreted as the Levi graph of the Desargues configuration, with a vertex for each point and line of the configuration and an edge for every incident point-line pair. | Граф Дезарга, двудольный симметричный кубический граф с 20 вершинами, назван этим именем, поскольку его можно представить как граф Леви конфигурации Дезарга, с вершиной для каждой точки и для каждой прямой и ребром для каждой инциденции точка-прямая. |
| The neighborhood of any vertex in the Schläfli graph forms a 16-vertex subgraph in which each vertex has 10 neighbors (the numbers 16 and 10 coming from the parameters of the Schläfli graph as a strongly regular graph). | Окрестность любой вершины графа Шлефли есть подграф с 16 вершинами, в котором каждая вершина имеет 10 соседних вершин (числа 16 и 10 получаются как параметры графа Шлефли, когда он рассматривается как строго регулярный граф). |