CLRS - Maxflow Augmented Flow Lemma 26.1 - tidak mengerti penggunaan def. dalam bukti

Dalam Cormen et. al., Pengantar Algoritma (edisi ke-3), saya tidak mendapatkan garis dalam pembuktian Lemma 26.1 yang menyatakan bahwa aliran augmented adalah aliran dalam dan st(ini hlm. 717-718).$f\uparrow f'$$G$$|f\uparrow f'| =|f|+|f'|$

Kebingungan saya: Ketika memperdebatkan aliran-konservasi, mereka menggunakan definisi pada baris pertama untuk mengatakan bahwa untuk setiap$f\uparrow f'$$u\in V\setminus\{s,t\}$

$$\sum_{v\in V} (f\uparrow f')(u,v) = \sum_{v\in V} (f(u,v)+f'(u,v) - f'(v,u)),$$

di mana jalur yang ditambah didefinisikan sebagai

$$(f\uparrow f')(u,v) = \begin{cases} f(u,v)+f'(u,v) - f'(v,u) & \text{if $(u,v)\in E$}, \\ 0 & \text{otherwise}. \end{cases}$$

Mengapa mereka mengabaikan klausa 'sebaliknya' dalam penjumlahan? Saya tidak berpikir klausa pertama bernilai nol dalam semua kasus seperti itu. Apakah mereka menggunakan aliran-konservasi dan dalam beberapa cara?$f$$f'$

Catatan: Notasi dan definisi yang digunakan di bawah ini dipinjam dari buku edisi ketiga.

Untuk menjawab pertanyaan ini, pertama, amati bahwa jika , maka dengan definisi aliran,$(u,v) \notin E$

$$f(u,v) = f'(u,v) = (f \uparrow f')(u,v) = 0 \, .$$

Selanjutnya, karena , diperoleh bahwa . Ini hanya menyiratkan bahwa ,$f'(v,u) \le c_f(u,v) = f(u,v)$$f'(v,u) = 0$$\forall (u,v) \notin E$

$$(f \uparrow f')(u,v) = f(u,v) + f'(u,v) - f'(v,u) = 0 \, .$$

Oleh karena itu, definisi aliran augmented dapat digeneralisasi untuk semua menjadi sebagai berikut:$(u,v) \in V \times V$

$$(f \uparrow f')(u,v) = f(u,v) + f'(u,v) - f'(v,u) \, .$$

Sisa bukti berikut dari pengamatan ini yang, tentu saja, tidak dijelaskan secara eksplisit dalam teks.

PS Harap dicatat bahwa definisi formal aliran dalam edisi ketiga buku ini sangat berbeda dari yang ada di edisi kedua. Secara khusus, dalam edisi kedua, ada properti aliran bernama miring simetri yang membutuhkan . Properti ini telah dihapus pada edisi ketiga karena asumsi bahwa if dan if$f(u,v) = - f(v,u), \forall u,v \in V$$(v,u) \notin E$$(u,v) \in E$$f(v,u) = 0$$(v,u) \notin E$. Karena itu, definisi konservasi aliran dalam dua edisi juga berbeda. Banyak kebingungan semacam itu, pada kenyataannya, berasal dari perubahan definisi ini yang mungkin dimaksudkan untuk menyederhanakan bukti, tetapi ternyata lebih membingungkan. Saya pribadi lebih suka menempel pada edisi kedua buku untuk bab khusus ini.