CO351 Study Guide - Final Guide: Graph Theory

• School: University of Waterloo
• Department: Combinatorics and Optimization
• Course: CO351
• Professor: Pei

Document Summary

In class, we proved the arc version of the menger theorem from graph theory. question, we prove the node version of the theorem. Let d = (n, a) be a digraph, and s, t n be distinct nodes. We would like the new digraph to have at most a polynomial in |n | number of nodes, and the construction not to depend on the st-dipaths in d. Solution: we de ne a digraph d = (n , a ) as follows. The node set n = n {v : v n, v 6 {s, t}}. The source s = s, and the sink t = t. we have arcs a = {u v : uv a, u 6= s} {vv : v n }. All arcs are given a capacity of 1. Any set of k node-disjoint st-dipaths yields a feasible st- ow as in the max- ow instance constructed for the arc version of the menger theorem.