Примери коришћења Подграфы на Руском и њихови преводи на Енглески
{-}
-
Official
-
Colloquial
Все эти подграфы изоморфны дополнению графа Клебша.
These subgraphs are all isomorphic to the complement graph of the Clebsch graph.Сферические сепараторы, построенные таким образом, разбивают входной граф на подграфы, имеющие не более n( d+ 1)/( d+ 2) вершин.
The sphere separators constructed in this way partition the input graph into subgraphs of at most n(d+ 1)/(d+ 2) vertices.Выпуклые подграфы играют важную роль в теории неполных кубов и медианных графов.
Convex subgraphs play an important role in the theory of partial cubes and median graphs.Неглубокий минор или минор ограниченной глубины- это ограниченный вид минора графа, в котором стянутые подграфы имеют малый диаметр.
A shallow minor or limited-depth minor is a restricted form of a graph minor in which the subgraphs that are contracted to form the minor have small diameter.Степени листьев- это подграфы степеней деревьев, порожденные листьями деревьев.
Leaf powers are the subgraphs of powers of trees induced by Таким образом, в этой нотации,Ламановы графы- это в точности( 2, 3)- плотные графы, и подграфы Ламановых графов- это в точности( 2, 3)- разреженные графы.
Thus, in their notation,the Laman graphs are exactly the(2,3)-tight graphs, and the subgraphs of the Laman graphs are exactly the(2,3)-sparse graphs.Если граф не имеет конечного хроматического числа,тогда из теоремы де Брейна- Эрдеша следует, что граф должен содержать конечные подграфы для каждого возможного хроматического числа.
If a graph does not have finite chromatic number,then the De Bruijn-Erdős theorem implies that it must contain finite subgraphs of every possible finite chromatic number.Их алгоритм находит большие планарные подграфы внутри заданного графа, такие, что, если существует незацепленное вложение, они представляют планарное вложение подграфа. .
Their algorithm finds large planar subgraphs within the given graph such that, if a linkless embedding exists, it has to respect the planar embedding of the Заметим, что расстояние здесь измеряется в числе дуг в графе Hi, апотому это расстояние может быть больше расстояния в графе G. Миноры глубины ноль- это то же самое, что подграфы данного графа.
Note that this distance is measured by hop count in Hi, andbecause of that it may be larger than the distance in G. Shallow minors of depth zero are the same thing as subgraphs of the given graph.Термин« клика» пришел из работы Люка и Пери,использовавших полные подграфы при изучении социальных сетей для моделировании клик людей, то есть групп людей, знакомых друг с другом.
The word"clique", in its graph-theoretic usage, arose from the work of Luce& Perry(1949),who used complete subgraphs to model cliques(groups of people who all know each other) in social networks.В частности, путем усечения иерархии сепараторов в подходящем месте можно найти сепаратор размера O( n/√ log n),удаление которого разбивает граф на подграфы размера c log n для любой константы c.
Specifically, by truncating a separator hierarchy at an appropriate level, one may find a separator of size O(n/√log n)the removal of which partitions the graph into subgraphs of size c log n, for any constant c.Понятие остовных деревьев известно втеории графов- t- остова, это остовные подграфы графов с похожими свойствами растяжения, где расстояние между вершинами графа определяется в терминах теории графов.
The notion of graph spanners has been known in graph theory:t-spanners are spanning subgraphs of graphs with similar dilation property, where distances between graph vertices are defined in graph-theoretical terms.Кроме того, подграфы любого графа не могут иметь древесность, большую древесности самого графа, или, эквивалентно, древесность графа должна быть не меньше максимальной древосности его подграфов. .
Additionally, the subgraphs of any graph cannot have arboricity larger than the graph itself, or equivalently the arboricity of a graph must be at least the maximum arboricity of any of its Интуитивно понятно, что бесконечный граф имеет произвольно большие конечные подграфы с любой плотностью, меньшей верхней плотности, и не имеет произвольно больших конечных подграфов с плотностью, большей верхней плотности.
Intuitively, an infinite graph has arbitrarily large finite subgraphs with any density less than its upper density, and does not have arbitrarily large finite Существуют планарные графы с n вершинами( для произвольно больших значений n), такие, чтодля любого сепаратора S, разбивающего оставшийся граф на подграфы с не более чем 2n/ 3 вершинами, S имеет по меньшей мере√( 4π√ 3)√ n вершин, примерно 1. 56√ n.
There exist n-vertex planar graphs(for arbitrarily large values of n) such that,for every separator S that partitions the remaining graph into subgraphs of at most 2n/3 vertices, S has at least√(4π√3)√n vertices, approximately 1.56√n.Определение не изменится, если вместо порожденных подграфов брать произвольные подграфы, поскольку непорожденный подграф может иметь степени вершин, не превосходящие степеней вершин порожденного с тем же набором вершин подграфа. .
The definition would be the same if arbitrary Для молекулярной структуры, описываемой планарным графом G, резонансным графом( или графом Z- преобразований) графа G является граф, вершины которого описывают совершенные паросочетания графа G, аребра которого соединяют пары совершенных паросочетаний, симметрическая разность которых является внутренней гранью графа G. Полициклические ароматические углеводороды могут быть описаны как подграфы шестиугольной мозаики плоскости, а резонансные графы описывают возможные структуры с двойными связями этих молекул.
For a molecular structure described by a planar graph G, the resonance graph or(Z-transformation graph) of G is a graph whose vertices describe perfect matchings of G andwhose edges connect pairs of perfect matchings whose symmetric difference is an interior face of G. Polycyclic aromatic hydrocarbons may be described as subgraphs of a hexagonal tiling of the plane, and the resonance graph describes possible double-bond structures of these molecules.Любой максимальный планарный граф может быть разложен на вершинно 4- связные максимальные планарные подграфы путем разделения вдоль треугольников( не являющихся гранями графа)- если имеется треугольник, не являющийся гранью, можно образовать два меньших максимальных планарных графа, один состоит из части, находящейся внутри треугольника, другой состоит из внешней по отношению к треугольнику части.
Any maximal planar graph may be decomposed into 4-vertex-connected maximal planar subgraphs by splitting it along its separating triangles(triangles that are not faces of the graph): given any non-facial triangle: one can form two smaller maximal planar graphs, one consisting of the part inside the triangle and the other consisting of the part outside the triangle.Обратно- из любой ежевики порядка k, можно построить укрытие того же порядка путем определения β( X)( для каждого X) какX- борта, который включает все подграфы в ежевике, не имеющие общих точек с X. Требование, что подграфы в ежевике касаются друг друга, может быть использован для того, чтобы показать, что такой X- борт существует, и что все борты β( X), выбранные таким способом, касаются друг другом.
Conversely, from any bramble of order k, one may construct a haven of the same order, by defining β(X)(for each choice of X)to be the X-flap that includes all of the subgraphs in the bramble that are disjoint from X. The requirement that the subgraphs in the bramble all touch each other can be used to show that this X-flap exists, and that all of the flaps β(X) chosen in this way touch each other.Например, в техническом отчете 2003 года" Book embeddings of graphs and a theorem of Whitney",Пол Кайнен определяет подгамильтоновы графы как подграфы планарных гамильтоновых графов без ограничения множества вершин в расширенном графе, но пишет, что« в определении подгамильтонова графа можно потребовать, что расширение осуществляется только добавлением ребер» Bekos, Gronemann, Raftopoulou.
For instance in a 2003 technical report"Book embeddings of graphs and a theorem of Whitney",Paul Kainen defines subhamiltonian graphs to be subgraphs of planar Hamiltonian graphs, without restriction on the vertex set of the augmentation, but writes that"in the definition of subhamiltonian graph, one can require that the extension only involve the inclusion of new edges.При изоморфизме подграфу эти« лишние» ребра в G2 могут присутствовать.
In subgraph isomorphism, these"extra" edges in G2 may be present.Для доказательства, что задача поиска изоморфного подграфа NP- полна, ее нужно сформулировать как задачу разрешимости.
To prove subgraph isomorphism is NP-complete, it must be formulated as a decision problem.Максимальный двудольный подграф( задача разрешимости)- задача GT25 в Приложении A1. 2.
Maximum bipartite subgraph(decision version) is the problem GT25 in Appendix A1.2.Тогда G образует подграф графа пересечений поддеревьев.
Thus, G forms a subgraph of the intersection graph of the subtrees.Однако задачи поиска изоморфного подграфа с некоторыми видами подграфов могут быть решены за полиномиальное время.
However certain other cases of subgraph isomorphism may be solved in polynomial time.При этом задача поиска изоморфного подграфа в графе является NP- полной.
The Subgraph Isomorphism problem is NP-complete.Компонентой двусвязности графа называется максимальный по включению двусвязный подграф.
A biconnected component of a graph is a maximum(with respect to inclusion) biconnected subgraph of this graph.Исследование максимального размера плотного подграфа случайного графа Стр.
Analysis of size of the largest dense subgraph of random hypergraph pp.Исследование максимального размера плотного подграфа случайного графа.
Analysis of size of the largest dense subgraph of random hypergraph.Любой максимальный планарный граф, отличный от K4 W4,содержит в качестве подграфа либо W5, либо W6.
Every maximal planar graph, other than K4 W4,contains as a subgraph either W5 or W6.
