| As Schnyder observes, the incidence poset of a graph G has order dimension two if and only if the graph is a path or a subgraph of a path. | Как заметил Шнайдер, частично упорядоченное множество инцидентности вершин графа G имеет порядковую размерность два тогда и только тогда, когда граф является путём или подграфом пути. |
| The 5-regular Clebsch graph is the Keller graph of dimension two, part of a family of graphs used to find tilings of high-dimensional Euclidean spaces by hypercubes no two of which meet face-to-face. | 5-регулярный граф Клебша является графом Келлера размерности два, и входит в семейство графов, используемых для поиска покрытия Евклидовых пространств большой размерности гиперкубами, не имеющими общих граней. |
| The first of these two theorems was the perfect graph theorem of Lovász (1972), stating that a graph is perfect if and only if its complement is perfect. | Первая из этих теорем была теорема о совершенных графах Ласло Ловаса (1972) утверждающая, что граф совершенен тогда и только тогда, когда его дополнение совершенно. |
| The Frucht graph is one of the two smallest cubic graphs possessing only a single graph automorphism, the identity (that is, every vertex can be distinguished topologically from every other vertex). | Граф Фрухта - это один из двух минимальных кубических графов, имеющих единственный автоморфизм - тождественность (таким образом, любая вершина может быть топологически отличима от остальных). |
| Conversely, as Lefschetz shows, whenever a graph G has a set of cycles with this property, they necessarily form the face cycles of an embedding of the graph onto the sphere. | В обратную сторону, как показал Лефшец, если граф G имеет набор циклов с этим свойством, он обязательно формирует циклы граней при вложении в сферу. |
| The tensor product of graphs is the category-theoretic product and the exponential graph is the exponential object for this category. | Тензорное произведение графов является произведением в теории категорий и экспоненциальный граф является экспоненциальным объектом для категории. |
| Here, a linear forest is an acyclic graph with maximum degree two, i.e., a disjoint union of path graphs. | Здесь линейный лес - это ациклический граф с максимальной степенью два, то есть, дизъюнктное объединение путей. |
| It is named after Peter G. Doyle and Derek F. Holt, who discovered the same graph independently in 1976 and 1981 respectively. | Дойла и Дерека Ф. Холта, обнаружившими граф независимо в 1976 и 1981 соответственноy. |
| A graph G is said to be k-factorable if it admits a k-factorization. | Говорят, что граф G k-факторизуем, если он позволяет k-разбиение. |
| Two nice theorems in this direction are Jaeger's 4-flow theorem (every 4-edge-connected graph has a nowhere-zero 4-flow) and Seymour's 6-flow theorem (every bridgeless graph has a nowhere-zero 6-flow). | Две элегантные теоремы в этом направлении - теорема Джагера о 4-потоке (любой рёберно 4-связный граф имеет нигде не нулевой 4-поток) и теорема Сеймура о 6-потоке (любой граф без мостов имеет нигде не нулевой 6-поток). |
| For example, this characterization can be used to show that the following graph is not a line graph: In this example, the edges going upward, to the left, and to the right from the central degree-four vertex do not have any cliques in common. | Например, такая характеристика может быть использована, чтобы показать, что следующий граф не является рёберным: В этом примере рёбра, идущие от центральной вершины 4-й степени вверх, влево и вправо не содержат общих клик. |
| Goddard, Hedetniemi, and Hedetniemi also demonstrated a graph in which the eternal domination number of the graph is less than the clique covering number. | В. Годдарда, С. М. Хедетними и С. Т. Хедетними также продемонстрировали граф, у которого вечное доминирующее множество графа меньше минимального размера кликового покрытия. |
| For direct proofs that the octahedral graph and the pentagonal-prism graph are the only two planar forbidden minors, see Dai & Sato (1990) and El-Mallah & Colbourn (1990). | Прямое доказательство того, что граф октаэдра и пятиугольной призмы являются единственными двумя планарными запрещёнными минорами, смотрите статьи Даи, Сато (Dai, Sato 1990) и Эль-Маллаха, Колбоурна (El-Mallah, Colbourn 1990). |
| According to Kron, "Diakoptics, or the Method of Tearing, is a combined theory of a pair of storehouses of information, namely equations+graph, or matrices+graph, associated with a given physical or economic system.". | По Крону, «Диакоптика, или метод расчленений, объединяет три источника информации, а именно: графы + уравнения, графы + матрицы, граф + коммутативная диаграмма, связанные с данной физической или экономической системой. |
| The problems of checking whether two self-complementary graphs are isomorphic and of checking whether a given graph is self-complementary are polynomial-time equivalent to the general graph isomorphism problem. | Задача проверки, являются ли два самодополнительных графа изоморфными и проверка, является ли заданный граф самодополнительным, эквивалентны по времени выполнения общей задаче проверки изоморфизма графов. |
| In particular, it is bad to have the scene graph contained within the spatial partitioning system, as the scene graph is better thought of as the grander system to the spatial partitioning. | В частности, плохой практикой является хранение графа сцены в системе разбиения пространства, поскольку лучше понимать граф сцены как систему более высокого уровня по отношению к разбиению пространства. |
| That is, if an n-vertex graph G is p-degenerate, then a monochromatic copy of G should exist in every two-edge-colored complete graph on cp n vertices. | Таким образом, если граф G с n вершинами является p-вырожденным, то монохроматическая копия графа G должна существовать в любом окрашенном двумя цветами графе с cp n вершинами. |
| In some versions of graph minor theory the graph resulting from a contraction is simplified by removing self-loops and multiple adjacencies, while in other version multigraphs are allowed, but this variation makes no difference to Wagner's theorem. | В некоторых версиях теории миноров графа полученный после стягивания рёбер граф упрощается путём удаления петель и кратных рёбер, в то время как в других версиях мультиграфы разрешаются, но эти вариации несущественны для теоремы Вагнера. |
| For each possible choice of whether a stretcher or its complement or a proper wheel exists within the given Berge graph, the graph can be shown to be in one of the basic classes or to be decomposable. | В зависимости от того, существует ли растяжка, дополнение к растяжке или собственное колесо внутри заданного графа Бержа, можно показать, что граф принадлежит одному из базовых классов, или может быть подвергнут декомпозиции. |
| Although there is little difference mathematically between a graph and its transpose, the difference may be larger in computer science, depending on how a given graph is represented. | Хотя математически разница между графом и ему транспонированным графом не велика, в информатике разница может оказаться очень большой, в зависимости от способа, каким граф представлен. |
| In any directed acyclic graph, it is a vacuous truth that every k divides all cycles (because there are no directed cycles to divide) so no directed acyclic graph can be aperiodic. | В любом направленном ациклическом графе является истинным, но совершенно бессодержательным, утверждение, что любое число к делит все циклы (поскольку вообще нет направленных циклов), так что никакой направленный ациклический граф не может быть апериодичным. |
| Then Aanderaa and Rosenberg formulated a new conjecture (the Aanderaa-Rosenberg conjecture) which says that deciding whether a graph possesses a non-trivial monotone graph property requires Ω(n2) queries. | Тогда Аандераа и Розенберг сформулировали новую гипотезу (гипотезу Аандераа - Розенберга), которая утверждает, что решение, обладает ли граф нетривиальным монотонным свойством, требует Ω (n 2) {\displaystyle \Omega (n^{2})} запросов. |
| 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. |
| So both the Spanning Caterpillar Problem and the MSCP have linear time algorithms if a graph is an outerplanar, a series-parallel, or a Halin graph. | Таким образом, как задача о стягивающей гусенице, так и задача о минимальной стягивающей гусенице имеют алгоритмы линейного времени, если граф внешнепланарен, является параллельно-последовательным графом, или графом Халина. |
| 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 рёбрами, названные именем румынского химика Александру Т. Балабана. |