Sta znaci na Engleskom МАКСИМАЛЬНАЯ КЛИКА - prevod na Енглеском

• maximal clique
• maximum clique

Примери коришћења Максимальная клика на Руском и њихови преводи на Енглески

В этом случае I∪{ x}- максимальное независимое множество и C- максимальная клика.
In this case, I∪{x} is a maximum independent set and C is a maximum clique.

В этом случае, C∪{ x}- максимальная клика и I- максимальное независимое множество.
In this case, C∪{x} is a maximum clique and I is a maximum independent set.

Максимальная клика такого графа соответствует прямым в определении структуры инцидентности.
The maximal cliques of such a graph correspond to the lines in the incidence structure definition.

Для каждой вершины с меткой максимальная клика- это максимальная клика, полученная у потомков вершины.
For a node labeled 0, the maximum clique is the maximum among the cliques computed for that node's children.

Кограф- это граф, все порожденные подграфы которого обладают свойством, что любая максимальная клика пересекается с любым наибольшим независимым множеством в единственной вершине.
A cograph is a graph all of whose induced subgraphs have the property that any maximal clique intersects any maximal independent set in a single vertex.

В графе Аполлония любая максимальная клика- это полный граф с четырьмя вершинами, образованный выбором любой вершины и трех ближайших соседей.
In an Apollonian network, every maximal clique is a complete graph on four vertices, formed by choosing any vertex and its three earlier neighbors.

Максимальная клика- это клика, которая не может быть расширена путем включения дополнительных смежных вершин, то есть нет клики большего размера, включающей все вершины данной клики..
A maximal clique is a clique that cannot be extended by including one more adjacent vertex, that is, a clique which does not exist exclusively within the vertex set of a larger clique..

Клика графа G- это множество X вершин графа G, обладающих свойством, что любая пара различных вершин X соединена ребром в G. Максимальная клика графа G- это клика X вершин графа G, такая что нет клики Y вершин графа G, которая содержит все вершины X плюс по меньшей мере еще одну вершину.
A clique of a graph G is a set X of vertices of G with the property that every pair of distinct vertices in X are adjacent in G. A maximal clique of a graph G is a clique X of vertices of G, such that there is no clique Y of vertices of G that contains all of X and at least one other vertex.

Для вершины с меткой 1 максимальная клика будет объединением клик, вычисленных для потомков вершины, а размер этой клики равен сумме размеров клик.
For a node labeled 1, the maximum clique is the union of the cliques computed for that node's children, and has size equal to the sum of the children's clique sizes.

Пусть G- расщепляемый граф, разложенный на клику C и независимое множество I. Тогда любая максимальная клика в расщепленном графе либо совпадает с C, либо является окрестностью вершины из I. Таким образом, в расщепляемом графе легко найти максимальную клику и, кроме того, максимальное независимое множество.
Let G be a split graph, partitioned into a clique C and an independent set I. Then every maximal clique in a split graph is either C itself, or the neighborhood of a vertex in I. Thus, it is easy to identify the maximum clique, and complementarily the maximum independent set in a split graph.

См., в частности, стр. 21-" Максимальная клика( а потому, максимальное независимое множество и максимальная упаковка множеств) не может быть аппроксимировано с O( n 1- ϵ){\ displaystyle O( n^{ 1-\ epsilon})} разве только NP⊂ ZPP.
See in particular pp. 21:"Maximum clique(and therefore also maximum independent set and maximum set packing) cannot be approximated to within O( n 1- ϵ){\displaystyle O(n^{1-\epsilon})} unless NP⊂ ZPP.

Найдите размер максимальной клики в таком графе.
Find the size of the maximum clique in such graph.

Однако, клики в наборе C не обязательно должны быть максимальными кликами.
However, the cliques in C do not necessarily have to be maximal cliques.

Выведите одно число- количество вершин в максимальной клике образованного графа.
Print a single number- the number of vertexes in the maximum clique of the given graph.

Таким образом, совершенство( определенное как равенство размера максимальной клики и хроматического числа в любом порожденном подграфе) эквивалентно максимуму размера независимого множества и числа кликового покрытия.
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.

Совершенный граф- это граф, в котором хроматическое число и размер максимальной клики равны, и в котором это равенство существует в любом индуцированном подграфе.
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.

Почти 2d- угольник- это связный граф конечного диаметра d со свойством, что для любой вершины x и любой максимальной клики M существует единственная вершина x' в M, ближайшая к x.
A near 2d-gon is a connected graph of finite diameter d with the property that for every vertex x and every maximal clique M there exists a unique vertex x' in M nearest to x.

