Transitive reduction (original) (raw)
В математике транзитивным сокращением бинарного отношения R на множестве X называется минимальное отношение на X, такое, что транзитивное замыкание совпадает с транзитивным замыканием R. Если транзитивное замыкание R антисимметрично и конечно, то единственно. Однако ни существование, ни единственность в общем случае не гарантированы.
| Property | Value |
|---|---|
| dbo:abstract | In the mathematical field of graph theory, a transitive reduction of a directed graph D is another directed graph with the same vertices and as few edges as possible, such that for all pairs of vertices v, w a (directed) path from v to w in D exists if and only if such a path exists in the reduction. Transitive reductions were introduced by , who provided tight bounds on the computational complexity of constructing them. More technically, the reduction is a directed graph that has the same reachability relation as D. Equivalently, D and its transitive reduction should have the same transitive closure as each other, and the transitive reduction of D should have as few edges as possible among all graphs with that property. The transitive reduction of a finite directed acyclic graph (a directed graph without directed cycles) is unique and is a subgraph of the given graph. However, uniqueness fails for graphs with (directed) cycles, and for infinite graphs not even existence is guaranteed. The closely related concept of a minimum equivalent graph is a subgraph of D that has the same reachability relation and as few edges as possible. The difference is that a transitive reduction does not have to be a subgraph of D. For finite directed acyclic graphs, the minimum equivalent graph is the same as the transitive reduction. However, for graphs that may contain cycles, minimum equivalent graphs are NP-hard to construct, while transitive reductions can be constructed in polynomial time. Transitive reduction can be defined for an abstract binary relation on a set, by interpreting the pairs of the relation as arcs in a directed graph. (en) В математике транзитивным сокращением бинарного отношения R на множестве X называется минимальное отношение на X, такое, что транзитивное замыкание совпадает с транзитивным замыканием R. Если транзитивное замыкание R антисимметрично и конечно, то единственно. Однако ни существование, ни единственность в общем случае не гарантированы. (ru) Транзитивне скорочення бінарного відношення на множині — це найменше відношення на множині , транзитивне замикання якого збігається з транзитивним замиканням . «Найменше відношення» визначається за допомогою відношення включення. Якщо транзитивне замикання є антисиметричним та скінченним, тоді транизитивне скорочення буде єдиним. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Tred-G.svg?width=300 |
| dbo:wikiPageID | 3757117 (xsd:integer) |
| dbo:wikiPageInterLanguageLink | dbpedia-de:Transitive_Hülle_(Relation) |
| dbo:wikiPageLength | 12252 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1116542694 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Binary_relation dbr:Cycle_(graph_theory) dbr:Depth-first_search dbr:Induced_subgraph dbr:Computational_complexity_of_matrix_multiplication dbr:Matrix_multiplication dbr:Glossary_of_graph_theory dbr:NP-hard dbr:SIAM_Journal_on_Computing dbr:Linear_time dbr:Computational_complexity dbr:Ordered_pair dbr:Path_(graph_theory) dbc:Graph_algorithms dbc:Set_theory dbr:Time_complexity dbr:Transitive_closure dbr:Hasse_diagram dbr:Logical_matrix dbr:Adjacency_matrix dbr:Partially_ordered_set dbr:Directed_cycle dbr:Directed_graph dbr:Graph_theory dbr:Journal_of_the_ACM dbr:Strongly_connected_component dbr:Reachability dbr:Covering_relation dbc:Graph_theory dbr:Directed_acyclic_graph dbr:Citation_graph dbr:Polynomial_time dbr:If_and_only_if dbr:Set_(mathematics) dbr:Longest_path_problem dbr:Vertex_(graph_theory) dbr:Mathematical dbr:Transitivity_(mathematics) dbr:Hamiltonian_cycle dbr:Breadth_first_search dbr:Sparse_graph dbr:File:Tred-G.svg dbr:File:Tred-Gprime.svg |
| dbp:id | TransitiveReduction (en) |
| dbp:title | Transitive Reduction (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Mathworld dbt:Mvar dbt:Reflist dbt:Sfnp dbt:Short_description |
| dct:subject | dbc:Graph_algorithms dbc:Set_theory dbc:Graph_theory |
| gold:hypernym | dbr:Graph |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | В математике транзитивным сокращением бинарного отношения R на множестве X называется минимальное отношение на X, такое, что транзитивное замыкание совпадает с транзитивным замыканием R. Если транзитивное замыкание R антисимметрично и конечно, то единственно. Однако ни существование, ни единственность в общем случае не гарантированы. (ru) Транзитивне скорочення бінарного відношення на множині — це найменше відношення на множині , транзитивне замикання якого збігається з транзитивним замиканням . «Найменше відношення» визначається за допомогою відношення включення. Якщо транзитивне замикання є антисиметричним та скінченним, тоді транизитивне скорочення буде єдиним. (uk) In the mathematical field of graph theory, a transitive reduction of a directed graph D is another directed graph with the same vertices and as few edges as possible, such that for all pairs of vertices v, w a (directed) path from v to w in D exists if and only if such a path exists in the reduction. Transitive reductions were introduced by , who provided tight bounds on the computational complexity of constructing them. Transitive reduction can be defined for an abstract binary relation on a set, by interpreting the pairs of the relation as arcs in a directed graph. (en) |
| rdfs:label | Transitive Reduktion (de) Transitive reduction (en) Транзитивное сокращение (ru) Транзитивне скорочення (uk) |
| owl:sameAs | freebase:Transitive reduction yago-res:Transitive reduction wikidata:Transitive reduction dbpedia-de:Transitive reduction dbpedia-ru:Transitive reduction dbpedia-sr:Transitive reduction dbpedia-uk:Transitive reduction https://global.dbpedia.org/id/2rV91 |
| prov:wasDerivedFrom | wikipedia-en:Transitive_reduction?oldid=1116542694&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Tred-G.svg wiki-commons:Special:FilePath/Tred-Gprime.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Transitive_reduction |
| is dbo:wikiPageWikiLink of | dbr:Dedekind–MacNeille_completion dbr:Dependency_graph dbr:Dominance_drawing dbr:Mathematical_diagram dbr:Upward_planar_drawing dbr:Glossary_of_graph_theory dbr:Topological_sorting dbr:Transitive_closure dbr:Transitive_relation dbr:Hasse_diagram dbr:Glossary_of_order_theory dbr:Graph_theory dbr:Reachability dbr:Covering_relation dbr:Temporal_logic dbr:Bipolar_orientation dbr:Coffman–Graham_algorithm dbr:Directed_acyclic_graph dbr:Series-parallel_partial_order dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:St-planar_graph dbr:Multitree |
| is foaf:primaryTopic of | wikipedia-en:Transitive_reduction |
