dipath

dipath

[′dī‚path]
(mathematics)
McGraw-Hill Dictionary of Scientific & Technical Terms, 6E, Copyright © 2003 by The McGraw-Hill Companies, Inc.
References in periodicals archive ?
A dipath of [??] is a sequence ([v.sub.1], [v.sub.2],...
Clearly [??] is weak since every two vertices within a same [B.sub.i] can reach each other and the orientation of the edges [e.sub.1], [e.sub.2],..., [e.sub.x] form a dipath in the B-contraction.
* [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a dipath for every j [member of] {[j.sub.1], [j.sub.2],...
Proof: Note that because [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the only path with length at most k joining [u.sub.i] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], either [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] must be a dipath of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].
,[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]}, the only path with length at most k joining [u'.sub.i] and s([v.sub.i,j]) in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is [u'.sub.i]P[v.sub.i,j]Ps([v.sub.i,j]), and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a dipath of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has to be a dipath of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].
Proof: Similarly as for previous Claim 2, if the statement of the claim is not fulfilled by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then there is no dipath with length at most k joining any two of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] including the s([v.sub.i,j])'s.
Indeed, assume that having the dipath [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (resp.
This is done in such a way that there is an orientation of the edges of E ([G.sub.H] ) - E ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) so that every two vertices of [G.sub.H] that do not form a representative pair are joined by a dipath with length at most k.
Besides, there is a dipath with length at most k joining u' and any vertex v' from another gadget [G.sub.v], unless u' = u, v' = v, and {u, v} is a representative pair.
Furthermore, these three dipaths cannot be all directed from or towards the s([v.sub.i,j])'s.
A dipath [P.sub.n] is a digraph (directed graph) with vertex set {[[nu].sub.1],...,[[nu].sub.n]} and arcs ([[nu].sub.i], [[nu].sub.i+1]) for i = 1, ...,n - 1.

Full browser ?