Teori graph
merupakan cabang matematika yang penting dan banyak manfaat karena
teori-teorinya dapat diterapkan untuk memecahkan masalah dalam kehidupan
sehari-hari. Dengan menggunakan rumusan atau model teori graph yang tepat suatu
permasalahan dapat dilihat atau diamati lebih jelas, sehingga memudahkan untuk
menganalisanya. Salah satu model yang banyak dipakai dalam melihat permasalahan
adalah model jaringan. Beberapa contoh permasalahan yang dapat diselesaikan
dengan menggunakan model jaringan antara lain sistem jalan raya, sistem pipa
air, dan sistem distribusi.
Jaringan adalah graph berarah yang mempunyai tepat satu titik sumber, tepat satu titik tujuan, dan setiap sisi berarah dari jaringan mempunyai muatan atau kapasitas berupa bilangan bulat positif. Permasalahan jaringan ini dapat diselesaikan dengan menggunakan salah satu model yaitu aliran maksimal.
Untuk mencari aliran maksimal pada suatu jaringan digunakan algoritma aliran maksimal-pemotongan minimal (Maxsimal Flow- Minimal Cut). Tujuan dari algoritma ini adalah untuk menemukan lintasan dari sumber ke tujuan, sehingga aliran dari lintasan tersebut dapat dinaikkan. Secara garis besar langkah-langkah dari algoritma ini adalah sebagai berikut: setiap sisi pada jaringan diberi aliran awal nol, melabeli titik sumber dengan (-,∞), memberi label pada setiap titik sampai titik tujuan dengan beberapa aturan, jika titik t sudah berlabel maka akan ditemukan lintasan dari titik s ke titik t, setelah ditemukan lintasan dari s ke t maka aliran disepanjang lintasan tersebut dapat dinaikkan. Hal ini dilakukan secara berulang-ulang sampai tidak ditemukan lagi lintasan yang akhirnya dapat dinaikkan.
Jaringan adalah graph berarah yang mempunyai tepat satu titik sumber, tepat satu titik tujuan, dan setiap sisi berarah dari jaringan mempunyai muatan atau kapasitas berupa bilangan bulat positif. Permasalahan jaringan ini dapat diselesaikan dengan menggunakan salah satu model yaitu aliran maksimal.
Untuk mencari aliran maksimal pada suatu jaringan digunakan algoritma aliran maksimal-pemotongan minimal (Maxsimal Flow- Minimal Cut). Tujuan dari algoritma ini adalah untuk menemukan lintasan dari sumber ke tujuan, sehingga aliran dari lintasan tersebut dapat dinaikkan. Secara garis besar langkah-langkah dari algoritma ini adalah sebagai berikut: setiap sisi pada jaringan diberi aliran awal nol, melabeli titik sumber dengan (-,∞), memberi label pada setiap titik sampai titik tujuan dengan beberapa aturan, jika titik t sudah berlabel maka akan ditemukan lintasan dari titik s ke titik t, setelah ditemukan lintasan dari s ke t maka aliran disepanjang lintasan tersebut dapat dinaikkan. Hal ini dilakukan secara berulang-ulang sampai tidak ditemukan lagi lintasan yang akhirnya dapat dinaikkan.
Deskripsi
Alternatif :
Teori graph merupakan cabang matematika yang penting dan banyak manfaat karena teori-teorinya dapat diterapkan untuk memecahkan masalah dalam kehidupan sehari-hari. Dengan menggunakan rumusan atau model teori graph yang tepat suatu permasalahan dapat dilihat atau diamati lebih jelas, sehingga memudahkan untuk menganalisanya. Salah satu model yang banyak dipakai dalam melihat permasalahan adalah model jaringan. Beberapa contoh permasalahan yang dapat diselesaikan dengan menggunakan model jaringan antara lain sistem jalan raya, sistem pipa air, dan sistem distribusi.
Jaringan adalah graph berarah yang mempunyai tepat satu titik sumber, tepat satu titik tujuan, dan setiap sisi berarah dari jaringan mempunyai muatan atau kapasitas berupa bilangan bulat positif. Permasalahan jaringan ini dapat diselesaikan dengan menggunakan salah satu model yaitu aliran maksimal.
Untuk mencari aliran maksimal pada suatu jaringan digunakan algoritma aliran maksimal-pemotongan minimal (Maxsimal Flow- Minimal Cut). Tujuan dari algoritma ini adalah untuk menemukan lintasan dari sumber ke tujuan, sehingga aliran dari lintasan tersebut dapat dinaikkan. Secara garis besar langkah-langkah dari algoritma ini adalah sebagai berikut: setiap sisi pada jaringan diberi aliran awal nol, melabeli titik sumber dengan (-,∞), memberi label pada setiap titik sampai titik tujuan dengan beberapa aturan, jika titik t sudah berlabel maka akan ditemukan lintasan dari titik s ke titik t, setelah ditemukan lintasan dari s ke t maka aliran disepanjang lintasan tersebut dapat dinaikkan. Hal ini dilakukan secara berulang-ulang sampai tidak ditemukan lagi lintasan yang akhirnya dapat dinaikkan.
Teori graph merupakan cabang matematika yang penting dan banyak manfaat karena teori-teorinya dapat diterapkan untuk memecahkan masalah dalam kehidupan sehari-hari. Dengan menggunakan rumusan atau model teori graph yang tepat suatu permasalahan dapat dilihat atau diamati lebih jelas, sehingga memudahkan untuk menganalisanya. Salah satu model yang banyak dipakai dalam melihat permasalahan adalah model jaringan. Beberapa contoh permasalahan yang dapat diselesaikan dengan menggunakan model jaringan antara lain sistem jalan raya, sistem pipa air, dan sistem distribusi.
Jaringan adalah graph berarah yang mempunyai tepat satu titik sumber, tepat satu titik tujuan, dan setiap sisi berarah dari jaringan mempunyai muatan atau kapasitas berupa bilangan bulat positif. Permasalahan jaringan ini dapat diselesaikan dengan menggunakan salah satu model yaitu aliran maksimal.
Untuk mencari aliran maksimal pada suatu jaringan digunakan algoritma aliran maksimal-pemotongan minimal (Maxsimal Flow- Minimal Cut). Tujuan dari algoritma ini adalah untuk menemukan lintasan dari sumber ke tujuan, sehingga aliran dari lintasan tersebut dapat dinaikkan. Secara garis besar langkah-langkah dari algoritma ini adalah sebagai berikut: setiap sisi pada jaringan diberi aliran awal nol, melabeli titik sumber dengan (-,∞), memberi label pada setiap titik sampai titik tujuan dengan beberapa aturan, jika titik t sudah berlabel maka akan ditemukan lintasan dari titik s ke titik t, setelah ditemukan lintasan dari s ke t maka aliran disepanjang lintasan tersebut dapat dinaikkan. Hal ini dilakukan secara berulang-ulang sampai tidak ditemukan lagi lintasan yang akhirnya dapat dinaikkan.
Tidak ada komentar:
Posting Komentar