Sta znaci na Engleskom РЕБЕРНЫЙ ГРАФ - prevod na Енглеском

• line graph

Примери коришћења Реберный граф на Руском и њихови преводи на Енглески

Другими словами, реберный граф гиперграфа- это граф пересечений семейства конечных множеств.
In other words, the line graph of a hypergraph is the intersection graph of a family of finite sets.

Все они сильно регулярны и имеют те же параметры и спектр, что и реберный граф L( K8) полного графа K8.
They are strongly regular, with the same parameters and spectra as the line graph L(K8) of the complete graph K8.

Можно проверить, является ли реберный граф, или, более обще, граф без клешней, хорошо покрытым за полиномиальное время.
It is possible to test whether a line graph, or more generally a claw-free graph, is well-covered in polynomial time.

Реберный граф графа G определяется как граф пересечений ребер графа G, где каждое ребро рассматривается как множество из двух его конечных вершин.
The line graph of a graph G is defined as the intersection graph of the edges of G, where we represent each edge as the set of its two endpoints.

Задача нахождения оптимальной раскраски такого графа тоже NP- трудна, поскольку( через реберный граф) эта задача обобщает NP- трудную задачу вычисления хроматического числа графа..
It is also NP-hard to find an optimal coloring of the graph, because(via line graphs) this problem generalizes the NP-hard problem of computing the chromatic index of a graph..

Для любого графа G его реберный граф L( G) является свободным от клешней, а потому минимальное наибольшее независимое множество в L( G) является также минимальным доминирующим множеством в LG.
For any graph G, its line graph L(G) is claw-free, and hence a minimum maximal independent set in L(G) is also a minimum dominating set in LG.

Любой двудольный граф является подграфом полного двудольного графа, а значит любой реберный граф двудольнго графа является порожденным подграфом ладейного графа..
Any bipartite graph is a subgraph of a complete bipartite graph, and correspondingly any line graph of a bipartite graph is an induced subgraph of a rook's graph..

Теперь теорема Кенига о реберное раскраске, утверждающая, что хроматический индекс равен максимальной степени вершин в двудольном графе, может быть интерпретирована как утверждение, что реберный граф двудольного графа совершенен.
Now Kőnig's Line Coloring Theorem, stating that the chromatic index equals the maximum vertex degree in any bipartite graph, can be interpreted as stating that the line graph of a bipartite graph is perfect.

Таким образом, хотя теорема Уитни гарантирует, что реберный граф почти всегда содержит в себе закодированную топологию графа G, это не гарантирует, что эти два графа имеют простые динамические связи.
Put another way, the Whitney graph isomorphism theorem guarantees that the line graph almost always encodes the topology of the original graph G faithfully but it does not guarantee that dynamics on these two graphs have a simple relationship.

Для графа G реберный граф L( G) имеет вершины, соответствующие ребрам графа G, и ребра для каждой пары смежных ребер в G. Таким образом, хроматическое число L( G) равно хроматическому индексу G. Если G- двудольный, клики в L( G)- это в точности множества ребер в G, имеющих общую конечную вершину.
If G is a graph, the line graph L(G) has a vertex for each edge of G, and an edge for each pair of adjacent edges in G. Thus, the chromatic number of L(G) equals the chromatic index of G. If G is bipartite, the cliques in L(G) are exactly the sets of edges in G sharing a common endpoint.

Если G- ориентированный граф, то его ориентированный реберный граф или реберный орграф имеет одну вершину для каждой дуги из G. Две вершины, соответствующие дугам из u в v и из w в x из графа G связаны дугой из uv в wx в реберном орграфе, когда v w.
If G is a directed graph, its directed line graph or line digraph has one vertex for each edge of G. Two vertices representing directed edges from u to v and from w to x in G are connected by an edge from uv to wx in the line digraph when v w.

Реберные графы двудольных графов смотри теорему Кенига.
The line graphs of bipartite graphs see Kőnig's theorem.

Ладейные графы( реберные графы полных двудольных графов) являются частным случаем.
The rook's graphs(line graphs of complete bipartite graphs) are a special case.

Реберные графы могут быть описаны девятью запрещенными подграфами и клешня является простейшим из этих девяти графов..
Line graphs may be characterized in terms of nine forbidden subgraphs; the claw is the simplest of these nine graphs..

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

Граф Шрикханде разделяет эти параметры с точно одним другим графом, 4× 4 ладейным графом, то есть реберным графом L( K4, 4) полного двудольного графа K4, 4.
The Shrikhande graph shares these parameters with exactly one other graph, the 4×4 rook's graph, i.e., the line graph L(K4,4) of the complete bipartite graph K4,4.

