What is the translation of " ODD CYCLE " in Russian?

• нечетный цикл
• нечетных циклов

Examples of using Odd cycle in English and their translations into Russian

Odd cycles are harmonious, as is the Petersen graph.
Нечетные циклы являются гармоничными графами, как и граф Петерсена.

Correspondingly, the chromatic number of an odd cycle is three.
Соответственно, хроматическое число нечетных циклов равно трем.

Removing this edge from the odd cycle leaves a path, which may be colored using the two colors for its subgraph.
Удаление этого ребра из нечетного цикла оставляет путь, который можно раскрасить двумя цветами.

Alternatively, the imperfection of this graph follows from the perfect graph theorem and the imperfection of the complementary odd cycle.
Или несовершенство этого графа следует из теоремы о совершенных графах и несовершенства дополнений нечетным циклам.

However, if there exists at least one odd cycle, then no 2-edge-coloring is possible.
Однако, если существует хотя бы один нечетный цикл, его ребра нельзя выкрасить в 2 цвета.

An odd cycle of length greater than 3 cannot be perfect, because its chromatic number is three and its clique number is two.
Нечетный цикл длины больше 3 не может быть совершенным, поскольку его хроматическое число равно трем, а кликовое число равно двум.

For example, all complete graphs Kn and all odd cycles(cycle graphs of odd length) are cores.
Например, все полные графы Kn и все нечетные циклы( графов- циклов нечетной длины) являются ядрами.

As there are no odd cycles in G in that case, blossoms will never be found and one can simply remove lines B20- B24 of the algorithm.
Поскольку в этом случае нет нечетных циклов G, цветки никогда не будут найдены и можно просто удалить строки B20- B24 алгоритма.

By Brooks' theorem, every k-regular graph(except for odd cycles and cliques) has chromatic number at most k.
По теореме Брукса любой k- регулярный граф( за исключением нечетных циклов и клик) имеет хроматическое число, не превосходящее k.

See Lovász(1992) If G is(k- 1)-regular, meaning every vertex is adjacent to exactly k- 1 others, then G is either Kk or an odd cycle.
Если граф G( k- 1)- регулярен( каждая вершина смежна в точности k- 1 другим), то граф G либо является полным графом Kk, либо нечетным циклом.

Removing the vertices of an odd cycle transversal from a graph leaves a bipartite graph as the remaining induced subgraph.
Удаление вершин сечения нечетных циклов из графа оставляет двудольный граф в качестве порожденного подграфа.

This applies only to connected graphs; disconnected counterexamples include disjoint unions of odd cycles, or of copies of K2k+1.
Это относится только к связным графам, несвязные контрпримеры содержат несвязное объединение нечетных циклов или копий графа K2k+ 1.

Since the product of two odd cycle graphs contains an odd cycle, the product G× H is not 2-colorable either.
Поскольку произведение двух нечетных циклов содержит нечетный цикл, произведение G× H{\ displaystyle G\ times H} также не может быть раскрашено в 2 цвета.

In other words, the list chromatic number of a connected undirected graph G never exceeds Δ, unless G is a clique or an odd cycle.
Другими словами, предписанное хроматическое число связного неориентированного графа никогда не превосходит Δ, если только G не является кликой или циклом нечетной длины.

Similarly, the complement of an odd cycle of length 2k+ 1 cannot be perfect, because its chromatic number is k+ 1 and its clique number is k.
Похожим образом, дополнительный граф нечетного цикла длины 2k+ 1 не может быть совершенным, поскольку его хроматическое число равно k+ 1, а его кликовое число равно k.

One of these subclasses was the family of claw-free graphs: it was discovered by several authors that claw-free graphs without odd cycles and odd holes are perfect.
Одним из таких подклассов было семейство графов без клешней- несколько авторов обнаружили, что графы без клешней и без нечетных циклов и дыр совершенны.

After this step, each remaining odd cycle contains at least one edge that may be colored with one of the two colors belonging to the opposite subgraph.
Следующим шагом раскрашиваются ребра нечетных циклов, в которых по меньшей мере одно ребро может быть раскрашено одним из двух цветов, принадлежащих противоположному подграфу.

Therefore, if a minimally imperfect graph has a 2-join, it must equal one of its blocks, from which it follows that it must be an odd cycle and not Berge.
Таким образом, если минимальный несовершенный граф имеет 2- соединение, он должен быть равен одному из его блоков, откуда следует, что он должен быть нечетным циклом и не быть графом Бержа.

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.
Для k= 3 любой k- критический граф( то есть любой нечетный цикл) может быть построен как k- конструируемый граф таким образом, что все графы, образованные при его построении, являются также k- критическими.

