2
$\begingroup$

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)$

enter image description here

enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. May 1 '14 at 17:08
  • $\begingroup$ 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.. $\endgroup$ – user119264 May 1 '14 at 17:11
  • 2
    $\begingroup$ 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. $\endgroup$ – D.W. May 1 '14 at 17:25
  • 1
    $\begingroup$ What are they doing with it? Where does the definition come from? $\endgroup$ – Raphael May 2 '14 at 21:54
  • $\begingroup$ @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. $\endgroup$ – user119264 May 6 '14 at 1:36
3
$\begingroup$

D.W.'s advice to consider some small examples is excellent. Two great examples to start with are an isolated vertex and a single edge! Once you can how the construction transforms vertices and edges, you know what happens to the building blocks.

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$."

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user119264 May 6 '14 at 19:03
  • $\begingroup$ I call the sum of the flow through all incoming edges (which is the same as the sum through all outgoing edges) the flow of the node. If you call this value "flow at that point", then yes. $\endgroup$ – FrankW May 6 '14 at 19:09

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.