Each arc of [[??].sub.k,e] is directed from an even vertex to an odd vertex and each arc of [[??].sub.k, o] is directed from an odd vertex to an even vertex (see Figure 4 for k = 5).

In [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the odd vertices and even vertices alternate and an odd vertex is obtained by adding aj to its preceding (even) vertex, along the anti-directed cycle, and an even vertex is obtained from its preceding (odd) vertex by adding (-bj) to it.

Based on the optimal path search, a trace (single stroke) is assessed in the graph until an

odd vertex is reached.

If the number is even, then the vertex is called an even vertex; otherwise it is called an

odd vertex. In figure 2, for example, A is an

odd vertex because three curves go to it.

Furthermore, given a perfect matching [M.sub.e] on [R.sup.N.sub.e] ([beta], [delta]) by orienting each of its edges from its even to its odd vertex one obtains edges oriented in the directions up, down, left or right.

As a start, a new set of red vertices is added to [R.sup.M,N] as follows: in the middle of each horizontal edge of [R.sup.M,N] which has an odd vertex to its right a red vertex is added.