INDUCED SUBGRAPH на Русском - Русский перевод

• порожденный подграф
• порожденного подграфа
• порожденном подграфе

Примеры использования Induced subgraph на Английском языке и их переводы на Русский язык

Any induced subgraph of a bipartite graph remains bipartite.
Любой порожденный подграф двудольного графа остается двудольным.

A cograph is a graph in which every connected induced subgraph has a disconnected complement.
Кограф- это граф, в котором любой связный порожденный подграф имеет несвязное дополнение.

Thus, any induced subgraph inherits the distances of the larger graph.
Таким образом, любой порожденный подграф наследует расстояния большего графа.

A perfect graph is a graph in which the clique number equals the chromatic number in every induced subgraph.
Совершенный граф- это граф, в котором кликовое число равно хроматическому числу в каждом порожденном подграфе.

A cograph is a graph in which every nontrivial induced subgraph has at least two vertices with the same neighbourhoods.
Кограф- это граф, в котором любой нетривиальный порожденный подграф имеет по меньшей мере две вершины с совпадающими окрестностями.

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

An undirected graph is perfect if, in every induced subgraph, the chromatic number equals the size of the largest clique.
Неориентированный граф является совершенным, если в каждом порожденном подграфе хроматическое число равно размеру наибольшей клики.

If the input graph is not a Helly circular-arc graph, then the algorithm returns a certificate of this fact in the form of a forbidden induced subgraph.
Если входной граф не является циркулярным графом дуг Хелли, то алгоритм возвращает подтверждение этого факта в виде запрещенного порожденного подграфа.

Any induced subgraph of a comparability graph is itself a comparability graph, formed from the restriction of the partial order to a subset of its elements.
Любой Порожденный подграф графа сравнимости сам является графом сравнимости, образованным из частичного порядка путем сужения на подмножество элементов.

Perfectly orderable graphs, the graphs that can be ordered in such a way that a greedy coloring algorithm is optimal on every induced subgraph.
Идеально упорядочиваемые графы- графы, которые можно упорядочить таким образом, что алгоритм жадной раскраски является оптимальным для любого порожденного продграфа.

It is easy to see that bipartite graphs are perfect: in any nontrivial induced subgraph, the clique number and chromatic number are both two and therefore both equal.
Легко видеть, что двудольные графы совершенны- в любом нетривиальном порожденном подграфе, как кликовое число, так и хроматическое число равны двум.

A perfect graph is a graph in which the chromatic number and the size of the maximum clique are equal, and in which this equality persists in every induced subgraph.
Совершенный граф- это граф, в котором хроматическое число и размер максимальной клики равны, и в котором это равенство существует в любом индуцированном подграфе.

The degeneracy of a graph G was defined by Lick& White(1970) as the least k such that every induced subgraph of G contains a vertex with k or fewer neighbors.
Вырожденность графа G Лик и Уайт определили как наименьшее число k, для которого любой порожденный подграф графа G содержит вершину с k и менее соседями.

A graph is said to be maximal-clique irreducible if every maximal clique has an edge that belongs to no other maximal clique, and hereditary maximal-clique irreducible if the same property is true for every induced subgraph.
Говорят, что граф имеет несводимые наибольшие клики, если любая наибольшая клика содержит ребро, которое не принадлежит никакой другой наибольшей клике, и наследственно несводимые наибольшие клики, если это свойство верно для любого подграфа.

It is NP-hard, as a special case of the problem of finding the largest induced subgraph with a hereditary property as the property of being bipartite is hereditary.
Задача NP- трудна, так как является специальным случаем нахождения наибольшего порожденного подграфа с наследственным свойством так как свойство двудольности наследуется.

In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph.
В теории графов вполне упорядочиваемый граф- это граф, вершины которого можно упорядочить так, что алгоритм жадной раскраски с этим упорядочением оптимально раскрашивает любой порожденный подграф заданного графа.

Thus, if a subfamily of the cographs(such as the planar cographs) is closed under induced subgraph operations then it has a finite number of forbidden induced subgraphs..
Так, если семейство кографов( таких как планарные кографы) замкнуто относительно операции построения порожденного подграфа, то оно имеет конечное число запрещенных порожденных подграфов..

