Subbab 13.1 Notasi dan Terminologi Dasar
Graf berarah yang, untuk setiap pasangan simpul \(x,y\text{,}\) memuat paling banyak salah satu dari dua sisi berarah \((x,y)\) dan \((y,x)\) di antara keduanya disebut graf berorientasi. Penyusunan dasar masalah aliran jaringan dimulai dengan sebuah graf berorientasi \(\bfG\text{,}\) yang disebut jaringan, dengan dua simpul khusus yang disebut sumber dan muara. Kita menggunakan huruf \(S\) untuk menyatakan sumber dan huruf \(T\) untuk menyatakan muara (terminus). Semua sisi yang bersisian dengan sumber diarahkan menjauhi sumber, sedangkan semua sisi yang bersisian dengan muara diarahkan menuju muara. Selain itu, pada setiap sisi terdapat kapasitas tak negatif yang membatasi banyaknya muatan yang dapat disalurkan melalui sisi tersebut. Kapasitas sisi \(e=(x,y)\) dinotasikan dengan \(c(e)\) atau \(c(x,y)\text{.}\) Dalam program komputer, simpul-simpul suatu jaringan dapat diidentifikasi dengan kunci bilangan bulat, tetapi dalam buku ini kita biasanya menggunakan huruf untuk memberi label pada simpul jaringan. Cara ini membantu membedakan simpul dari kapasitas dalam diagram jaringan. Sebuah jaringan diperlihatkan pada Gambar 13.1. Bilangan yang berkaitan dengan sisi-sisinya adalah kapasitas sisi tersebut; misalnya, \(c(E,B)=24\) dan \(c(A,T)=56\text{.}\)
Sebuah jaringan
Aliran \(\phi\) dalam suatu jaringan adalah fungsi yang pada setiap sisi berarah \(e=(x,y)\) menetapkan nilai tak negatif \(\phi(e)=\phi(x,y)\leq c(x,y)\) sehingga hukum kekekalan berikut berlaku:
-
\(\sum_{x} \phi(S,x)= \sum_{x} \phi(x,T)\text{,}\) i.e., jumlah yang meninggalkan sumber sama dengan jumlah yang tiba di muara. Besaran ini disebut nilai aliran \(\phi\text{.}\)
-
Untuk setiap simpul \(y\) yang bukan sumber maupun muara, jumlah yang meninggalkan \(y\) sama dengan jumlah yang memasuki \(y\text{.}\) Artinya, \(\sum_{x}\phi(x,y)= \sum_{x}\phi(y,x)\text{.}\)
Kita memperlihatkan suatu aliran dalam jaringan pada Gambar 13.2.
Aliran jaringan
Pada gambar ini, bilangan yang berkaitan dengan setiap sisi menyatakan kapasitas sisi dan banyaknya aliran yang ditempatkan \(\phi\) pada sisi itu. Sebagai contoh, sisi \((E,D)\) memiliki kapasitas \(20\) dan saat ini membawa aliran sebesar \(8\text{.}\) (Karena \(\phi(x,y)\leq c(x,y)\text{,}\) kita selalu dapat dengan mudah menentukan bilangan mana yang merupakan kapasitas dan mana yang merupakan aliran.) Nilai aliran ini adalah \(30 = \phi(S,F)+\phi(S,B)+\phi(S,E)=\phi(A,T)+\phi(C,T)\text{.}\) Untuk melihat bahwa hukum kekekalan kedua berlaku, misalnya, pada simpul \(B\text{,}\) perhatikan bahwa aliran yang masuk ke \(B\) adalah \(\phi(S,B)+\phi(E,B)+\phi(D,B) = 20\text{,}\) sedangkan aliran yang keluar dari \(B\) adalah \(\phi(B,F)+\phi(B,A)+\phi(B,C)=20\text{.}\)
Untuk suatu jaringan, menemukan sebuah aliran sangatlah mudah. Kita cukup menetapkan \(\phi(e)=0\) untuk setiap sisi \(e\text{.}\) Sebenarnya, arti penting pengamatan ini sangat mudah diremehkan. Masalah aliran jaringan merupakan kasus khusus dari kelas masalah optimisasi yang lebih umum, yang dikenal sebagai program linear; secara umum, menemukan solusi layak bagi masalah pemrograman linear dapat sangat sulit. Bahkan, secara konseptual, menemukan solusi layak—solusi apa pun—sama sulitnya dengan menemukan solusi optimal.