Хордальный граф, в котором все максимальные клики и все минимальные кликовые сепараторы имеют один и тот же размер, является k- деревом, а графы Аполлония являются примерами 3- деревьев.
A chordal graph in which all maximal cliques and all minimal clique separators have the same size is a k-tree, and Apollonian networks are examples of 3-trees.

Таким образом, можно за полиномиальное время найти максимальную клику или независимое множество в дистанционно- наследуемом графе или найти его оптимальную раскраску.
Thus, it is possible in polynomial time to find the maximum clique or maximum independent set in a distance-hereditary graph, or to find an optimal graph coloring of any distance-hereditary graph.

Дерево имеет древесную ширину единица по той же причине, что и полные графы а именно, они хордальны и имеют максимальную клику размером два.
A tree has treewidth one by the same reasoning as for complete graphs namely, it is chordal, and has maximum clique size two.

Например, чтобы найти максимальную клику в кографе, вычисляем, проходя снизу вверх, максимальную клику в каждом подграфе, представленным поддеревом кодерева.
For instance, to find the maximum clique in a cograph, compute in bottom-up order the maximum clique in each subgraph represented by a subtree of the cotree.

В этом случае G имеет единственное разложение( C, I) на клику и независимое множество, C является максимальной кликой, и I является максимальным независимым множеством.
In this case, G has a unique partition(C, I) into a clique and an independent set, C is the maximum clique, and I is the maximum independent set.

Другие задачи невозможно аппроксимировать ни с каким постоянным коэффициентом, или даже с полиномиальным коэффициентом( если P≠ NP), и среди таких задач находится задача о максимальной клике.
Others are impossible to approximate within any constant, or even polynomial, factor unless P NP, as in the case of the Maximum Clique Problem.

Многие из известных нижних границ чисел Рамсея появляются из примеров циркулянтных графов, имеющих маленькие максимальные клики и маленькие максимальные независимые множества.
Many of the known lower bounds on Ramsey numbers come from examples of circulant graphs that have small maximum cliques and small maximum independent sets.

Поскольку G совершенен, таковым является и G*, а тогда он имеет максимальную клику K*, размер которой равен числу цветов в этой раскраске, что равно числу различных максимальных независимых множеств в G. Необходимым образом K* содержит различные представления для каждого из этих максимальных множеств.
Because G is perfect, so is G*, and therefore it has a maximum clique K* whose size equals the number of colors in this coloring, which is the number of distinct maximum independent sets in G; necessarily, K* contains a distinct representative for each of these maximum independent sets.

Используя( k- 1)- мерные сортировочные деревья для хранения и выборки координат, алгоритмы Фелснера решают задачи нахождения хроматического числа, максимальной клики и максимального независимого множества за время O( n log k- 1⁡ n){\ displaystyle{ O} n\ log^{ k- 1} n.
Using(k- 1)-dimensional range trees to store and query coordinates, Felsner's algorithms for chromatic number, maximum clique, and maximum independent set can be applied to k-trapezoid graphs in O( n log k- 1⁡ n){\displaystyle{O}(n\log^{k-1}n)} time.

Если задан граф G, его кликовый граф K( G)- это граф, такой что каждая вершина графа K( G) представляет максимальную клику графа G две вершины графа K( G) соединены ребром( смежны), если соответствующие клики имеют хотя бы одну общую вершину.
Given a graph G, its clique graph K(G) is a graph such that every vertex of K(G) represents a maximal clique of G; and two vertices of K(G) are adjacent when the underlying cliques in G share at least one vertex in common.

Таким образом, попеременно беря максимальный размер и суммируя значения для каждой вершины кодерева, мы вычислим максимальный размер клики, а попеременно выбирая максимальную клику и объединяя, построим саму максимальную клику.
Thus, by alternately maximizing and summing values stored at each node of the cotree, we may compute the maximum clique size, and by alternately maximizing and taking unions, we may construct the maximum clique itself.

Вопреки близкой связи между максимальной кликой и максимальным независимом множестве в произвольном графе, задачи нахождения независимого множества и клики могут существенно отличаться, когда решаются на специальном классе графов.
Despite the close relationship between maximum cliques and maximum independent sets in arbitrary graphs, the independent set and clique problems may be very different when restricted to special classes of graphs.

В то время как основные задачи, такие как поиск максимального независимого множества, максимальной клики, раскраски и кликового покрытия остаются NP- полными для двойственных хордальных графов, некоторые варианты задачи о минимальном доминирующем множестве и дереве Штейнера эффективно решаются для двойственных хордальных графов но задача независимого доминирования остается NP- полной.
While some basic problems such as maximum independent set, maximum clique, coloring and clique cover remain NP-complete for dually chordal graphs, some variants of the minimum dominating set problem and Steiner tree are efficiently solvable on dually chordal graphs but Independent Domination remains NP-complete.