ОРИЕНТИРОВАННЫЙ ГРАФ на Английском - Английский перевод

• directed graph
• oriented graph

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

Пусть G( V, α)- ориентированный граф.
Let G(V, α) be a directed graph.

Например, они позволяют представить ориентированный граф с деревьями на узлах.
For example, they allow representation of a directed graph with trees on the nodes.

Пусть G( V, E)- ориентированный граф и пусть M- абелева группа.
Let G(V, E) be a directed graph and let M be an abelian group.

Ориентация является ациклической, если полученный ориентированный граф не имеет ориентированных циклов.
It is an acyclic orientation if the resulting directed graph has no directed cycles.

Турнир- ориентированный граф, в котором каждая пара вершин соединена одним ребром.
A tournament is a directed graph with one directed edge between each pair of vertices.

Любой неориентированный и ориентированный граф содержит свое ядро и как ретракт, и как порожденный подграф.
Every graph and every directed graph contains its core as a retract and as an induced subgraph.

Это ориентированный граф, не имеющий циклов, в котором каждая вершина имеет степень, не превосходящую трех.
It is an undirected graph with no cycles in which every vertex has degree at most two.

Ориентированная раскраска ориентированного графа является гомоморфизмом в любой ориентированный граф.
An oriented coloring of a directed graph is a homomorphism into any oriented graph.

Тогда Ориентированный граф является двусвязным тогда и только тогда, когда у него есть открытая ушная декомпозиция.
Then A directed graph is biconnected if and only if it has an open ear decomposition.

Пусть G- конечный сильно связанный ориентированный граф, в котором все вершины имеют одинаковую полустепень исхода k.
Let G be a finite, strongly connected, directed graph where all the vertices have the same out-degree k.

Транзитивная ориентация- это ориентация, при которой получаемый ориентированный граф является своим транзитивным замыканием.
A transitive orientation is an orientation such that the resulting directed graph is its own transitive closure.

Ориентация графа G- это назначение направления каждому ребру графа G, что превращает его в ориентированный граф.
An orientation of G is an assignment of a direction to each edge of G, making it into a directed graph.

Под многоугольным графом понимается ориентированный граф, полученный из цикла путем некоторой ориентации его ребер.
Under a polygonal graph is meant an oriented graph obtained from a cycle by some orientation of its edges.

Ориентированный граф является сильно связным, если он содержит ориентированный путь из любой вершины в любую другую вершину.
A directed graph is strongly connected if it contains a directed path from every vertex to every other vertex.

Тогда имеет место следующая теорема: Ориентированный граф является сильно связным тогда и только тогда, когда он имеет ушную декомпозицию.
Then we have the following theorem: A directed graph is strongly connected if and only if it has an ear decomposition.

Ориентированный граф называется направленным, если ни одна из его пар вершин не соединена двумя симметричными( разнонаправленными) ребрами.
A directed graph is called an oriented graph if none of its pairs of vertices is linked by two symmetric edges.

Если отношение интерпретировать как ориентированный граф, то обратное отношение, это тот же самый объект, что и транспонированный граф..
If the relation is interpreted as a directed graph, this is the same thing as the transpose of the graph..

Аналогично, ориентированный граф является двусвязным, если для любых двух вершин существует простой цикл, содержащий обе вершины.
Similarly, a directed graph is biconnected if, for every two vertices, there exists a simple cycle in the graph containing both of them.

Для распределенной системы, в основе которой лежит ориентированный граф без кратных ребер и петель, рассматривается проблема отката( backtracing problem): как передать сообщение от конца дуги в ее начало.
For a distributed system based on a directed graph without multiple edges and loops, the backtracing problem is considered: how to transfer a message from the final vertex of the arc to its initial vertex.

Если ориентированный граф разделен на компоненты сильной связности, циклы существуют только в компонентах, но не между ними, поскольку циклы сильно связаны.
If a directed graph has been divided into strongly connected components, cycles only exist within the components and not between them, since cycles are strongly connected.

