# Don't understand this graph definition

I'm studying for my finals in algorithms and reading the part about flow networks. There's a certain section that has me completely stumped and it is as follows:

Given a graph $G= \langle V_G, E_G \rangle$, we can construct the $H(G)=\langle V_H, E_H\rangle$ as follows: $$V_H = V_G\times\{0,1\}$$ $$E_H = \{((v,0),(v,1))|v\in V_G\}\cup\{((x,1),(y,0))|(x,y)\in E_G\}.$$ Say that we have a graph $\langle G,u,v\rangle$ where $G$ is some directed graph, which contains vertices $u$ and $v$ then $H(G)$ can be used to find the smallest number of nodes that must be removed from $G$ to separate $u$ to $v$, meaning there will be no simple path from $u$ to $v$.

I really don't understand what's going on here, partly because I can't visualise $H(G)$. I assume we'd get some bipartite graph and maybe apply Edmonds-Karp only because the flow networks sections is succinct and there's not much else in this chapter. Could someone tell/show me what $H(G)$ is doing exactly and why this result is true. Much appreciated.

EDIT:

I've added some images of the what I got for $H(G)$ for some simple graphs. I understand that the function will transform a graph into a bipartite graph. But, how does this graph tell us the minimum number of vertices that have to be removed so there doesn't exists a simple path from $u$ to $v$ in the original graph? I'm perhaps wondering if it is a maximum matching problem in disguise.

• Have you tried working through some small examples by hand? Pick a small graph $G$, then plug into the definition of $H$ to work out what the graph $H$ is, and then see how to work the problem on those specific graphs. Do a few examples like that and you'll probably get a better idea what's going on.
– D.W.
May 1, 2014 at 17:08
• I'm having a lot of trouble visualizing $H$. Maybe I should draw a pic and attach it to the question, to see if it's right.. May 1, 2014 at 17:11
• That's why I'm suggesting you work through an example. Don't try to visualize it from nothing; that's hard. Instead, write down the vertex set and the edge set of $H$ for a particular example, then try to draw the graph $H$ based on this, and then you have a picture you can look at.
– D.W.
May 1, 2014 at 17:25
• What are they doing with it? Where does the definition come from?
– Raphael
May 2, 2014 at 21:54
• @Raphael the definition came from my lecture notes. I've edited the question with more understanding after D.W.'s comment. But, I'm still a bit confused about something. May 6, 2014 at 1:36

Also, some familiarity with the basics of these constructions helps. In particular, any time you see "Let the vertex set of the new graph be $V\times S\,$" for some set $S$, you should think: "Take a copy of $V$ for every element of $S$, and label each copy with the element it's associated with." So, here, the vertex set of $H$ is two copies of $G$'s vertex set: one labelled $0$ and one labelled $1$. Now, look at the edges. The first set of edges says, "For every vertex $v\in G$, add an edge from copy $0$ to copy $1$." The second set says, "For every edge $(x,y)\in G$, add an edge from copy $1$ of $x$ to copy $0$ of $y$."
As David already pointed out, the construction replaces each vertex $v$ with two vertices $(v,0)$ and $(v,1)$ and an edge from $(v,0)$ to $(v,1)$ (I'll call this edge $e_v$ in the following).
Now, since all incoming edges of $v$ are connected to $(v,0)$ and all outgoing edges are connected to $(v,1)$, the edge $e_v$ will have exactly the flow of the node $v$ in the original graph.
You probably were presented an algorithm that finds a minimal edge cut in the lecture. It should be obvious how this gives a minimal vertex cut for $G$, if only edges $e_v$ are in the cut. If the cut contains edges from the second set, it is less obvious, but we may still translate this into a set of vertices to remove. (We have more than one choice about which vertex to remove for any such edge.) I'll leave it to you to figure out the details.
• when you say "the edge $e_v$ will have exactly the flow of the node $v$ in the original graph," do you mean the flow at that point in the network since nodes themselves do not have flow? May 6, 2014 at 19:03