Menentukan Flow maksimum pada jaringan Bipartisi

INDONESIA:

Jaringan merupakan graf berarah terhubung lemah yang mempunyai nilai kapasitas. Flow pada jaringan adalah fungsi yang memetakan setiap busur dalam jaringan ke suatu bilangan real non negatif yang memenuhi:
...(disebut kapasitas batas)
...(disebut nilai flowf )
...(disebut konservasi flow)

Nilai flow maksimum pada suatu jaringan dicari dengan menggunakan algoritma Ford-Fulkerson.

Tujuan penelitian ini adalah membandingkan nilai flow pada jaringan bipartisi yang diperoleh dengan menggunakan algoritma Ford-Fulkerson dengan nilai flow yang diperoleh dengan mencari nilai flow parsial dari jaringan tersebut dengan tujuan membuat teorema baru.

Untuk menerapkan algoritma Ford-Fulkerson untuk mencari nilai flow maksimum pada jaringan bipartisi ditambahkan satu titik sumber yang terhubung ke semua titik sumber yang ada pada jaringan itu, dan satu titik tujuan yang juga terhubung ke semua titik tujuan yang ada pada jaringan tersebut,lalu menjalankan algoritma Ford-Fulkerson. Sedangkan untuk mencari nilai flow dengan membagi jaringan dapat dilakukan dengan membagi jaringan bipartisi menjadi beberapa jaringan berdasarkan banyak titik sumbernya dan mencari nilai flow dari masing-masing bagian. Nilai flow maksimum yang diperoleh dengan menerapkan algoritma Ford-Fulkerson dibandingkan dengan nilai flow maksimum yang diperoleh dengan membagi jaringan tersebut.

Hasil penelitian ini adalah nilai flow maksimum jaringan bipartisi dengan algoritma Ford-Fulkerson sama dengan total nilai flow maksimum parsialnya.

Bagi penelitian selanjutnya diharapkan dapat menemukan bermacam-macam teorema tentang nilai flow pada jaringan bipartisi dengan cara yang lebih mudah.;

ENGLISH:

Network is a weakly connected digraph which has capacity. Flow in a network is a non negative function defined on the edges that satisfies the following conditions:
...(it is called bound capacity)
...(it is called value of flowf )
...(it is called flow conservation)

The maximum flow value of a network is determined using Ford-Fulkerson algorithm.

The purpose of this research is to compare flow value found using Ford-Fulkerson algorithm and flow value found using partial flows to make new theorem of bipartite network flow.

To apply Ford-Fulkerson algorithm for finding maximum flow in bipartite networks, a super-sink and a super-source need to be added to that network. On the other side, to find maximum flow in bipartite networks by splitting the networks become some pieces depend on the number of sources then finding the maximum flow value of each piece. The maximum flow value determined using Ford-Fulkerson algorithm is compared to maximum flow value determined using splitting method.

The result of this research is that maximum flow of bipartite network determined using Ford-Fulkerson algorithm is equal to the total of its partial flows.

For the next research the writer suggests to find some other theorems about finding maximum flow of bipartite network using easier ways.