Метод Шульце строит полный ориентированный граф, в котором вершины представляют кандидатов, а любые две вершины соединены ребром.
The Schulze method constructs a complete directed graph in which the vertices represent the candidates and every two vertices are connected by an edge.

Ориентированный 1- лес, часто называемый функциональным графом( см ниже), а иногда- максимальным ориентированным псевдолесом,- это ориентированный граф, в котором каждая вершина имеет исходящую степень в точности равную единице.
A directed 1-forest- most commonly called a functional graph(see below), sometimes maximal directed pseudoforest- is a directed graph in which each vertex has outdegree exactly one.

Мультиорграф- это ориентированный граф, в котором разрешены кратные дуги, то есть дуги, имеющие те же начальные и конечные вершины.
A multidigraph is a directed graph which is permitted to have multiple arcs, i.e., arcs with the same source and target nodes.

Существуют гамильтоновы ориентированные графы с n{\ displaystyle n} вершинами и с n( n+ 1)/ 2- 3{\ displaystyle n( n+ 1)/ 2- 3} дугами, не являющиеся панциклическими, но любой гамильтонов ориентированный граф по меньшей мере с n( n+ 1)/ 2- 1{\ displaystyle n( n+ 1)/ 2- 1} дугами панцикличен.
There exist n-vertex Hamiltonian directed graphs with n(n+ 1)/2- 3 edges that are not pancyclic, but every Hamiltonian directed graph with at least n(n+ 1)/2- 1 edges is pancyclic.

Двусвязный ориентированный граф- это такой граф, что для любых двух вершин v и w имеется два ориентированных пути из v в w, не имеющих общих вершин кроме v и w.
A biconnected directed graph is one such that for any two vertices v and w there are two directed paths from v to w which have no vertices in common other than v and w.

То есть тогда и только тогда можно выбрать направление каждого ребра неориентированного графа G, превратив граф в ориентированный граф, в котором существует( ориентированный) путь из любой вершины в любую другу вершину, когда граф G связен и не имеет мостов.
That is, it is possible to choose a direction for each edge of an undirected graph G, turning into a directed graph that has a path from every vertex to every other vertex, if and only if G is connected and has no bridge.

Транспортной сетью называется ориентированный граф[ math] G( V, E)[/ math], каждому ребру[ math] e\ in E[/ math] которого приписана неотрицательная пропускная способность[ math] c( e)\ ge/ math.
A transportation network is a directed graph[math]G(V, E)[/math] in which a nonnegative capacity[math]c(e)\ge 0[/math] is assigned to each edge[math]e\in E/math.

Утверждение можно обобщить от путей к другим ориентированным графам- для любого полидерева P существует двойственный ориентированный граф D, такой, что для любого ориентированного графа G существует гомоморфизм из G в D тогда и только тогда, когда не существует изоморфизма из P в G. Теорема Галлаи- Хассе- Роя- Витавера неоднократно переоткрывалась.
This statement can be generalized from paths to other directed graphs: for every polytree P there is a dual directed graph D such that, for every directed graph G, there is a homomorphism from G to D if and only if there is not a homomorphism from P to G. The Gallai-Hasse-Roy-Vitaver theorem has been repeatedly rediscovered.

Проверку, можно ли ориентированный граф с фиксированным планарным вложением нарисовать как восходящий планарный с совместимым вложением, можно выполнить путем проверки, что вложение является бимодальным, и моделирования задачи совместимого назначения как задачи о потоке в сети.
Testing whether a directed graph with a fixed planar embedding can be drawn upward planar, with an embedding consistent with the given one, can be accomplished by checking that the embedding is bimodal and modeling the consistent assignment problem as a network flow problem.

Можно рассматривать эту задачу как задачу теории графов, если построить функциональный граф( то есть ориентированный граф, в котором каждая вершина имеет единственную исходящую дугу), вершины которого являются элементами множества S, а ребра соответствуют отображению элементов в соответствующие значения функции, как показано на рисунке.
One can view the same problem graph-theoretically, by constructing a functional graph(that is, a directed graph in which each vertex has a single outgoing edge) the vertices of which are the elements of S and the edges of which map an element to the corresponding function value, as shown in the figure.