Suppose that the problem is closed under induced subgraphs(if a solution of size≤ k exists in a given graph, then a solution of this size or smaller also exists in every induced subgraph) and that there exists an efficient subroutine that determines whether a solution Y of size k+ 1 can be compressed to a smaller solution of size k.
Предположим, что задача замкнута относительно порожденных подграфов( если решение существует для⩽ k{\ displaystyle\ leqslant k} для данного графа, то решение этого размера или меньшего существует для любого порожденного подграфа) и что существует эффективная процедура, которая определяет, может ли решение Y размера k+ 1{\ displaystyle k+ 1} быть сжато до меньшего решения размера k.

Line graphs of trees have been used to find graphs with a given number of edges and vertices in which the largest induced subgraph that is a tree is as small as possible.
Реберные графы деревьев используются для поиска графов с заданным числом ребер и вершин, в котором наибольший порожденный подграф, являющийся деревом как можно меньшего размера.

Given a simple graph G(V, E), the set of triples of the vertex set V whose induced subgraph has an odd number of edges forms a two-graph on the set V. Every two-graph can be represented in this way.
Если дан обычный граф G( V, E), то набор троек вершин из V, у которых порожденный подграф имеет нечетное число ребер, образует два- граф на V. Любой два- граф можно представить в таком виде.

The graph is both chordal(every cycle of length greater than three has a diagonal) and distance-hereditary every connected induced subgraph has the same distances as the whole graph.
Граф является и хордальным( любой цикл с длиной, превосходящей три, имеет диагональ), и дистанционно- наследуемым любой связный порожденный подграф имеет те же расстояния, что и весь граф.

Perfect graphs may also be described as the graphs in which, in every induced subgraph, the size of the largest independent set is equal to the number of cliques in a partition of the graph's vertices into a minimum number of cliques.
Совершенные графы можно также описать как графы, в которых для любого порожденного подграфа размер наибольшего независимого множества равен числу клик в разложении вершин графа на минимальное число клик.

The same technique can be applied to finding sets of edges for graph properties closed under subgraphs(rather than induced subgraph), or for other properties beyond graph theory.
Ту же самую технику можно применять для нахождения множеств ребер для свойств графов, замкнутых относительно подграфов( отличных от порожденного подграфа) или других свойств в теории графов.

Based on the characterization of cographs as the graphs without induced subgraph isomorphic to a chordless path with four vertices, the clique-width of many graph classes defined by forbidden induced subgraphs has been classified.
Основываясь на описании кографов как графов без порожденных подграфов, изоморфных путям без хорд, была классифицирована кликовая ширина многих классов графов, определенных запрещенными порожденными подграфами..

Perfect matchings may be used to provide another characterization of the claw-free graphs: they are exactly the graphs in which every connected induced subgraph of even order has a perfect matching.
Совершенные паросочетания могут быть использованы для еще одной характеристики графов без клешней- это в точности те графы, в которых любой связный порожденный подграф четного порядка имеет совершенное паросочетание.

Thus, perfection(defined as the equality of maximum clique size and chromatic number in every induced subgraph) is equivalent to the equality of maximum independent set size and clique cover number.
Таким образом, совершенство( определенное как равенство размера максимальной клики и хроматического числа в любом порожденном подграфе) эквивалентно максимуму размера независимого множества и числа кликового покрытия.

In graph theory, a branch of discrete mathematics, a distance-hereditary graph(also called a completely separable graph) is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph.
В теории графов дистанционно- наследуемый граф( или вполне сепарабельный граф)- это граф, в котором расстояния в любом связном порожденном подграфе те же самые, что и в исходном графе.

More formally, a graph G is said to be perfectly orderable if there exists an ordering π of the vertices of G, such that every induced subgraph of G is optimally colored by the greedy algorithm using the subsequence of π induced by the vertices of the subgraph..
Более формально, говорят, что граф G вполне упорядочиваемый, если существует упорядочение π вершин графа G, такое, что любой порожденный подграф графа 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..
Как и любой другой двудольный граф, граф Хершеля является совершенным- хроматическое число любого порожденного подграфа равно размеру наибольшей клики этого подграфа..

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.