Rigorous defintions of concepts related to graph coverage.

[Jae-Woo-Jung]

Since I thought that there is ambiguity in definitions in the lecture notes, I rewrote the definitions of concepts more rigorously. But I'm not sure that my paraphrasing is correct. Is there any misunderstanding of concepts? Especially, 0(edge), 11(sidetrip), 12(detour), 15(def-clear), 19(du-tour with sidetrip) are not sure.

And I want to share my paraphrasing.

Given a grpah G, The set of nodes of G, the set of initial nodes of G, the set of final nodes of G, and the set of edges of G are defined. Also, for each node n of G, use(n), def(n) are defined.

0. An edge of G is an element of { (n, m) : n, m are nodes of G and n≠m}.
   (I'm not sure there can be self-loop, n from n. But the lecture note said an edge is from one node to another.)

1. p is a path of G iff p=[n_0, n_1, ..., n_k] where k is a non-negative integer and n_i is a node of G for all i=1, 2, ..., k, and (nj, n{j+1}) is an edge of G for all j=1, 2, ...., k-1.

And we say that 1-1. k is the length of p. 1-2. p starts at n_0. 1-3. p ends at n_k. 1-4. p visits n_i for each i=0, 1, ..., k. 1-5. p is a path from n_0 to n_k. 1-6. p is a path from (n_0, n1) to (n{k-1}, n_k).

3. A path q is a subpath of p iff q is a subsequence of nodes in p.

Here is ambiguity in "subsequence". For example, one may ask whether [1, 2, 5] is a subsequence of [1, 2, 3, 5]. In this context, the answer is no. More rigorously, (q is a subsequence of [n_0, n_1, ..., n_k] iff q=[ni, n{i+1}, ... n_j] for some 0≤i≤j≤k.

4. For a node N of G, Reach(N)={M: M is a node of G and there is a path p of G such that p starts at N and ends at M.}

5. A path p is a test path of G iff p starts at an initial node of G and ends at a final node of G.

6. A path p tours a path q iff q is a subpath of p.

(I don't know why there is a redundant part in definition in the lecutre notd:
In the lecture note: A test path p tours "subpath" q if q is a subpath of p. already mentioned that q is a subpath before 'if' part.)

6-1. For a test t, path(t) is a path of G executed by t. 6-2. For a set T of tests, path(T)={path(t): t∈T}

7. A path p=[n_0, n_1, ..., n_k] is a simple path of G iff ( n1, ..., n{k-1} are all distinct and both n_0 and n_k are not in {n_1, n2, ..., n{k-1} }

8. A path p is a prime path of G iff for any simple path q of G, (if p is a subpath of q, then p=q). (i.e. a prime path is a maximal simple path)

9. A Round-Trip Path is a prime path that starts and ends at the same node.

10. A test path p tours a path q iff q is a subpath of p.

11. A test path p=[n_0, n_1, ..., n_k] tours a path q=[m_0, m_1, ..., ml] with sidetrips iff (there is an injective function g from {0, 1, 2, ..., l-1} into {0, 1, 2, ..., k-1} such that for 0≤i≤j≤l-1, g(i)≤g(j) and [n{g(i)}, n{g(i)+1}]=[m{i}, m_{i+1}])

12. A test path p=[n_0, n_1, ..., n_k] tours a path q=[m_0, m_1, ..., ml] with detours iff (there is an injective function g from {0, 1, 2, ..., l} into {0, 1, 2, ..., k} such that for 0≤i≤j≤l-1, g(i)≤g(j) and n{g(i)}=m_i).

13. For nodes or edges N and M, ( (N, M) is a DU pair iff there is a variable x such that x∈def(N)∩use(M) ). (Note that def(N) and use(M) are given sets by the definition of G)

14. Let p=[n_0, n_1, ..., n_k] be a path of G from N to M, x be a variable. (Here, N, M can be nodes or edges of G.) Then, (p is def-clear with respect to x iff ( (N, M) is a du pair and for every 0<i<k, x isn't in def(n_i) and for every 0<j<k-1, x isn't in def( (nj, n{j+1}) ).

(I'm not sure that (N, M) is a du pair is a necessary condition for that p is def-clear with respect to x.)

15. For nodes or edges N and M of G and a variable x, (the def of x at N reaches the use at M iff there is a def-clear path from N to M with respect to x)

Here, "def of x at N reaches the use at M" implies "(N, M) is a DU pair".

16. Let p be a path of G, x be a variable. Then, (p is a du-path of G with respect to x iff p is simple and def-clear with respect to x).

I don't know why there is a term "subpath" in the lecture note. And the condition "p is def-clear with respect to x" already implies p is from a def v to a use of v.

17. For node n_i, n_j of G and a variable v, du(n_i, n_j, v) = {p: p is a du-path with respect to v and p is from n_i to n_j} du(n_i, v) = {p: p is a du-path with respect to v and p starts at n_i}

18. Let p be a test path of G, q be a path of G, v be a variable. Then, (p du-tours q with respect to v iff (q is a subpath of p and q is def-clear with respect to v) ).

19. Let p=[n_0, n_1, ..., n_k] be a test path of G, q=[m_0, m_1, .., ml] be a path of G, v be a variable. Then, (p du-tours q with respect to v with sidetrips iff (there is an injective function g from {0, 1, 2, ..., l-1} into {0, 1, 2, ..., k-1} such that for 0≤i≤j≤l-1, g(i)≤g(j) and [n{g(i)}, n{g(i)+1}]=[m{i}, m_{i+1}]) and [m0=n{g(0)}, n{g(0)+1}, n{g(0)+2}, ..., n{g(l-1)}, n{g(l-1)+1}] is def-clear with respect to v).

Here, I'm not sure [n{g(i)}, n{g(i)+1}, n{g(i)+2}, ..., n{g(l-1)}, n_{g(l-1)+1}] should be def-clear.

[Jae-Woo-Jung]

Note that according to the above definition of touring with sidetrip, every path p tours p itself with sidetrips.

[swtv-kaist]

Wow, thank you for your effort on the detailed questions, Jaewoo.

A. As you mentioned, my lecture slides are intentionally informal for intuitive understanding. The textbook defines the terms more rigorously.

B.

1. A self edge is allowed (since it is not explicitly prohibited).
2. n_i is a node of G for all i=1, 2, ..., k => n_i is a node of G for all i=0, 1, 2, ..., k (nj, n{j+1}) is an edge of G for all j=1, 2, ...., k-1 => (nj, n{j+1}) is an edge of G for all j=0, 1, 2, ...., k-1 Note that we allow a path of length 0 (i.e., a path containing only a single node)

I will add answers to the remaining items after today's class ;-)

[moonzoo]

3. The textbook uses "subsequence" in a strict meaning. Thus, [1, 2, 5] is NOT a "subsequence" of [1, 2, 3, 5] in this class.
4. Reach(N) is a subgraph reachable from N; Reach(N) contains not only reachable nodes, but also reachable edges from N
5. Yes
6. You are right. I will remove the redundant term "subpath" from the sentence in the lecture slides.
7. Yes, if you change "both n_0 and n_k are not in" => "n_0 or n_k is not in"
8. Yes
9. Yes
10. Yes