Constructing a new graph. G'. What does it mean v ∈ S_{i+1}?

Question

John lives in a city whose streets has the same length. His apartment is located at a specified node H. John need to do his errands where he visits each of k different shop in order. However, each store have more than one location in his city. More particularly, for each 1 ≤ i ≤ k there is a set $S_{i}$ of vertices at which a branch of the $i^{th}$ shop is located (you can assume that the $S_{i}$ are disjoint). Construct a new graph G' as following:

Create a new graph G' whose nodes are given by both a node of G, representing John’s current location, and a number 0 ≤ i ≤ k, giving the number of stops that John has successfully made. In particular, the vertices of G' are exactly given by (v, i) with v ∈ Node and i ∈ {0, 1,..., k}. Edges in G' are between (u, i) and (v, i) if (u, v) is an edge of G, or between (u, i) and (v, i + 1) if (u, v) is an edge of G and v ∈ $S_{i+1}$.

What does it really mean by "between (u,i) and (v,i+1) if (u,v) is an edge of G and V v ∈ $S_{i+1}$"?

Let's say we have simple graph G as below:

Here is my attempt of constructing the new graph G'.

How many new nodes do we need to make, 3 or 4 copies? I only make 3 so far since there are only 3 errands. Please let me know if my G' is correct. Thank you.

Answer 1

The vertices of $G'$ are exactly given by $(v, i)$ with $v\in Nodes$ and $i \in \{0, 1,\cdots, k\}$. Edges in $G'$ are between $(u, i)$ and $(v, i)$ if $(u, v)$ is an edge of $G$, or between $(u, i)$ and $(v, i + 1)$ if $(u, v)$ is an edge of $G$ and $v\in S_{i+1}.$

We know $Nodes$ are 6 nodes, i.e., $H, B1, B2, Bus, P, M$ and $k=3$ as there are three kinds of shops, i.e., bank, post office and movie where $S_1$ is the set of banks, $S_2$ post offices and $S_3$ movies.

There are 24 vertices of $G'$ $$\begin{align} (H,0),(B1,0), (B2,0), (Bus,0), (P,0), (M,0), \\ (H,1),(B1,1), (B2,1), (Bus,1), (P,1), (M,1), \\ (H,2),(B1,2), (B2,2), (Bus,2), (P,2), (M,2), \\ (H,3),(B1,3), (B2,3), (Bus,3), (P,3), (M,3). \\ \end{align}$$

The edges are $$\begin{align} &(H,0)(B1,0), (B1,0)(Bus,0), (Bus,0)(P,0), (P,0)(M,0), (H,0)(B2,0) \\ &(H,1)(B1,1), (B1,1)(Bus,1), (Bus,1)(P,1), (P,1)(M,1), (H,1)(B2,1) \\ &(H,2)(B1,2), (B1,2)(Bus,2), (Bus,2)(P,2), (P,2)(M,2), (H,2)(B2,2) \\ &(H,3)(B1,3), (B1,3)(Bus,3), (Bus,3)(P,3), (P,3)(M,3), (H,3)(B2,3) \\ &(H,0)(B1,1), (Bus,0)(B1,1), (H,0)(B2,1) \\ &(Bus,1)(P,2), (M,1)(P,2)\\ &(P,2)(M,3)\\ \end{align}$$

What does it really mean "between $(u, i)$ and $(v, i + 1)$ if $(u, v)$ is an edge of $G$ and $v\in S_{i+1}$" ?

It means exactly what it means.

For $i=0$, $v$ must be one of two nodes in $S_{0+1}=S_1$, i.e., $B1$ and $B2$.

• If $v$ is $B1$, $u$ must be either $H$ or $Bus$ since all edges in $G$ whose endpoints include $B1$ are $HB1$ and $BusB1$. So $(H,0)(B1,1)$ and $(Bus,0)(B1,1)$ are edges in $G'$.
• If $v$ is $B2$, $u$ must be $H$ since the only edge in $G$ whose endpoints include $B2$ is $HB2$. So $(H,0)(B2,1)$ is an edge of $G'$.

It should be clear now what should happen if $i=1$ or $i=2$. Note $i$ cannot be 3 since there is no $S_{3+1}.$

How many new nodes do need to make, 3 or 4 copies ? I only make 3 so far since there are only 3 errands.

Yes, besides the $G$ itself, we should make 3 copies of $G$, one copy of $G$ for each shop John should visit. There should be 4 copies of $G$ with 6 extra (red) edges.