Removing Anti-Parallel Edges


We can't just subtract 4 from 10 to get 6 because the resulting graph would not model the possiblity that we choose to use only the pipe from v2 to v1.

The solution is to introduce fictional or virtual vertices that break up one of each pair of anti-parallel edges.


Dan Suthers
Last modified: Sat Apr 11 03:16:13 HST 2015
Images are from the instructor's material for Cormen et al. Introduction to Algorithms, Third Edition.