Discrete Structures207910 marksNumerical: equivalence relation and network flowEquivalence Relations
Show that the relation R = {(a, b): |a-b| is even} is an equivalence relation in the set of integers. Given the following transport network with the edges called with their capacities find all S-D cuts and their capacities and what the minimum capacity?
Show that the relation R = {(a, b): |a-b| is even} is an equivalence relation in the set of integers. Given the following transport network with the edges called with their capacities find all S-D cuts and their capacities and what the minimum capacity?[10]
--- To prove R is an equivalence relation, we verify reflexivity, symmetry, and transitivity. For any integer $a$: $$a - a = 0 = 0$$ Since $0$ is even, $(a, a) \in R$ for all $a \in \mathbb{Z}$. R is reflexive. ✓ Suppose $(a, b) \in R$, so $a - b$ is even. Then: $$b - a = -(a - b) = a - b$$ which...