| dbo:abstract
|
- Une orientation forte est, en théorie des graphes, l'attribution d'un sens à chaque arête d'un graphe non orienté (une orientation) qui en fait un graphe fortement connexe. Par exemple, on peut attribuer une orientation forte à un réseau routier s'il est possible de faire de chaque rue un sens unique sans rendre aucune intersection inaccessible. Le théorème de Robbins caractérise les graphes fortement orientables, qui sont exactement les graphes connexes sans pont. Les orientations eulériennes et les orientations bien équilibrées sont des cas particuliers d'orientations fortes. Pour les graphes non connexes, la notion d'orientation forte se généralise par les orientations totalement cycliques. L'ensemble des orientations fortes d'un graphe forme un , dont les orientations adjacentes diffèrent par l'orientation d'une seule arête. Étant donné un graphe, il est possible de lui trouver une orientation forte en temps linéaire. En revanche, compter le nombre d'orientations fortes d'un graphe donné est un problème #P-complet . (fr)
- In graph theory, a strong orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that makes it into a strongly connected graph. Strong orientations have been applied to the design of one-way road networks. According to Robbins' theorem, the graphs with strong orientations are exactly the bridgeless graphs. Eulerian orientations and well-balanced orientations provide important special cases of strong orientations; in turn, strong orientations may be generalized to totally cyclic orientations of disconnected graphs. The set of strong orientations of a graph forms a partial cube, with adjacent orientations in this structure differing in the orientation of a single edge. It is possible to find a single orientation in linear time, but it is #P-complete to count the number of strong orientations of a given graph. (en)
- Сильна орієнтація неорієнтованого графа — це призначення напрямків кожному ребру (орієнтація графа), за якого граф перетворюється на сильно зв'язний граф. Сильні орієнтації можна використати для планування односторонньої мережі доріг. Згідно з теоремою Роббінса, графи з сильними орієнтаціями — це точно графи без мостів. Ейлерова орієнтація і добре збалансована орієнтація є важливими частковими випадками сильних орієнтацій. У свою чергу, сильні орієнтації можна узагальнити до цілком циклічних орієнтацій незв'язних графів. Множина сильних орієнтацій графа утворює частковий куб, у якому суміжні орієнтації відрізняються лише орієнтацією однієї дуги. Окрему сильну орієнтацію можна знайти за лінійний час, але порахувати число сильних орієнтацій даного графа є #P-повною задачею. (uk)
- Сильная ориентация неориентированного графа — это назначение направлений каждому ребру (ориентация графа), при котором граф превращается в сильно связный граф. Сильные ориентации можно использовать для планирования односторонней сети дорог. Согласно теореме Роббинса графы с сильными ориентациями — это в точности графы без мостов. Эйлерова ориентация и хорошо сбалансированная ориентация являются важными частными случаями сильных ориентаций. В свою очередь, сильные ориентации можно обобщить до вполне цикличных ориентаций несвязных графов. Множество сильных ориентаций графа образует частичный куб, в котором смежные ориентации отличаются лишь ориентацией одной дуги. Можно найти отдельную сильную ориентацию за линейное время, но посчитать число сильных ориентаций заданного графа является #P-полной задачей. (ru)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 15579 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:bot
| |
| dbp:date
| |
| dbp:fixAttempted
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Сильна орієнтація неорієнтованого графа — це призначення напрямків кожному ребру (орієнтація графа), за якого граф перетворюється на сильно зв'язний граф. Сильні орієнтації можна використати для планування односторонньої мережі доріг. Згідно з теоремою Роббінса, графи з сильними орієнтаціями — це точно графи без мостів. Ейлерова орієнтація і добре збалансована орієнтація є важливими частковими випадками сильних орієнтацій. У свою чергу, сильні орієнтації можна узагальнити до цілком циклічних орієнтацій незв'язних графів. Множина сильних орієнтацій графа утворює частковий куб, у якому суміжні орієнтації відрізняються лише орієнтацією однієї дуги. Окрему сильну орієнтацію можна знайти за лінійний час, але порахувати число сильних орієнтацій даного графа є #P-повною задачею. (uk)
- Une orientation forte est, en théorie des graphes, l'attribution d'un sens à chaque arête d'un graphe non orienté (une orientation) qui en fait un graphe fortement connexe. Par exemple, on peut attribuer une orientation forte à un réseau routier s'il est possible de faire de chaque rue un sens unique sans rendre aucune intersection inaccessible. (fr)
- In graph theory, a strong orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that makes it into a strongly connected graph. Strong orientations have been applied to the design of one-way road networks. According to Robbins' theorem, the graphs with strong orientations are exactly the bridgeless graphs. Eulerian orientations and well-balanced orientations provide important special cases of strong orientations; in turn, strong orientations may be generalized to totally cyclic orientations of disconnected graphs. The set of strong orientations of a graph forms a partial cube, with adjacent orientations in this structure differing in the orientation of a single edge. It is possible to find a single orientation in linear time, but it is #P-complete (en)
- Сильная ориентация неориентированного графа — это назначение направлений каждому ребру (ориентация графа), при котором граф превращается в сильно связный граф. Сильные ориентации можно использовать для планирования односторонней сети дорог. Согласно теореме Роббинса графы с сильными ориентациями — это в точности графы без мостов. Эйлерова ориентация и хорошо сбалансированная ориентация являются важными частными случаями сильных ориентаций. В свою очередь, сильные ориентации можно обобщить до вполне цикличных ориентаций несвязных графов. Множество сильных ориентаций графа образует частичный куб, в котором смежные ориентации отличаются лишь ориентацией одной дуги. Можно найти отдельную сильную ориентацию за линейное время, но посчитать число сильных ориентаций заданного графа является #P-пол (ru)
|
| rdfs:label
|
- Orientation forte (fr)
- Strong orientation (en)
- Сильная ориентация (теория графов) (ru)
- Сильна орієнтація (теорія графів) (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
