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

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.

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.

• The example you gave on edges is not completed, right? following your example on B1, we can say that If v is P, u must be either Bus or M since all edges in G whose endpoints include P are BusP and MP . So (Bus,0)(P,1) and (M,0)(P,1) are edges in G′. – Dmomo Jan 30 at 9:27
• You are almost correct. For $i=1$, we have $(Bus,1)(P,2)$ and $(M,1)(P,2)(P,2)$ instead of $(Bus,0)(P,1)$ and $(M,0)(P,1)$. For $i=2$, we have $(P,2)(M,3)$. – Apass.Jack Jan 30 at 9:31
• we can say that If v is P, u must be either Bus or M since all edges in G whose endpoints include P are BusP and MP . So (Bus,1)(P,0) and (M,1)(P,0) are edges in G′. If v is bus, u must be either B1 or P since all edges in G whose endpoints include P are B1Bus and PBus . So (Bus,0)(B1,1) and (Bus,0)(P,1) are edges in G′. – Dmomo Jan 30 at 9:34
• Please pay attention to the value of $i$. If $v$ is $P$, then $i+1$ must be 2 since $P\in S_2$ only. That is, $i$ must be 1. When we materialize "between $(u,i)$ and $(v,i+1)$ if $(u,v)$ is an edge of $G$ and $v\in S_{i+1}$", the same value of $i$ must be assigned to each appearance of $i$, just as the same value of $u$ must be assigned to each appearance of $u$. – Apass.Jack Jan 30 at 9:40
• Thank you for your help, but I don't think you are wrong this time, You said "For i=0, v must be one of two nodes in S0+1=S1, i.e., B1 and B2." When i =0, v could be H, B1, B2, Bus, P, and M – Dmomo Jan 30 at 9:56