| A complete multipartite graph is a graph that is complete k-partite for some k. | Полный многодольный граф - это граф, который является полным к-дольным для некоторого к. |
| In other words, a graph is an integral graph if all of the roots of the characteristic polynomial of its adjacency matrix are integers. | Другими словами, граф является целым графом, если все корни характеристичесого многочлена его матрицы смежности являются целыми числами. |
| If the graph does not contain any cycles (i.e. it's an acyclic graph), its girth is defined to be infinity. | Если граф не содержит циклов (то есть является ациклическим графом), его обхват по определению равен бесконечности. |
| The Robertson graph is the unique (4,5)-cage graph and was discovered by Robertson in 1964. | Граф Робертсона является уникальной (4,5)-клеткой и его открыл Робертсон в 1964. |
| If a graph family F is closed under the operation of taking induced subgraphs, then every graph in F is also locally F. For instance, every chordal graph is locally chordal; every perfect graph is locally perfect; every comparability graph is locally comparable. | Если семейство графов F замкнуто относительно операции взятия порождённых подграфов, то любой граф в F локально тоже F. Например, любой хордальный граф локально хордален, любой совершенный граф локально совершенен, любой граф сравнимости является графом сравнимости. |
| For instance, the octahedron is the unique connected locally C4 graph, the icosahedron is the unique connected locally C5 graph, and the Paley graph of order 13 is locally C6. | Например, граф октаэдра является единственным локально C4 графом, граф икосаэдра является единственным локально C5 графом, а граф Пэли порядка 13 локально равен C6. |
| According to the Foster census, the Möbius-Kantor graph is the unique cubic symmetric graph with 16 vertices, and the smallest cubic symmetric graph which is not also distance-transitive. | Согласно списку Фостера граф Мёбиуса - Кантора является единственным симметричным графом с 16 вершинами и наименьшим кубическим симметричным графом, который не является дистанционно-транзитивным. |
| One of these two embeddings forms a torus, so the Nauru graph is a toroidal graph: it consists of 12 hexagonal faces together with the 24 vertices and 36 edges of the Nauru graph. | Одно из этих двух вложений образует тор, так что граф Науру является тороидальным графом - он состоит из 12 шестиугольных граней вместе с 24 вершинами и 36 гранями графами Науру. |
| If all triangles found in this way have medians, and the previous algorithm finds that the graph satisfies all the other conditions for being a median graph, then it must actually be a median graph. | Если все треугольники найдены и у всех них есть медианы, а также предыдущий алгоритм определяет, что граф удовлетворяет остальным условиям медианных графов, то он должен быть медианным. |
| For k = 3, there are four forbidden minors: K5, the graph of the octahedron, the pentagonal prism graph, and the Wagner graph. | Для к = З существует четыре запрещённых минора - K5, граф октаэдра, граф пятиугольной призмы и граф Вагнера. |
| In some cases, a graph may be embedded in space in such a way that, for each cycle in the graph, one can find a disk bounded by that cycle that does not cross any other feature of the graph. | В некоторых случаях граф может быть вложен в пространство таким образом, что для каждого цикла в графе можно найти диск, ограниченный этим циклом, который не пересекает другие элементы графа. |
| The NNG (treated as an undirected graph with multiple nearest neighbors allowed) of a set of points in the plane or any higher dimension is a subgraph of the Delaunay triangulation, the Gabriel graph, and the Semi-Yao graph. | ГБС (рассматриваемый как неориентированный граф с разрешением нескольких ближайших соседей) множества точек плоскости или любого пространства более высокой размерности является подграфом триангуляции Делоне, графа Габриэля и полуяова графа. |
| In graph algorithms, therefore, it may sometimes be useful to construct the reversal of a graph, in order to put the graph into a form which is more suitable for the operations being performed on it. | Для алгоритмов на графах, поэтому, иногда было бы полезно построить обратный граф, чтобы привести граф к виду, который более подходит к операциям, применяемым к графу. |
| A cograph is a graph with no induced path on four vertices, P4, and a threshold graph is a graph with no induced P4, C4 nor 2K2. | Кограф - это граф с отсутствием порождённых путей с четырьмя вершинами, P4, а пороговые графы - это графы баз порождённых подграфов P4, C4 или 2K2. |
| Equivalently, a moral graph of a directed acyclic graph G is an undirected graph in which each node of the original G is now connected to its Markov blanket. | Эквивалентно, моральный граф ориентированного ациклического графа G является неориентарованным графом, в котором каждый узел исходного графа G соединяется с его марковским ограждением. |
| Therefore, by Steinitz's theorem, the Herschel graph is a polyhedral graph: there exists a convex polyhedron (an enneahedron) having the Herschel graph as its skeleton. | Поэтому, по теореме Штайница граф Голднера - Харари является полиэдральным графом - существует выпуклый многогранник (эннеаэдр), имеющий граф Хершеля в качестве своего скелета . |
| Similarly, a directed graph is biconnected if, for every two vertices, there exists a simple cycle in the graph containing both of them. | Аналогично, ориентированный граф является двусвязным, если для любых двух вершин существует простой цикл, содержащий обе вершины. |
| A directed graph is called an oriented graph if none of its pairs of vertices is linked by two symmetric edges. | Ориентированный граф называется направленным, если ни одна из его пар вершин не соединена двумя симметричными (разнонаправленными) рёбрами. |
| It can be constructed by joining 2 copies of the cycle graph C3 with a common vertex and is therefore isomorphic to the friendship graph F2. | Граф может быть построен объединением двух копий циклов СЗ по одной общей вершине, а потому граф изоморфен графу дружеских отношений F2. |
| Every chordal graph is a strangulated graph, a graph in which every peripheral cycle is a triangle, because peripheral cycles are a special case of induced cycles. | Любой хордальный граф является сжатым, то есть графом, у которого любой периферийный цикл является треугольником, поскольку периферийные циклы являются специальным случаем порождённого цикла. |
| For instance a complete bipartite graph K1,n has the same line graph as the dipole graph and Shannon multigraph with the same number of edges. | Например, полный двудольный граф K1,n имеет тот же рёберныё граф, что и дипольный граф и мультиграф Шеннона с тем же числом рёбер. |
| The smallest cubic semi-symmetric graph (that is, one in which each vertex is incident to exactly three edges) is the Gray graph on 54 vertices. | Наименьший кубический полусимметричный граф (то есть граф, в котором каждая вершина инцидентна в точности трём рёбрам) является граф Грея с 54 вершинами. |
| Equivalently, every k-critical graph (a graph that requires k colors but for which every proper subgraph requires fewer colors) is k-constructible. | Эквивалентно, любой к-критический граф (граф, требующий к цветов, но любой собственный подграф требует меньше цветов) является к-конструируемым. |
| A universal graph for a family F of graphs is a graph that contains every member of F as a subgraphs. | Универсальный граф для семейства графов F - это граф, который содержит любой элемент семейства F в качестве подграфа. |
| This follows from the fact that it is a Moore graph, since any Moore graph is the largest possible regular graph with its degree and diameter (Hoffman & Singleton 1960). | Это следует из факта, что граф является графом Мура, поскольку граф Мура является наибольшим возможным регулярным графом с такой степенью вершин и диаметром (Hoffman, Singleton 1960). |