Acyclic orientation (original) (raw)
In graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orientation. Orientations of trees are always acyclic, and give rise to polytrees. Acyclic orientations of complete graphs are called transitive tournaments. The bipolar orientations are a special case of the acyclic orientations in which there is exactly one source and one sink; every transitive tournament is bipolar.
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orientation. The chromatic number of any graph equals one more than the length of the longest path in an acyclic orientation chosen to minimize this path length. Acyclic orientations are also related to colorings through the chromatic polynomial, which counts both acyclic orientations and colorings.The planar dual of an acyclic orientation is a totally cyclic orientation, and vice versa. The family of all acyclic orientations can be given the structure of a partial cube by making two orientations adjacent when they differ in the direction of a single edge. Orientations of trees are always acyclic, and give rise to polytrees. Acyclic orientations of complete graphs are called transitive tournaments. The bipolar orientations are a special case of the acyclic orientations in which there is exactly one source and one sink; every transitive tournament is bipolar. (en) Ациклическая ориентация неориентированного графа — это назначение направлений каждому ребру (ориентация), при которой не образуется какого-либо ориентированного цикла, а потому такая ориентация превращает граф в направленный ациклический граф. Любой граф имеет ациклическую ориентацию. Хроматическое число любого графа равно минимальной длине среди всех ациклических ориентаций. Ациклические ориентации связаны с раскраской посредством хроматического многочлена, который подсчитывает как ациклические ориентации, так и раскраски.Для планарных графов ациклические ориентации являются двойственными графами , и наоборот. Множеству ациклических ориентаций заданного графа может быть придана структура частичного куба, в котором две циклические ориентации смежны, если они отличаются направлением только одного ребра. Ориентации деревьев всегда ацикличны и являются . Ациклические ориентации полных графов называются транзитивными турнирами. Биполярные ориентации являются частными случаями ациклических ориентаций, в которых имеется в точности один источник и один сток. Любой транзитивный турнир является биполярным. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Acyclic_orientations_of_C4.svg?width=300 |
| dbo:wikiPageID | 36619881 (xsd:integer) |
| dbo:wikiPageLength | 8973 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1032162355 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Total_ordering dbr:Totally_cyclic_orientation dbr:Undirected_graph dbc:Graph_theory_objects dbr:Complete_graph dbr:Orientation_(graph_theory) dbr:Chromatic_number dbr:Chromatic_polynomial dbr:Graph_coloring dbr:Comparability_graph dbr:Topological_sorting dbr:Tournament_(graph_theory) dbr:Transitive_closure dbr:Tree_(graph_theory) dbr:Gallai–Hasse–Roy–Vitaver_theorem dbr:Partial_cube dbr:Cycle_graph dbr:Dual_graph dbr:Directed_cycle dbr:Graph_theory dbr:Bipolar_orientation dbr:Directed_acyclic_graph dbr:Planar_graph dbr:Polytree dbr:Tutte_polynomial dbr:Strong_orientation dbr:Transitive_orientation dbr:Planar_dual dbr:Longest_path dbr:File:Acyclic_orientations_of_C4.svg dbr:File:Polytree.svg |
| dbp:wikiPageUsesTemplate | dbt:Math dbt:Mvar dbt:Reflist |
| dcterms:subject | dbc:Graph_theory_objects |
| rdf:type | yago:Object100002684 yago:PhysicalEntity100001930 yago:WikicatGraphTheoryObjects |
| rdfs:comment | In graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orientation. Orientations of trees are always acyclic, and give rise to polytrees. Acyclic orientations of complete graphs are called transitive tournaments. The bipolar orientations are a special case of the acyclic orientations in which there is exactly one source and one sink; every transitive tournament is bipolar. (en) Ациклическая ориентация неориентированного графа — это назначение направлений каждому ребру (ориентация), при которой не образуется какого-либо ориентированного цикла, а потому такая ориентация превращает граф в направленный ациклический граф. Любой граф имеет ациклическую ориентацию. Ориентации деревьев всегда ацикличны и являются . Ациклические ориентации полных графов называются транзитивными турнирами. Биполярные ориентации являются частными случаями ациклических ориентаций, в которых имеется в точности один источник и один сток. Любой транзитивный турнир является биполярным. (ru) |
| rdfs:label | Acyclic orientation (en) Ациклическая ориентация (ru) |
| owl:sameAs | freebase:Acyclic orientation yago-res:Acyclic orientation wikidata:Acyclic orientation dbpedia-ru:Acyclic orientation https://global.dbpedia.org/id/4KhRH |
| prov:wasDerivedFrom | wikipedia-en:Acyclic_orientation?oldid=1032162355&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Acyclic_orientations_of_C4.svg wiki-commons:Special:FilePath/Polytree.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Acyclic_orientation |
| is dbo:wikiPageWikiLink of | dbr:Orientation_(graph_theory) dbr:Chromatic_polynomial dbr:Glossary_of_graph_theory dbr:Graph_coloring dbr:Disjunctive_graph dbr:Gallai–Hasse–Roy–Vitaver_theorem dbr:Dual_graph dbr:Bipolar_orientation dbr:Directed_acyclic_graph dbr:Order_polynomial dbr:Tutte_polynomial dbr:Strong_orientation dbr:Unique_sink_orientation |
| is foaf:primaryTopic of | wikipedia-en:Acyclic_orientation |
