| In the mathematical field of graph theory, an Archimedean graph is a graph that forms the skeleton of one of the Archimedean solids. | В теории графов архимедов граф - это граф, который образует скелет одного из архимедовых тел. |
| If the degree is 4 or less, or the graph is also edge-transitive, or the graph is a minimal Cayley graph, then the vertex-connectivity will also be equal to d. | Если степень равна 4 или меньше, или граф также рёберно транзитивен, или граф является минимальным графом Кэли, то вершинная связность будет равна d. |
| In the mathematical field of graph theory, the triangle graph is a planar undirected graph with 3 vertices and 3 edges, in the form of a triangle. | В теории графов треугольным графом называется планарный неориентированный граф с тремя вершинами и тремя рёбрами, образующими треугольник. |
| The Hadwiger conjecture in graph theory proposes that if a graph G does not contain a minor isomorphic to the complete graph on k vertices, then G has a proper coloring with k - 1 colors. | Гипотеза Хадвигера делает предположение, что если граф G не содержит минор, изоморфный полному графу с k вершинами, то граф G имеет правильную раскраску в k - 1 цветов. |
| The Turán graph T(n,2) is a complete bipartite graph and, when n is even, a Moore graph. | Граф Турана T(n,2) - это полный двудольный граф, и, если n чётно, это граф Мура. |
| The problems of testing whether a graph is a median graph, and whether a graph is triangle-free, both had been well studied when Imrich, Klavžar & Mulder (1999) observed that, in some sense, they are computationally equivalent. | Задачи проверки, является ли граф медианным, и содержит ли граф треугольники, обе хорошо изучены, и как отмечают Имрих, Клавжар и Мулдер (Imrich, Klavžar, Mulder 1999), в некотором смысле они вычислительно эквивалентны. |
| Now Kőnig's Line Coloring Theorem, stating that the chromatic index equals the maximum vertex degree in any bipartite graph, can be interpreted as stating that the line graph of a bipartite graph is perfect. | Теперь теорема Кёнига о рёберноё раскраске, утверждающая, что хроматический индекс равен максимальной степени вершин в двудольном графе, может быть интерпретирована как утверждение, что рёберный граф двудольного графа совершенен. |
| They are not the only covers involving prisms: for instance, the hexagonal prism can also cover a non-planar graph, the utility graph K3,3, by identifying antipodal pairs of vertices. | Они не только накрывают призмы, например, шестиугольная призма может также накрывать непланарный коммунальный граф КЗ, З путём отождествления антиподальных пар вершин. |
| In this sense, greedy embedding may be viewed as a form of graph drawing, in which an abstract graph (the communications network) is embedded into a geometric space. | В этом смысле жадное вложение можно рассматривать как форма визуализации графов, в котором абстрактный граф (коммуникационная сеть) вкладывается в геометрическое пространство. |
| The cyclic edge connectivity of a graph is the smallest number of edges that may be deleted in such a way that the remaining graph has more than one cyclic component. | Циклическая рёберная связность графа - это наименьшее число рёбер, которое можно удалить так, чтобы оставшийся граф содержал более чем одну циклическую компоненту. |
| Every m-edge string graph can be partitioned into two subsets, each a constant fraction the size of the whole graph, by the removal of O(m3/4log1/2m) edges. | Любой струнный граф с м рёбрами можно разбить на два подмножества, при этом каждое подмножество составляет фиксированную долю полного графа, путём удаления O(m3/4log1/2m) рёбер. |
| A claw is another name for the complete bipartite graph K1,3 (that is, a star graph with three edges, three leaves, and one central vertex). | Клешнёй называется полный двудольный граф K1,3 (то есть звезда с тремя рёбрами, тремя листьями и одной центральной вершиной). |
| It is named after Solomon W. Golomb, who constructed it (with a non-planar embedding) as a unit distance graph that requires four colors in any graph coloring. | Граф назван именем Соломона Вольфа Голомба, который построил его (с непланарным вложением) как граф единичных расстояний, который требует четыре цвета для раскраски. |
| In graph theory the conductance of a graph G=(V, E) measures how "well-knit" the graph is: it controls how fast a random walk on G converges to a uniform distribution. | Проводимость графа G=(V, E) измеряет, насколько «плотно сложен» граф - он контролирует, насколько быстро случайное блуждание на G сходится к равномерному распределению. |
| As with any bipartite graph, the Herschel graph is a perfect graph: the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph. | Как и любой другой двудольный граф, граф Хершеля является совершенным - хроматическое число любого порождённого подграфа равно размеру наибольшей клики этого подграфа. |
| Then the comparability graph of T is trivially perfect, and every trivially perfect graph can be formed in this way. | Тогда граф сравнимости порядка Т тривиально совершенен и любой тривиально совершенный граф может быть сформирован таким образом. |
| The one remaining graph for which this has not yet been done is K1,2,2,2, a seven-vertex apex graph that forms the skeleton of a four-dimensional octahedral pyramid. | Единственный оставшийся граф, для которого это ещё не сделано, это K1,2,2,2, верхушечный граф с семью вершинами, который образует остов четырёхмерной восьмигранной пирамиды. |
| A directed acyclic graph must be planar in order to have an upward planar drawing, but not every planar acyclic graph has such a drawing. | Направленный ациклический граф должен быть планарным, чтобы иметь восходящее планарное представление, но не всякий планарный ациклический граф имеет такое представление. |
| Every complete bipartite graph of the form K2,n is 1-planar, as is every complete tripartite graph of the form K1,1,n. | Любой полный двудольный граф вида K2,n является 1-планарным, как и любой полный дрёхдольный граф вида K1,1,n. |
| Every 3-colorable graph G that contains a triangle (that is, has the complete graph K3 as a subgraph) is homomorphically equivalent to K3. | Любой З-раскрашиваемый граф G, содержащий треугольник (то есть, имеет полный граф K3 в качестве подграфа) гомеоморфно эквивалентен K3. |
| They also have separators, small sets of vertices the removal of which decomposes the graph into connected components whose size is a constant fraction of the size of the whole graph. | Они также имеют сепараторы, небольшое множество вершин, удаление которых разбивает граф на связные компоненты, размер которых составляет постоянную дробную часть от всего графа. |
| Since such graphs have a unique embedding (up to flipping and the choice of the external face), the next bigger graph, if still planar, must be a refinement of the former graph. | Поскольку такие графы имеют единственное вложение (с точностью до выбора внешней грани), следующий больший граф, если он остаётся планарным, должен быть уточнением предыдущего графа. |
| It follows from the handshaking lemma, proven by Leonhard Euler in 1736 as part of the first paper on graph theory, that every cubic graph has an even number of vertices. | Из леммы о рукопожатиях, доказанной Эйлером в 1736 году, как части его первой работы по теории графов, следует, что любой кубический граф имеет чётное число вершин. |
| The graph Q0 consists of a single vertex, while Q1 is the complete graph on two vertices and Q2 is a cycle of length 4. | Граф Q0 состоит из единственной вершины, граф Q1 является полным графом с двумя вершинами, а Q2 - цикл длины 4. |
| This graph, and graphs closely related to it, have been frequently used in graph drawing to prove lower bounds on the area requirements of various styles of drawings. | Этот граф и тесно связанные графы часто используются в области визуализации графов для доказательства нижних границ требующейся площади при различных стилях рисования. |