| The Möbius-Kantor graph is the Levi graph of the Möbius-Kantor configuration, a system of 8 points and 8 lines that cannot be realized by straight lines in the Euclidean plane. | Граф Мёбиуса - Кантора является графом Леви конфигурации Мёбиуса - Кантора, системы из 8 точек и 8 линий, которые нельзя реализовать с помощью прямых линий на евклидовой плоскости. |
| Alternately, if a graph possesses a monotone property, then every supergraph of this graph on the same vertex set also possesses it. | Альтернативно, если граф обладает монотонным свойством, тогда любой суперграф этого графа на том же наборе вершин тоже обладает этим свойством. |
| Among them are a 92 vertex graph by Horton published in 1982, a 78 vertex graph by Owens published in 1983, and the two Ellingham-Horton graphs (54 and 78 vertices). | Среди них - граф с 92 вершинами, опубликованный Хортоном в 1982, граф с 78 вершинами, который опубликовал Оуэнс в 1983, и два графа Эллингхама - Хортона (с 54 и 78 вершинами). |
| A directed 1-forest - most commonly called a functional graph (see below), sometimes maximal directed pseudoforest - is a directed graph in which each vertex has outdegree exactly one. | Ориентированный 1-лес, часто называемый функциональным графом (см ниже), а иногда - максимальным ориентированным псевдолесом, - это ориентированный граф, в котором каждая вершина имеет исходящую степень в точности равную единице. |
| Because it is a bipartite graph that has an odd number of vertices, the Herschel graph does not contain a Hamiltonian cycle (a cycle of edges that passes through each vertex exactly once). | Поскольку граф является двудольным и имеет нечётное число вершин, он не содержит гамильтонов цикл (цикл из рёбер, который проходит через каждую вершину в точности один раз). |
| By repeatedly simplifying the graph whenever such a subgraph is found, they reduce the problem to one in which the remaining graph has bounded treewidth, at which point it can be solved by dynamic programming. | Повторно упрощая граф, когда такой подграф находится, они сводят задачу к задаче, в которой оставшийся граф ограничен древесной шириной, и с этого момента задача может быть решена с помощью динамического программирования. |
| With this construction, each graph Gi is an induced subgraph of Gi + 1, and the union of this chain of induced subgraphs is the Rado graph itself. | При таком построении любой граф Gi является порождённым подграфом графа Gi + 1, а объединением этой цепочки подграфов является сам граф Радо. |
| In computational geometry and robot motion planning, a visibility graph is a graph of intervisible locations, typically for a set of points and obstacles in the Euclidean plane. | В вычислительной геометрии и планировании движений роботов граф видимости - это граф взаимной видимости точек пространства, обычно для множества точек и преград на евклидовой плоскости. |
| For k = 3, every k-critical graph (that is, every odd cycle) can be generated as a k-constructible graph such that all of the graphs formed in its construction are also k-critical. | Для к=З любой к-критический граф (то есть любой нечётный цикл) может быть построен как к-конструируемый граф таким образом, что все графы, образованные при его построении, являются также к-критическими. |
| If the complete graph Kn + 1 has a perfect 1-factorization, then the complete bipartite graph Kn, n also has a perfect 1-factorization. | Если полный граф Kn + 1 имеет совершенную 1-факторизацию, то полный двудольный граф Kn, n также имеет совершенную 1-факторизацию. |
| The ChromaticPolynomial function in the computer algebra system Mathematica uses the second recurrence if the graph is dense, and the first recurrence if the graph is sparse. | Функция ChromaticPolynomial в системе компьютерной алгебры Mathematica использует вторую рекуррентную формулу если граф плотный, и первую, если граф разреженный. |
| If a graph G has a haven of order k, with k >= h3/2n1/2 for some integer h, then G must also have a complete graph Kh as a minor. | Если граф G имеет укрытие порядка k, при k >= h3/2n1/2 для некоторого целого h, тогда G должен также иметь полный граф Kh в качестве минора. |
| Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types of sets that are used to form an intersection representation of them. | Любой граф можно представить как граф пересечений, но некоторые важные специальные классы можно определить посредством типов множеств, используемых для представления в виде пересечений множеств. |
| However, apex graphs are intimately connected to bounded local treewidth: the minor-closed graph families F that have bounded local treewidth are exactly the families that have an apex graph as one of their forbidden minors. | Однако верхушечные графы тесно связаны с графами с ограниченной локальной древесной шириной - замкнутые по минорам семейства графов F, имеющие ограниченную локальную древесную ширину, являются в точности семействами, одним из запрещённых миноров которых является какой-либо верхушечный граф. |
| The hypercube graph Qn (for n > 1): is the Hasse diagram of a finite Boolean algebra. is a median graph. | Граф гиперкуба Qn (n > 1): является диаграммой Хассе конечной булевой алгебры; является медианным графом. |
| Additionally, if a graph G has clique-width k, then the graph power Gc has clique-width at most 2kck. | Кроме того, если граф G имеет кликовую ширину k, то степень графа Gc имеет кликовую ширину, не превосходящую 2kck. |
| For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three. | Например, рёбра графа на иллюстрации можно раскрасить в три цвета, но нельзя раскрасить в два, так что граф имеет хроматический индекс З. |
| More generally, a graph G has an upward planar drawing if and only if it is directed and acyclic, and is a subgraph of an st-planar graph on the same vertex set. | Более обще, граф G имеет восходящее планарное представление тогда и только тогда, когда он ориентированный, ациклический и является подграфом st-планарного графа на том же самом наборе вершин. |
| This is because every undirected graph can be thought of as a directed graph where every arc (u, v) appears together with its inverse arc (v, u), and this does not change the definition of homomorphism. | Это потому, что любой неориентированный граф можно рассматривать как ориентированный, в котором любая дуга (u, v) появляется вместе с обратной дугой (v, u), а это не меняет определение гомоморфизма. |
| Alternatively, a graph is outerplanar if and only if it does not contain K4 or K2,3 as a minor, a graph obtained from it by deleting and contracting edges. | Альтернативно, граф внешнепланарен тогда и только тогда, когда он не содержит K4 или K2,3 в качестве минора, графа, полученного путём удаления и стягивания рёбер. |
| The graph of a triangular prism is also a Halin graph: it can be drawn so that one of its rectangular faces is the exterior cycle, and the remaining edges form a tree with four leaves, two interior vertices, and five edges. | Граф треугольной призмы является также графом Халина - его можно нарисовать так, что одна из его прямоугольных граней будет внешним циклом, а оставшиеся рёбра образуют дерево с четырьмя листьями, двумя внутренними вершинами и пятью рёбрами. |
| His method generalizes naturally to the construction of a median graph for any set of species and binary characteristics, which has been called the median network or Buneman graph and is a type of phylogenetic network. | Его метод обобщается естественным образом для построения медианного графа любого множества видов и бинарных характеристик, и этот граф называют медианной сетью или графом Бунемана и он представляет собой филогенетическую сеть. |
| For example, the king's graph, a graph whose vertices are squares of a chessboard and whose edges represent possible moves of a chess king, is a strong product of two path graphs. | Например, граф ходов короля, граф, в котором вершинами являются клетки шахматной доски, а рёбра представляют возможные ходы короля, является сильным произведением двух путей. |
| In graph theory, a covering graph may also refer to a subgraph that contains either all edges (edge cover) or all vertexes (vertex cover). | В теории графов накрывающий граф может также относиться к подграфу, который содержит либо все рёбра (рёберное покрытие), либо все вершины (вершинное покрытие ). |
| By applying the same technique to a tree decomposition of an arbitrary graph, it is possible to show that any graph has a separator of size at most equal to its treewidth. | Применяя ту же самую технику к древесной декомпозиции произвольного графа, можно показать, что любой граф имеет сепаратор с размером, не превосходящим его древесной ширины. |