| Then, the greedy insertion algorithm for adding a set of values to a cuckoo hash table succeeds if and only if the cuckoo graph for this set of values is a pseudoforest, a graph with at most one cycle in each of its connected components. | Тогда жадный алгоритм вставки множества значений в кукушкину хеш-таблицу успешно завершается тогда и только тогда, когда кукушкин граф для этого множества значений является псевдолесом, графом максимум с одним циклом в каждой компоненте связности. |
| Since circle graph coloring with four or more colors is NP-hard, and since any circle graph can be formed in this way from some book embedding problem, it follows that optimal book embedding is also NP-hard. | Поскольку раскраска кругового графа в четыре и более цветов является NP-трудной задачей, и поскольку любой круговой граф может быть образован таким образом из некоторой задачи нахождения книжного вложения, нахождение оптимального книжного вложения является также NP-трудной задачей. |
| The result of Häggkvist's construction is a 10-regular triangle-free graph with 29 vertices and chromatic number 4, disproving the conjecture that there is no 4-chromatic triangle-free n-vertex graph in which each vertex has more than n/3 neighbours. | В результате получаем 10-регулярный граф без треугольников с 29 вершинами и хроматическим числом 4, что опровергает гипотезу, по которой не существует графа без треугольников с хроматическим числом 4 и n вершинами, в котором каждая вершина имеет больше чем n/3 соседей. |
| Take a graph G and let M and M' be two matchings in G. Let G' be the resultant graph from taking the symmetric difference of M and M'; i.e. (M - M') ∪ (M' - M). | Возьмём граф G и пусть M и M' будут двумя паросочетаниями в G. Пусть G' будет результатом взятия симметрической разности M и M'. |
| This problem is also referred to as the Degree-Diameter Subgraph Problem, as it contains the degree diameter problem as a special case (namely, by taking a sufficiently large complete graph as a host graph). | Эта задача называется MaxDDBS, и она содержит проблему размера - диаметра в качестве частного случая (а именно, если взять достаточно большой полный граф в качестве графа-хозяина). |
| That is, if a graph G is formed as the union of k k-cliques that intersect pairwise in at most one vertex, then G can be k-colored. | То есть, если граф G образован объединением k k-клик, которые попарно пересекаются не более чем в двух вершинах, граф G может быть раскрашен в k-цветов. |
| An impossible edge (also known as a fake edge) is an edge which has been added to the graph solely to preserve the property that the exit block postdominates all blocks. | Impossible edge, ложное ребро ребро, добавленное в граф исключительно ради сохранения свойства графа о постдоминировании выходного блока над любым другим блоком. |
| So, when there is only one face that contributes a nonzero amount, it is not possible for the total to be zero and the graph must be non-Hamiltonian. | И если имеется лишь одна такая грань, общая сумма не может быть нулевой и граф должен быть негамильтонов. |
| Frontend (the main chip of DVB-card) has received transponder parameters and other parameters via the bus-line I2C, a graph has been built. | Фронтенд (главный чип DVB-карты) получил параметры транспондера и другие параметры через шину I2C, был построен граф. |
| In other words, a graph is half-transitive if its automorphism group acts transitively upon both its vertices and its edges, but not on ordered pairs of linked vertices. | Другими словами, граф полутранзитивен, если его группа автоморфизмов действует транзитивно как на вершины, так и на рёбра, но не на упорядоченные пары связанных вершин. |
| It has been conjectured (combining Vizing's theorem and Brooks' theorem) that any graph has a total coloring in which the number of colors is at most the maximum degree plus two, but this remains unproven. | Существует гипотеза (комбинирующая теорему Визинга и теорему Брукса), что любой граф имеет тотальную раскраску, в которой число цветов не превосходит максимальной степени плюс два. |
| The graph C is a double cover (or 2-fold cover or 2-lift) of H: the preimage of each node in H has size 2. | Граф С является двойным покрытием (или двукратным покрытием) графа Н - прообраз каждой вершины из Н имеет размер 2. |
| The statement of the theorem is itself long and involved, but in short it establishes that such a graph must have the structure of a clique-sum of smaller graphs that are modified in small ways from graphs embedded on surfaces of bounded genus. | Утверждение теоремы длинно и запутано, но, вкратце, теорема устанавливает, что такой граф должен иметь структуру суммы по кликам меньших графов, которые получаются небольшой модификацией графов, вложенных в поверхности ограниченного рода. |
| It is easy to show that every graph without a bridge has a nowhere-zero Z-flow (a form of Robbins theorem), but interesting questions arise when trying to find nowhere-zero k-flows for small values of k. | Легко показать, что любой граф без мостов имеет нигде не нулевой Z-поток (из теоремы Роббинса), но интересный вопрос возникает при попытке найти нигде не нулевой k-поток для малых значений k. |
| A graph with crossing number k is necessarily k-planar, but not necessarily vice versa. | Граф с числом пересечений к обязательно к-планарен, но обратное не обязательно верно. |
| In the maximum-weight independent set problem, the input is an undirected graph with weights on its vertices and the output is an independent set with maximum total weight. | В задаче о независимом множестве максимального веса входом служит неориентированный граф с весами, заданными для вершин, а выходом - независимое множество с максимальным общим весом. |
| Additionally, every 3-vertex-connected 1-planar graph has a 1-planar drawing in which at most one edge, on the outer face of the drawing, has a bend in it. | Кроме того, любой вершинно З-связный 1-планарный граф имеет 1-планарный рисунок, в котором максимум одно ребро на внешней грани имеет изгиб. |
| If a graph is drawn without crossings using an arc diagram in which each edge is a single semicircle, then the drawing is a two-page book embedding, something that is only possible for the subhamiltonian graphs, a subset of the planar graphs. | Если граф нарисован без пересечений дуг в виде дуговой диаграммы, в которой каждое ребро представлено одной полуокружностью, рисунок является двустраничным книжным вложением, что возможно только для подгамильтоновых графов, подмножества планарных графов. |
| It is named after British astronomer Alexander Stewart Herschel, who wrote an early paper concerning William Rowan Hamilton's icosian game: the Herschel graph describes the smallest convex polyhedron for which this game has no solution. | Граф назван по имени британского астронома А. С. Хершеля, написавшего раннюю работу по поводу игры «Икосиан» Уильяма Роуэна Гамильтона - граф Хершеля даёт наименьший выпуклый многогранник, для которого игра не имеет решения. |
| Tietze's graph is also named after him; it describes the boundaries of a subdivision of the Möbius strip into six mutually-adjacent regions, found by Tietze as part of an extension of the four color theorem to non-orientable surfaces. | Граф Титце также назван в его честь; он описывает границы разбиения ленты Мебиуса на шесть взаимно смежных областей, найденных Титце в рамках обобщения теоремы о четырёх красках на неориентированные поверхности. |
| Cook (2003) shows that a still life pattern in Conway's Game of Life may be partitioned into two smaller still lifes if and only if an associated switch graph contains a regular cycle. | Кук показал, что конфигурация в в игре «Жизнь» может быть разбита на две меньшие конфигурации тогда и только тогда, когда граф ассоциированного графа путевых стрелок содержит регулярный цикл. |
| For any finite or countably infinite number of colors χ, there exists a unique countably-infinite χ-edge-colored graph Gχ such that every partial isomorphism of a χ-edge-colored finite graph can be extended to a full isomorphism. | Для любого конечного или счётного бесконечного числа цветов χ существует единственный счётно-бесконечный граф Gχ с раскраской рёбер в χ цветов, такой, что любой частичный изоморфизм конечного графа с раскраской в χ цветов может быть расширен до полного изоморфизма. |
| The graphs of branchwidth 1 are the graphs in which each connected component is a star; the minimal forbidden minors for branchwidth 1 are the triangle graph (or the two-edge cycle, if multigraphs rather than simple graphs are considered) and the three-edge path graph. | Графы с шириной ветвления 1 - это графы, в которых каждая связная компонента является звездой, а минимальные запрещённые миноры для графов с шириной ветвления 1 - это треугольный граф (или цикл из двух дуг, если рассматриваются мультиграфы) и пути из трёх дуг. |
| More generally, if there exists an n-vertex graph that is not a 1-shallow minor of any graph in the family, then the family must be n-biclique-free, because all n-vertex graphs are 1-shallow minors of Kn, n. | В частности, если существует граф с n вершинами, не являющийся 1-неглубокими минором, то семейство должно быть свободным от n-биклик, поскольку все графы с n вершинами являются 1-неглубокими минорами графа Kn, n. |
| A Hanan grid graph for a finite set of points in the plane is produced by the grid obtained by intersections of all vertical and horizontal lines through each point of the set. | Граф Ханана для конечного множества точек на плоскости получается из решётки, полученной пересечением всех вертикальных и горизонтальных линий, проходящих через каждую точку множества. |