reachability について

.
In an undirected graph, it is sufficient to identify the connected components, as any pair of vertices in such a graph can reach each other if and only if they belong to the same connected component. The connected components of a graph can be identified in linear time. The remainder of this article focuses on reachability in a ''directed'' graph setting.
== Definition ==
For a directed graph

G = (V, E)

, with vertex set

V

and edge set

E

, the reachability relation of

G

is the transitive closure of

E

, which is to say the set of all ordered pairs

(s,t)

of vertices in

V

for which there exists a sequence of vertices

v_0 = s, v_1, v_2, ..., v_k = t

such that the edge

(v_,v_i)

is in

E

for all

1 \leq i \leq k

.〔.〕
If

G

is acyclic, then its reachability relation is a partial order; any partial order may be defined in this way, for instance as the reachability relation of its transitive reduction.〔.〕
A noteworthy consequence of this is that since partial orders are anti-symmetric, if

s

can reach

t

, then we know that

t

''cannot'' reach

s

. Intuitively, if we could travel from

s

t

and back to

s

, then

G

would contain a cycle, contradicting that it is acyclic.
If

G

is directed but ''not'' acyclic (i.e. it contains at least one cycle), then its reachability relation will correspond to a preorder instead of a partial order.
〔.〕

抄文引用元・出典: フリー百科事典『ウィキペディア（Wikipedia）』
■ウィキペディアで「reachability」の詳細全文を読む

スポンサードリンク

翻訳と辞書 : 翻訳のためのインターネットリソース