1
$\begingroup$

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: enter image description here

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.enter image description here

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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′. $\endgroup$ – Dmomo Jan 30 at 9:27
  • $\begingroup$ 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)$. $\endgroup$ – Apass.Jack Jan 30 at 9:31
  • $\begingroup$ 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′. $\endgroup$ – Dmomo Jan 30 at 9:34
  • $\begingroup$ 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$. $\endgroup$ – Apass.Jack Jan 30 at 9:40
  • $\begingroup$ 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 $\endgroup$ – Dmomo Jan 30 at 9:56

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.