| However, while these give an absolute lower bound on the amount of connection needed, most such networks prefer a k-connected graph to a tree, so that failure of an any individual link will not split the network into parts. | Однако, поскольку это даёт абсолютную нижнюю границу на количество необходимого продукта, большинство таких сетей предпочитают рёберно к-связный граф вместо дерева, так что потеря любого отдельной связи не разобьёт сеть на части. |
| Grohe's algorithm performs these simplifications until the remaining graph has a small treewidth, and then applies Courcelle's theorem to solve the reduced subproblem. | Алгоритм Гроэ осуществляет это упрощение, пока оставшийся граф не будет иметь малую древесную ширину, а затем применяет теорему Курселя для решения уменьшенной подзадачи. |
| As Atneosen already observed, if edges may instead pass from one page to another across the spine of the book, then every graph may be embedded into a three-page book. | Как заметил уже Амеозен, если рёбра могут переходить со страницы на страницу (через корешок), то любой граф можно вложить в трёхстраничную книгу. |
| The canonical optimization variant of the above decision problem is usually known as the Maximum-Cut Problem or Max-Cut and is defined as: Given a graph G, find a maximum cut. | Канонический оптимизационный вариант вышеупомянутой задачи разрешимости известен как «задача о максимальном разрезе» и определяется следующим образом: Пусть задан граф G, нужно найти максимальный разрез. |
| Therefore, a strengthened formulation of the Albertson conjecture is that every n-chromatic graph has crossing number at least as large as the right hand side of this formula. | Таким образом, усиленная формулировка гипотезы Албертсона гласит, что любой n-хроматический граф имеет число пересечений, не меньший правой части этой формулы. |
| That is, by assuming a higher level of connectivity, the graph K3,3 can be made unnecessary in the characterization, leaving only a single forbidden minor, K5. | То есть при предположении более высокого уровня связности граф КЗ, З оказывается несущественным для описания, так что остаётся только один запрещённый минор, K5. |
| A k-vertex-connected graph is a graph that cannot be partitioned into more than one component by the removal of fewer than k vertices, or equivalently a graph in which each pair of vertices can be connected by k vertex-disjoint paths. | Вершинно к-связный граф - это граф, который нельзя разбить на несколько компонент путём удаления менее к вершин, или, эквивалентно, это граф, в котором каждая пара вершин может быть соединена к путями, не имеющими общих вершин. |
| When n = 4 {\displaystyle n=4}, there is another strongly regular graph, the Shrikhande graph, with the same parameters as the 4× 4 {\displaystyle 4\times 4} rook's graph. | Если n=4, существует ещё один сильно регулярный граф, а именно, граф Шрикханде, который имеет такие же параметры, что и ладейный граф 4×4. |
| 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 first thirteen items in the list are cubic symmetric graphs with up to 30 vertices (ten of these are also distance-transitive; the exceptions are as indicated): Other well known cubic symmetric graphs are the Dyck graph, the Foster graph and the Biggs-Smith graph. | Первые тринадцать элементов списка - кубические симметричные графы, имеющие до 30 вершин (десять из них - дистанционно-транзитивные), приведены ниже в таблице Другие хорошо известные симметричные кубические графы - это граф Дика, граф Фостера и Граф Бигса - Смита. |
| A graph G is called a domination-perfect graph if γ(H) = i(H) in every induced subgraph H of G. Since an induced subgraph of a claw-free graph is claw-free, it follows that every claw-free graphs is also domination-perfect. | Граф G называется доминантно-совершенным графом, если γ(H) = i(H) в любом порождённом подграфе H графа G. Поскольку порождённый подграф свободного от клешней графа является свободным от клешней, отсюда следует, что любой свободный от клешней граф является доминантно-совершенным. |
| It is not possible for a factor-critical graph to be bipartite, because in a bipartite graph with a near-perfect matching, the only vertices that can be deleted to produce a perfectly matchable graph are the ones on the larger side of the bipartition. | Фактор-критический граф не может быть двудольным, поскольку в двудольном графе с почти совершенным паросочетанием только вершины, которые могут быть удалены для получения графа с совершенным паросочетанием, находятся на большей стороне двудольного графа. |
| 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 получаются как параметры графа Шлефли, когда он рассматривается как строго регулярный граф). |
| Regular graphs of degree at most 2 are easy to classify: A 0-regular graph consists of disconnected vertices, a 1-regular graph consists of disconnected edges, and a 2-regular graph consists of a disjoint union of cycles and infinite chains. | Регулярные графы степени не больше двух легко классифицировать: 0-регулярный граф состоит из изолированных вершин (нуль-граф), 1-регулярный - из изолированных рёбер, а 2-регулярный - из разрозненных циклов. |
| Put another way, the Whitney graph isomorphism theorem guarantees that the line graph almost always encodes the topology of the original graph G faithfully but it does not guarantee that dynamics on these two graphs have a simple relationship. | Таким образом, хотя теорема Уитни гарантирует, что рёберный граф почти всегда содержит в себе закодированную топологию графа G, это не гарантирует, что эти два графа имеют простые динамические связи. |
| On the other hand, if G has large treewidth, then it contains a large grid minor, within which the graph can be simplified while leaving the crossing number unchanged. | С другой стороны, если G имеет большую древесную ширину, то он содержит большой минор-решётку, внутри которого граф может быть упрощён без изменения числа пересечений. |
| More generally, every median graph gives rise to a ternary operation m satisfying idempotence, commutativity, and distributivity, but possibly without the identity elements of a distributive lattice. | Обобщённо - любой медианный граф порождает тернарную операцию м, удовлетворяющую законам идемпотентности, коммутативности и дистрибутивности, но, возможно, без единичного элемента распределённой решётки. |
| Previous partial or special-case results include the following: If G is a finite strongly connected aperiodic directed graph with no multiple edges, and G contains a simple cycle of prime length which is a proper subset of G, then G has a synchronizing coloring. | Частичные результаты или специальные случаи, полученные до доказательства теоремы: Если G - конечный сильно связанный апериодичный ориентированный граф без кратных рёбер и G содержит цикл простой длины, тогда G имеет синхронизирующую раскраску. |
| The following decision problem related to maximum cuts has been studied widely in theoretical computer science: Given a graph G and an integer k, determine whether there is a cut of size at least k in G. This problem is known to be NP-complete. | Следующая задача разрешимости, связанная с максимальным разрезом, широко изучалась в теоретической информатике: Задан граф G и целое число k, определить, имеется ли разрез в G размером, не меньшим k. |
| If the graph is an infinite square lattice grid, then this definition of the Laplacian can be shown to correspond to the continuous Laplacian in the limit of an infinitely fine grid. | Если граф представляет собой бесконечную квадратную решётку, то его определение лапласиана можно связать с непрерывным лапласианом через предел бесконечной решётки. |
| In order to form a bi-secondary structure, a graph must have maximum degree at most three: each base can only participate in one arc of the diagram, in addition to the two links to its neighbors in the base sequence. | Для образования бивторичной структуры граф должен иметь степень, не превосходящую трёх - каждое основание может быть только в одном ребре диаграммы, а также в двух связях с соседними основаниями в последовательности. |
| A leaf power is a graph that is a k-leaf power for some k. | Листовая степень - это граф, являющийся к-листовой степенью для некоторого к. |
| The Levi graph of a system of points and lines usually has girth at least six: Any 4-cycles would correspond to two lines through the same two points. | Граф Леви системы точек и линий обычно имеет обхват по меньшей мере шесть: любой цикл длины 4 должен соответствовать двум линиям, проходящим через те же самые две точки. |
| The graph is aperiodic if and only if the period computed in this fashion is 1. | Граф апериодичен тогда и только тогда, когда период, вычисленный на этой стадии, равен 1. |
| While every graph admits a k-dominating set, only graphs with minimum degree k - 1 admit a k-tuple dominating set. | В то время как любой граф допускает к-доминирующее множество, только графы с минимальной степенью k-1 допускают k-кортежное доминирующее множество. |