1. **Problem statement:** We want to find the labeling function $f^*$ that minimizes the energy function $$E(f) = \sum_p D_p(f_p) + \lambda \sum_{(p,q) \in E_r} V_{p,q}(f_p, f_q)$$ where $D_p(l_i)$ is the data term (weight from pixel $p$ to terminal $i$) and $V_{p,q}(l_i, l_j)$ is the smoothness term (penalty for labeling difference between neighboring pixels $p$ and $q$). 2. **Graph construction:** The graph $G = (V, E)$ has nodes $V$ representing pixels and edges $E = E_e \cup E_r$ where $E_e$ connects pixels to terminals $s$ and $t$, and $E_r$ connects neighboring pixels. 3. **Cut and capacity:** A cut partitions $V$ into $S$ (pixels connected to $s$) and $T = V - S$. The capacity of the cut is $$\text{capacity} = \sum_{(p,s) \in E_e, p \in S} w_{p,s} + \sum_{(p,q) \in E_r, p \in S, q \in T} w_{p,q}$$ which corresponds to the energy $E(f)$. 4. **Goal:** Find the minimal cut that minimizes $E(f)$, i.e., $$f^* = \arg\min_f E(f)$$ 5. **Solution approach:** Use graph cuts algorithm to compute the minimal cut on $G$. The minimal cut corresponds to the optimal labeling $f^*$. 6. **Summary:** The problem reduces to finding a minimal cut in a graph constructed from pixels and terminals, where edge weights encode data and smoothness terms. The minimal cut partitions pixels into segments minimizing the energy function. **Final answer:** The optimal labeling $f^*$ is obtained by computing the minimal cut on the graph $G$ defined by the given weights and edges, minimizing $$E(f) = \sum_p D_p(f_p) + \lambda \sum_{(p,q) \in E_r} V_{p,q}(f_p, f_q)$$