AlegsaOnline.com

Pohon rentang minimum

Pengarang: Leandro Alegsa

18-06-2022

Sejumlah masalah dari teori graf disebut Pohon Perentang Minimum (Minimum spanning tree). Dalam teori graf, sebuah pohon adalah sebuah cara untuk menghubungkan semua simpul-simpul secara bersama-sama, sehingga terdapat tepat satu jalur dari satu simpul ke simpul-simpul lainnya di pohon tersebut. Jika graf tersebut merepresentasikan sejumlah kota yang dihubungkan oleh jalan, seseorang bisa memilih sejumlah jalan, sehingga setiap kota bisa dicapai dari setiap kota lainnya, tetapi tidak ada lebih dari satu cara untuk bepergian dari satu kota ke kota lainnya.

Sebuah graf bisa memiliki lebih dari satu pohon perentang (spanning tree), seperti halnya mungkin ada lebih dari satu cara untuk memilih jalan di antara kota-kota.

Sering kali, graf berbobot; setiap koneksi antara dua kota memiliki bobot: Mungkin diperlukan biaya untuk melakukan perjalanan di jalan tertentu, atau satu koneksi mungkin lebih panjang dari yang lain, ini berarti diperlukan lebih banyak waktu untuk melakukan perjalanan pada koneksi tersebut. Dalam bahasa teori graf, koneksi-koneksi ini disebut sisi-sisi.

Pohon rentang minimum adalah sebuah pohon. Pohon ini berbeda dari pohon-pohon lainnya karena pohon ini meminimalkan total bobot yang melekat pada sisi-sisi. Tergantung dari bentuk grafnya, mungkin ada lebih dari satu pohon perentang minimum. Dalam sebuah graf dimana semua sisi-sisinya memiliki bobot yang sama, setiap pohon adalah pohon perentang minimum. Jika semua sisi-sisinya memiliki bobot yang berbeda (yaitu: tidak ada dua sisi dengan bobot yang sama), maka terdapat tepat satu pohon perentang minimal.

Pohon perentang minimum dari sebuah graf planar. Setiap sisi diberi label dengan bobotnya, yang di sini secara kasar sebanding dengan panjangnya.

Menemukan pohon rentang minimum

Percobaan pertama

Sangat mudah untuk membuat algoritma yang akan menemukan pohon rentang minimum:

fungsi MST(G,W): T = {} sementara T tidak membentuk pohon perentang: temukan sisi berbobot minimum di E yang aman untuk T T = T union {(u,v)} kembalikan T

Dalam kasus ini, "aman" berarti bahwa memasukkan sisi tersebut tidak membentuk sebuah siklus di graf. Sebuah siklus berarti dimulai dari sebuah simpul, berjalan ke sejumlah simpul-simpul lain dan berakhir di titik awal lagi tanpa menggunakan sisi yang sama dua kali.

Sejarah

Ilmuwan Ceko Otakar Borůvka mengembangkan algoritma pertama yang diketahui untuk menemukan pohon rentang minimum, pada tahun 1926. Dia ingin memecahkan masalah menemukan cakupan Moravia yang efisien dengan listrik. Saat ini, algoritma ini dikenal sebagai algoritma Borůvka. Dua algoritma lain yang umum digunakan saat ini. Salah satunya dikembangkan oleh Vojtěch Jarník pada tahun 1930, dan dipraktikkan oleh Robert Clay Prim pada tahun 1957. Edsger Wybe Dijkstra menemukannya kembali pada tahun 1959, dan menyebutnya algoritma Prim. Algoritma lainnya disebut algoritma Kruskal, dan ditemukan oleh Joseph Kruskal pada tahun 1956. Ketiga algoritma ini bersifat greedy, dan berjalan dalam waktu polinomial.

Algoritma pohon perentang minimum tercepat sampai saat ini dikembangkan oleh Bernard Chazelle. Algoritma ini didasarkan pada soft heap, sebuah perkiraan antrian prioritas. Waktu berjalannya adalah O(m α(m,n)), dimana m adalah jumlah sisi-sisi, n adalah jumlah simpul-simpul dan α adalah invers fungsional klasik dari fungsi Ackermann. Fungsi α tumbuh sangat lambat, sehingga untuk semua tujuan praktis, fungsi ini bisa dianggap sebagai konstanta yang tidak lebih besar dari 4; dengan demikian algoritma Chazelle membutuhkan waktu yang sangat mendekati waktu linear.

Apa algoritma tercepat yang mungkin untuk masalah ini? Itu adalah salah satu pertanyaan terbuka tertua dalam ilmu komputer. Jelas ada batas bawah yang linear, karena kita setidaknya harus memeriksa semua bobot. Jika bobot-bobot sisi adalah bilangan bulat dengan panjang bit yang dibatasi, maka algoritma deterministik diketahui dengan waktu berjalan linear. Untuk bobot-bobot umum, ada algoritma acak yang waktu berjalan yang diharapkan adalah linear.

Masalahnya juga dapat didekati dengan cara terdistribusi. Jika setiap simpul dianggap sebagai komputer dan tidak ada simpul yang mengetahui apa pun kecuali mata rantai yang terhubung dengan simpul itu sendiri, seseorang masih bisa menghitung pohon perentang minimum terdistribusi.

Pertanyaan dan Jawaban

T: Apa yang dimaksud dengan pohon rentang minimum dalam teori graf?

J: Pohon rentang minimum adalah sebuah pohon yang meminimalkan total bobot yang melekat pada sisi-sisi dalam teori graf.

T: Apa yang dimaksud dengan pohon dalam teori graf?

A: Pohon adalah sebuah cara untuk menghubungkan semua simpul secara bersama-sama dalam teori graf, sehingga hanya ada satu jalur dari satu simpul ke simpul lainnya dalam pohon tersebut.

T: Apa tujuan pemilihan jalan dalam skenario teori graf yang merepresentasikan kota?

A: Tujuan pemilihan jalan dalam skenario teori graf yang merepresentasikan kota-kota adalah untuk memungkinkan setiap kota dapat dicapai dari setiap kota lainnya, tetapi dengan tidak lebih dari satu cara yang memungkinkan untuk melakukan perjalanan dari satu kota ke kota lainnya.

T: Dapatkah sebuah graf memiliki lebih dari satu pohon perentang?

J: Ya, sebuah graf dapat memiliki lebih dari satu pohon perentang.

T: Apa perbedaan antara pohon merentang minimum dengan pohon-pohon lain dalam teori graf?

A: Pohon merentang minimum meminimalisir total bobot yang melekat pada sisi-sisinya, sementara pohon-pohon lain tidak memiliki fitur ini.

T: Apa yang dimaksud dengan sisi dalam teori graf?

A: Sisi adalah hubungan antara dua simpul dalam teori graf.

T: Dapatkah ada lebih dari satu pohon rentang minimum dalam sebuah graf dengan sisi-sisi berbobot yang berbeda?

A: Ya, tergantung dari bentuk grafnya, bisa saja ada lebih dari satu pohon rentang minimum.