Примеры использования Любой граф на Русском языке и их переводы на Английский язык
{-}
-
Official
-
Colloquial
Любой граф имеет слабую 2- раскраску.
Этот пример показывает, что не любой граф с планарным накрытием сам является планарным.
As this example shows, not every graph with a planar cover is itself planar.Любой граф имеет ациклическую ориентацию.
Every graph has an acyclic orientation.Таким образом, любой граф с n вершинами и более чем с n- 1 ребрами, должен содержать цикл.
Thus every graph on n vertices with more than n- 1 edges must contain a cycle.Любой граф имеет базис циклов в котором каждый цикл является порожденным циклом.
Every graph has a cycle basis in which Combinations with other parts of speech
Использование с прилагательными
полный графпланарный графнеориентированный графдвудольный графлюбой графзаданного графаориентированный графсвязный графновый графрегулярный граф
Больше
Использование с глаголами
граф является
граф g является
ориентированного графаоставшийся графграф содержит
стал графомграф называется
граф петерсена является
Больше
Использование с существительными
го графатеории графовтитул графаграф петерсена
вершин графаграф монте-кристо
семейство графовграф сцены
граф пересечений
граф дракула
Больше
Таким образом, любой граф с книжной толщиной два автоматически является планарным.
Therefore, every graph with book thickness two is automatically a planar Любой граф с числом Хадвигера k имеет максимум n2O( k log log k) клик полных подграфов.
Every graph with Hadwiger number k has at most n2O(k log log k) cliques complete subgraphs.Также верно, что любой граф с n вершинами имеет число пересечений, не превосходящее n2/ 4.
It is also true that every graph with n vertices has intersection number at most n2/4.Любой граф, являющийся одновременно кографом и расщепляемым графом, является пороговым.
Every graph that is both a cograph and a split Мун и Мозер( Moon, Moser 1965) показали, что любой граф с n вершинами имеет не более 3n/ 3 наибольших клик.
То есть любой граф имеет либо малый сепаратор, либо укрытие высокого порядка.
That is, every graph has either a small separator or a haven of high order.Чтобы это понять, заметим, что( 1) слабая 2- раскраска является доматическим разбиением, еслинет изолированных вершин, и( 2) любой граф имеет слабую 2- раскраску.
To see this, note that(1) a weak 2-coloring is a domatic partition if there is no isolated vertex,and(2) any graph has a weak 2-coloring.Однако любой граф на счетном множестве вершин имеет нормальное остовное дерево.
However, every graph on a countable set of vertices does have a normal spanning tree.Он гипогамильтонов, что означает, что сам по себе он не имеет гамильтонова цикла но любой граф, образованный удалением отдельной вершины, гамильтонов.
It is hypohamiltonian, which means that it does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from it is Hamiltonian.Любой граф содержит максимум 3n/ 3 наибольших независимых множеств, однако бо́льшая часть графов имеет их куда меньше.
Every graph contains at most 3n/3 maximal independent sets, but many Colin de Verdière 1990 предположил, что любой граф с инвариантом де Вердьера μ может быть раскрашен с использованием не более чем μ+ 1 цветов.
Colin de Verdière(1990) conjectured that any graph with Colin de Verdière invariant μ may be colored with at most μ+ 1 colors.Концепция толщины возникла в гипотезе Фрэнка Харари 1962 года: любой граф с 9 вершинами либо сам, либо его дополнение, является непланарным.
The concept of thickness originates in the 1962 conjecture of Frank Harary: For any graph on 9 points, either itself or its complementary В то время как любой граф допускает k- доминирующее множество, только графы с минимальной степенью k- 1 допускают k- кортежное доминирующее множество.
While every graph admits a k-dominating set, only Эта гипотеза является усилением теоремы о четырех красках, поскольку любой граф, содержащий граф Петерсена в качестве минора, не может быть планарным.
This conjecture is a strengthened form of the four color theorem, because any graph containing the Petersen В частности, любой граф, удовлетворяющий условиям теоремы Оре является либо регулярным полным двудольным графом, либо панциклическим.
Specifically, every graph satisfying the conditions of Ore's theorem is either a regular complete bipartite Конкретнее, определим семейство F графов как имеющее ограниченную путевую ширину, если существует константа p, такая, что любой граф из F имеет путевую ширину, не превосходящую pp.
Specifically, define a family F of При таком построении любой граф Gi является порожденным подграфом графа Gi+ 1, а объединением этой цепочки подграфов является сам граф Радо.
With this construction, each graph Gi is an induced subgraph of Gi+ 1, and the union of this chain of induced subgraphs is the Rado Теорема Хайналя- Семереди о равномерной раскраске утверждает, что любой граф имеет( Δ+ 1)- цветную раскраску, при которой число вершин двух различных цветов отличается максимум на единицу.
The Hajnal-Szemerédi theorem on equitable coloring states that any graph has a(Δ+ 1)-coloring in which the sizes of В частности, любой граф имеет справедливую реберную раскраску, реберную раскраску с оптимальным числом цветов, в которой два класса цветов по размеру отличаются максимум на единицу.
In particular, any graph has an equitable edge coloring, an edge coloring with an optimal number of colors in which every two color classes differ in size by at most one unit.Применяя ту же самую технику к древесной декомпозиции произвольного графа, можно показать, что любой граф имеет сепаратор с размером, не превосходящим его древесной ширины.
By applying the same technique to a tree decomposition of an arbitrary Однако Грох иМаркс также показали, что любой граф с древесной шириной k имеет ежевику полиномиального размера и порядок Ω( k 1/ 2/ log 2 k){\ displaystyle\ Omega k^{ 1/ 2}/\ log^{ 2} k.
However, Grohe andMarx also showed that every graph of treewidth k has a bramble of polynomial size and of order Ω( k 1/ 2/ log 2 k){\displaystyle\Omega k^{1/2}/\log^{2}k.Любой граф G имеет в точности| χ G(- 1)|{\ displaystyle|\ chi_{ G}(- 1)|} различных ациклических ориентаций, так что в этом смысле ациклические ориентации можно понимать как раскраску с- 1 цветом.
Every graph G has exactly| χ G(- 1)|{\displaystyle|\chi_{G}(-1)|} different acyclic orientations, so in this sense an acyclic orientation can be interpreted as a coloring with -1 colors.Одна из формулировок теоремы Турана следующая: Любой граф G( V, E) содержит независимое множество размера, не меньшего| V|/( D+ 1), где D 2| E|/| V|- средняя степень графа. .
One way of stating Turán's theorem is the following: Any graph G(V, E) contains an independent set of size at least|V|/(D+1), where D 2|E|/|V| is the average degree of the Легко показать, что любой граф без мостов имеет нигде не нулевой Z- поток( из теоремы Роббинса), но интересный вопрос возникает при попытке найти нигде не нулевой k- поток для малых значений k.
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.Существует гипотеза( комбинирующая теорему Визинга итеорему Брукса), что любой граф имеет тотальную раскраску, в которой число цветов не превосходит максимальной степени плюс два.
It has been conjectured(combining Vizing's theorem andBrooks' 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.