Реберные графы деревьев- это блоковые графы, в которых любая разрезающая вершина инцидентна максимум двум блокам, или, что то же самое, блоковые графы без клешней.
The line graphs of trees are exactly the block graphs in which every cut vertex is incident to at most two blocks, or equivalently the claw-free block graphs..

Сначала определим производную G′ графа G это- синоним для реберного графа и двойственного графа..
First let us define the derivative G′ of a graph G it is a synonym for line graph and dual graph..

Глобальное описание краусовского типа для реберных графов k- униформных гиперграфов для любого k≥ 3 дано Бержем.
A global characterization of Krausz type for the line graphs of k-uniform hypergraphs for any k≥ 3 was given by Berge 1989.

Реберные графы двудольных графов создают один из ключевых блоков, который используется для доказательства теоремы о совершенных графах.
The line graphs of bipartite graphs form one of the key building blocks of perfect graphs, used in the proof of the strong perfect graph theorem.

Поскольку реберные графы двудольных графов совершенны, дополнения реберных графов двудольных графов тоже совершенны.
Since line graphs of bipartite graphs are perfect, the complements of line graphs of bipartite graphs are also perfect.

Древесная ширина и кликовая ширина также связаны теорией реберных графов- семейство графов имеет ограниченную древесную ширину тогда и только тогда, когда их реберные графы имеют ограниченную кликовую ширину.
Treewidth and clique-width are also connected through the theory of line graphs: a family of graphs has bounded treewidth if and only if their line graphs have bounded clique-width.

Можно связать также теорему Кенига о реберной раскраске с другим классом совершенных графов, реберными графами двудольных графов..
One can also connect Kőnig's Line Coloring Theorem to a different class of perfect graphs, the line graphs of bipartite graphs..

Это обобщает конструкцию реберных графов, в которых каждое ребро мультиграфа заменяется вершиной.
This generalizes the construction of a line graph, in which every edge of the multigraph is replaced by a vertex.

Другая теорема о двудольных графах, о том что хроматический индекс равен максимальной степени графа, эквивалентна совершенству реберного графа двудольных графов..
Another theorem about bipartite graphs, that their chromatic index equals their maximum degree, is equivalent to the perfection of the line graphs of bipartite graphs.

Любое семейство графов имеет ограниченную путевую ширину тогда и только тогда, когда его реберные графы имеют ограниченную линейную кликовую ширину, где линейная кликовая ширина заменяет операцию объединения в определении кликовой ширины на операцию присоединения отдельной новой вершины.
Any family of graphs has bounded pathwidth if and only if its line graphs have bounded linear clique-width, where linear clique-width replaces the disjoint union operation from clique-width with the operation of adjoining a single new vertex.

Пять основных классов совершенных графов, образующих основные случаи этой структурной декомпозиции, это двудольные графы, реберные графы двудольных графов, дополнения двудольных графов, дополнения реберных графов двудольных графов и двойные расщепляемые графы..
The five basic classes of perfect graphs that form the base case of this structural decomposition are the bipartite graphs, line graphs of bipartite graphs, complementary graphs of bipartite graphs, complements of line graphs of bipartite graphs, and double split graphs..

Более обще, число ребер, которые нужно добавить к реберному графу для произвольного дерева, чтобы он содержал гамильтонов путь( размер его гамильтонова дополнения), равно минимальному числу не пересекающихся по ребрам гусениц, на которые дерево может быть разбито.
More generally the number of edges that need to be added to the line graph of an arbitrary tree so that it contains a Hamiltonian path(the size of its Hamiltonian completion) equals the minimum number of edge-disjoint caterpillars that the edges of the tree can be decomposed into.

Реберные графы двудольных графов совершенны- в нем и в любом его порожденном подграфе число цветов, необходимых для любой раскраски вершин, равно числу вершин в наибольшей клике.
The line graphs of bipartite graphs are perfect: in them, and in any of their induced subgraphs, the number of colors needed in any vertex coloring is the same as the number of vertices in the largest complete subgraph.

Реберные графы двудольных графов образуют важное семейство совершенных графов, одно из небольшого числа семейств, использованных Чудновской с соавторами для описания совершенных графов и для того, чтобы показать, что любой граф без нечетных дыр и антидыр совершенен.
Line graphs of bipartite graphs form an important family of perfect graphs: they are one of a small number of families used by Chudnovsky et al.(2006) to characterize the perfect graphs and to show that every graph with no odd hole and no odd antihole is perfect.