Editing Transitive closure (section)

== In graph theory ==
[[File:Transitive-closure.svg|thumb|right|alt=Transitive closure constructs the output graph from the input graph.|Transitive closure constructs the output graph from the input graph.]]
In [[computer science]], the concept of transitive closure can be thought of as constructing a data structure that makes it possible to answer [[reachability]] questions. That is, can one get from node ''a'' to node ''d'' in one or more hops? A binary relation tells you only that node a is connected to node ''b'', and that node ''b'' is connected to node ''c'', etc. After the transitive closure is constructed, as depicted in the following figure, in an [[Big_O_notation#Orders_of_common_functions|O(1)]] operation one may determine that node ''d'' is reachable from node ''a''. The data structure is typically stored as a Boolean matrix, so if matrix[1][4] = true, then it is the case that node 1 can reach node 4 through one or more hops.

The transitive closure of the adjacency relation of a [[directed acyclic graph]] (DAG) is the reachability relation of the DAG and a [[strict partial order]].

[[File:Equivalentie.svg|thumb|A [[cluster graph]], the transitive closure of an undirected graph]]
The transitive closure of an [[undirected graph]] produces a [[cluster graph]], a [[disjoint union of graphs|disjoint union]] of [[clique (graph theory)|cliques]]. Constructing the transitive closure is an equivalent formulation of the problem of finding the [[component (graph theory)|components]] of the graph.<ref>{{citation
 | last1 = McColl | first1 = W. F.
 | last2 = Noshita | first2 = K.
 | doi = 10.1016/0166-218X(86)90020-X
 | issue = 1
 | journal = [[Discrete Applied Mathematics]]
 | mr = 856101
 | pages = 67–73
 | title = On the number of edges in the transitive closure of a graph
 | volume = 15
 | year = 1986}}</ref>