For any connected undirected graph G with maximum degree Δ, the chromatic number of G is at most Δ unless G is a complete graph or an odd cycle, in which case the chromatic number is Δ+ 1.
Для связного ненаправленного графа G с максимальной степенью Δ хроматическое число графа G не больше Δ, за исключением случаев, когда G- клика или нечетный цикл.

The problem of finding the smallest odd cycle transversal, or equivalently the largest bipartite induced subgraph, is also called odd cycle transversal, and abbreviated as OCT.
Задача нахождения наименьшего сечение нечетных циклов, или, эквивалентно, наибольшего двудольного порожденного подграфа, называется задачей сечения нечетных циклов англ. Odd Cycle Transversal, OCT.

In the other direction, a vertex cover of G◻ K 2{\displaystyle G\square K_{2}} can be transformed into an odd cycle transversal by keeping only the vertices for which both copies are in the cover.
В другом направлении, вершинное покрытие графа G◻ K 2{\ displaystyle G\ square K_{ 2}} может быть преобразовано в сечение нечетных циклов путем сохранения только вершин, для которых обе копии содержаться в покрытии.

For degree two, any odd cycle is such a graph, and for degree three, four, and five, these graphs can be constructed from platonic solids by replacing a single edge by a path of two adjacent edges.
Для степени два любой нечетный цикл является таким графом, а для степеней три, четыре и пять, такие графы можно построить из правильных многогранников путем замены ребер на пути из пар смежных ребер.

More specifically, if the thrackle conjecture is true, the thrackles may be exactly characterized by a result of Woodall: they are the pseudoforests in which there is no cycle of length four and at most one odd cycle.
Конкретнее, если гипотеза о трекле верна, принадлежность треклам может быть в точности выражена результатом Вудала- это псевдолеса, в которых нет циклов длины 4 и имеется по меньшей мере один нечетный цикл.

Conversely from a sequence of odd cycle contractions, each containing the vertex formed from the previous contraction, one may form an ear decomposition in which the ears are the sets of edges contracted in each step.
Обратно, из последовательности стягиваний нечетных циклов, содержащих вершины, полученные на предыдущих стягиваниях, можно образовать ушное разложение, в котором уши образуют множества стягиваемых ребер.

It is now known(the strong perfect graph theorem) that perfect graphs may be characterized as the graphs that do not have as induced subgraphs either an odd cycle or the complement of an odd cycle a so-called odd hole.
Известно( по строгой теореме о совершенных графах), что совершенные графы могут быть охарактеризованы как графы, не имеющие в качестве индуцированных подграфов нечетные циклы или дополнения нечетным циклам так называемые нечетные дыры.

The technique was invented by Reed, Smith and Vetta to show that the problem of odd cycle transversal was solvable in time O(3k kmn), for a graph with n vertices, m edges, and odd cycle traversal number k.
Технику разработали Рид, Смит и Ветта, чтобы показать, что задача об удалении нечетных циклов разрешима за время O( 3 k k m n){\ displaystyle O( 3^{ k} kmn)} для графов с n вершинами, m ребрами и числом удаляемых вершин k.

The odd cycle transversal can be transformed into a vertex cover by including both copies of each vertex from the transversal and one copy of each remaining vertex, selected from the two copies according to which side of the bipartition contains it.
Сечение нечетных циклов может быть преобразовано в вершинное покрытие путем включения обоих копий каждой вершины из сечения и одной копии каждой оставшейся вершины, выбранных из двух копий согласно тому, какой доле разбиения она принадлежит.

Iterative compression has been used successfully in many problems, for instance odd cycle transversal(see below) and edge bipartization, feedback vertex set, cluster vertex deletion and directed feedback vertex set.
Итеративное сжатие испльзовалось успешно во многих задачах, например для удаления нечетных циклов( см. ниже) и удаления ребер для получения двудольности, нахождения разрезающих циклы вершин, удаления кластерных вершин и нахождения разрезающих ориентированные циклы вершин.

For instance, if one contracts the ears of an ear decomposition, in the order given by the decomposition, then at the time each ear is contracted it forms an odd cycle, so the ear decomposition characterization may be used to find a sequence of odd cycles to contract.
Например, если стягивать уши ушного разложения в порядке, заданном разложением, то каждый раз стягиваемое ухо образует нечетный цикл, так что описание с помощью ушного разложения можно использовать для поиска последовательности нечетных циклов для стягивания.