Strong orientation (original) (raw)
Сильна орієнтація неорієнтованого графа — це призначення напрямків кожному ребру (орієнтація графа), за якого граф перетворюється на сильно зв'язний граф. Сильні орієнтації можна використати для планування односторонньої мережі доріг. Згідно з теоремою Роббінса, графи з сильними орієнтаціями — це точно графи без мостів. Ейлерова орієнтація і добре збалансована орієнтація є важливими частковими випадками сильних орієнтацій. У свою чергу, сильні орієнтації можна узагальнити до цілком циклічних орієнтацій незв'язних графів. Множина сильних орієнтацій графа утворює частковий куб, у якому суміжні орієнтації відрізняються лише орієнтацією однієї дуги. Окрему сильну орієнтацію можна знайти за лінійний час, але порахувати число сильних орієнтацій даного графа є #P-повною задачею.
| Property | Value |
|---|---|
| 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 | https://books.google.com/books%3Fid=EYAwztXnzf8C&pg=PA7 https://docs.lib.purdue.edu/cgi/viewcontent.cgi%3Farticle=1361&context=cstech https://ir.cwi.nl/pub/10053/10053D.pdf http://www.ams.sunysb.edu/~estie/papers/new-or.pdf |
| dbo:wikiPageID | 16678715 (xsd:integer) |
| dbo:wikiPageLength | 15579 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1116543345 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Menger's_theorem dbr:Euler_tour dbr:Dense_graph dbc:Graph_connectivity dbr:Undirected_graph dbr:Depth-first_search dbr:Information_Processing_Letters dbc:Graph_theory_objects dbr:Orientation_(graph_theory) dbr:NP-complete dbr:Linear_time dbr:Combinatorics,_Probability_and_Computing dbr:Acyclic_orientation dbr:Treewidth dbr:Partial_cube dbr:American_Mathematical_Monthly dbr:Bridge_(graph_theory) dbr:Flip_graph dbr:Graph_theory dbr:Graphs_and_Combinatorics dbr:Journal_of_Combinatorial_Theory dbr:Bipartite_graph dbr:Bipolar_orientation dbr:The_American_Mathematical_Monthly dbr:Directed_acyclic_graph dbr:Planar_graph dbr:Polynomial_time dbr:Tutte_polynomial dbr:Sharp-P-complete dbr:Robbins'_theorem dbr:Fully_polynomial-time_randomized_approximation_scheme dbr:Grid_graph dbr:Planar_dual dbr:Strongly_connected_graph |
| dbp:bot | InternetArchiveBot (en) |
| dbp:date | June 2018 (en) |
| dbp:fixAttempted | no (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Dead_link dbt:Harvtxt dbt:Math dbt:Mvar dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfnp dbt:Harvs |
| dct:subject | dbc:Graph_connectivity dbc:Graph_theory_objects |
| gold:hypernym | dbr:Assignment |
| rdf:type | yago:Object100002684 yago:PhysicalEntity100001930 yago:WikicatGraphTheoryObjects |
| 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 | freebase:Strong orientation yago-res:Strong orientation wikidata:Strong orientation dbpedia-fr:Strong orientation dbpedia-ru:Strong orientation dbpedia-uk:Strong orientation https://global.dbpedia.org/id/4vH1h |
| prov:wasDerivedFrom | wikipedia-en:Strong_orientation?oldid=1116543345&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Strong_orientation |
| is dbo:wikiPageRedirects of | dbr:Totally_cyclic_orientation |
| is dbo:wikiPageWikiLink of | dbr:Totally_cyclic_orientation dbr:Curtis_Greene dbr:Orientation_(graph_theory) dbr:Glossary_of_graph_theory dbr:Sauer–Shelah_lemma dbr:Acyclic_orientation dbr:Gallai–Hasse–Roy–Vitaver_theorem dbr:K-edge-connected_graph dbr:Dual_graph dbr:Eulerian_path dbr:Bridge_(graph_theory) dbr:Bipolar_orientation dbr:Robbins'_theorem |
| is foaf:primaryTopic of | wikipedia-en:Strong_orientation |