MAKALAH MATEMATIKA DISKRIT

TREE TRAVERSAL, SPANNING TREES, &

MINIMUM SPANNING TREES

DI SUSUN OLEH:

KELOMPOK 7

1. CHUMAIROH (2100720038)

2. MHD. SYARIFUDIN (2100720042)

3. LAILA NOR SIFA’ (2100720056)

4. SREI INDAH ASTUTIK (2100720069)

UNIVERSITAS ISLAM MALANG

FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN

JURUSAN PENDIDIKAN MATEMATIKA

2012

KATA PENGANTAR

Dengan memanjatkan puji syukur kehadirat Tuhan Yang Maha Esa karena atas

rahmat, taufik dan hidayahnyalah serta kerja keras dari kami sehingga makalah “Tree

Traversal, Spanning Trees & Minimum Spanning Trees” dapat kami selesaikan.

Makalah ini kami susun sebagai bahan presentasi mata kuliah Evaluasi Pembelajaran

Matematika. Tidak lupa kami sampaikan banyak terimakasih kepada Ikhsanul Halikin, M.Pd

selaku dosen pembimbing, serta tak lupa kami sampaikan terima kasih kepada teman-teman

yang telah membantu dalam penyelesaian makalah ini.

Tak pernah ada yang sempurna, kecuali Sang Pencipta. Oleh karena itu kami mohon

maaf yang sebesar-besarnya atas segala kesalahan-kesalahan yang ada dalam makalah ini.

Dan tak lupa kami akan selalu menunggu kritik dan sarannya. Semoga makalah ini dapat

bermanfaat bagi siapa saja yang membacanya. Amin.

Malang, Nopember 2012

Penyusun

TREE TRAVERSAL, SPANNING TREES & MINIMUM SPANNING TREES

Pohon Traversal Pendahuluan Pohon berakar yang berurutan sering digunakan untuk menyimpan informasi. Kita perlu beberapa prosedur untuk melewati setiap sudut dari sebuah pohon berakar yang berurutan untuk mengakses data. Kita akan menjelaskan beberapa pentingnya algoritma untuk melewati semua titik dari sebuah pohon berakar yang berurutan. Pohon berakar yang berurutan juga dapat digunakan untuk mewakili berbagai jenis pernyataan, seperti pernyataan aritmatika yang melibatkan angka, variabel, dan operasi. Pendaftaran yang berbeda dari titik pohon berakar yang berurutan digunakan untuk mewakili pernyataan yang berguna dalam menilai pernyataan.

Sistem Alamat Umum Prosedur untuk melintasi semua titik dari sebuah pohon berakar yang berurutan bergantung pada pengurutan/penyusunan anak-anak. Dalam pohon berakar berurutan, anak-anak dari titik internal ditampilkan dari kiri ke kanan dalam gambar yang mewakili grafik-grafik langsung.

Kita akan menjelaskan salah satu cara agar kita benar-benar dapat mengatur titik dari sebuah pohon berakar yang berurutan. Untuk melakukan pengaturan ini, pertama-tama kita harus melabeli semua titik. Kita melakukan ini secara berulang-ulang: 1. Labeli akar dengan bilangan bulat 0 . Kemudian labeli k nya anak-anak (di tingkat 1)

dari kiri ke kanan dengan 1, 2, 3,. . . , k. 2. Untuk setiap titik v pada tingkat n dengan label A, labeli anak kv nya, seolah-olah

mereka ditarik dari kiri ke kanan, dengan A.1, A.2,. . . , A.kv.

Dengan mengikuti prosedur ini, titik v pada level n, untuk n ≥ 1, dilabeli x1. x2…… xn, dimana lintasan yang berbeda dari akar v melintasi titikx1 pertama pada tingkat 1, titik x2 kedua pada tingkat 2, dan seterusnya. Pelabelan ini disebut system alamat umum pada pohon berakar yang berurutan.

Kita dapat mengatur titik puncak secara total dengan menggunakan pengurutan leksikografis dari labelnya dalam sistem alamat umum. X1.X2 berlabel titik. . . . . Xn kurang dari y1.y2 berlabel titik. . . . Ym jika ada i, 0. ≤ i ≤ n, dengan x1 = y1, x2 = y2,. . . , Xi-1 = yi-1, dan xi <yi, atau jika n <m dan xi = yi untuk i = 1, 2,. . . , n. Gambar 1 Sistem Alamat Umum dari Pohon Berakar yang berurutan.

CONTOH 1 Kita menampilkan pelabelan dari sistem alamat umum disebelah titk-titik dalam pohon berakar yang berurutan yang ditunjukkan Gambar 1. Pengaturan leksikografis dari pelabelan adalah

0 <1 <1.1 <1.2 <1.3 <2 <3 <3.1 <3.1.1 <3.1.2 <3.1.2.1 <3.1.2.2 <3.1.2.3 <3.1.2.4 <3.1.3 <3,2 <4 <4,1 <5 <5,1 <5.1.1 <5.2 <5.3

Algoritma Traversal Prosedur sistematis yang terdapat setiap pucak dari pohon berakar berurutan yang disebut algoritma traversal. Kita akan menjelaskan tiga dari algoritma tersebut yang paling sering digunakan, preorder traversal, inorder traversal, dan postorder traversal. Masing-masing algoritma dapat didefinisikan secara berulang-ulang. Kita definisikan preorder traversal terlebih dahulu. DEFINISI 1 Misalkan T adalah pohon berakar yang berurutan dengan akar r. Jika T hanya terdiri dari r, maka r adalah preorder traversal dari T. Jika tidak, anggaplah bahwa T1, T2,. . . , Tn adalah bagian pohon pada r dari kiri ke kanan di T. Preorder traversal dimulai dengan melewati r. Hal ini dilanjutkan dengan melintasi T1 di preorder, maka T2 di preorder, dan seterusnya, sampai Tn dilalui dalam preorder.

Pembaca harus memeriksa bahwa preorder traversal dari pohon berakar yang

berurutan memberikan urutan yang sama dari titik sebagai urutan yang diperoleh dengan menggunakan sistem alamat umum. Gambar 2 mengindikasikan bagaimana sebuah preorder traversal dilengkapi.

Contoh 2 Mengilustrasikan Preorder Traversal. CONTOH 2 Diurutan yang manakah preorder traversal melewati titik dalam T pohon berakar yang berurutan ditunjukkan dalam Gambar 3? Penyelesaian: Langkah-langkah dari preorder traversal T ditunjukkan pada Gambar 4. Kita melintasi T di preorder dengan mendaftar akar a dahulu, diikuti oleh daftar preorder dari bagian pohon dengan akar b, daftaran preorder dari bagian pohon dengan root c (hanya c) dan daftaran preorder dari bagian pohon dengan root d. Gambar 2 Preorder Traversal.

Gambar 5 Inorder Traversal.

Daftar preorder dari bagian pohon dengan akar b dimulai dengan mendaftar b, maka

titik bagian pohon dengan akar e di preorder, dan kemudian bagian pohon dengan akar f di preorder (yang hanya f). Daftar preorder dari bagian pohon dengan akar d dimulai oleh daftar d, diikuti oleh pendaftaran preorder dari subpohn dengan akar g, diikuti oleh bagian pohon dengan root h (yang hanya h), diikuti oleh bagian pohon dengan akar i (yang hanya i).

Pendaftaran preorder dari bagian pohon dengan akar e dimulai dengan mendaftar e, diikuti oleh daftaran preorder dari bagian pohon dengan akar j (yang hanya j), diikuti oleh daftaran preorder dari bagian pohon dengan akar k . Pendaftaran preorder dari bagian pohon dengan akar g adalah g diikuti oleh l, diikuti oleh m.

Pendaftaran preorder dari bagian pohon dengan akar k adalah k, n, o, p. Akibatnya, preorder traversal dari T adalah a, b, e, j, k, n, o, p, f, c, d, g, l, m, h, i.

Kita sekarang akan mendefinisikan inorder traversal.

DEFINISI 2 Misalkan T adalah pohon berakar yang berurutan dengan akar r. Jika T hanya terdiri dari r, maka r adalah traversal inorder T. Jika tidak, anggaplah bahwa T1, T2,. . . , Tn adalah bagian pohon di r dari kiri ke kanan. Traversal inorder dimulai dengan melintasi T1 di inorder, kemudian mengunjungi r. Traversal inorder berlanjut dengan melintasi T2 di inorder, maka T3 di inorder,. . . , Dan akhirnya Tn di inorder.

Gambar 5 menunjukkan bagaimana inorder traversal dilengkapi. Contoh 3 menggambarkan bagaimana inorder traversal dilengkapi untuk pohon tertentu. CONTOH 3 Diurutan manakah apakah traversal inorder mengunjungi titik pohon berakar berurutan T pada Gambar 3? Penyelesaian: Langkah-langkah dari traversal inorder pohon berakar berurutan T ditunjukkan pada Gambar 6. Traversal inorder dimulai dengan traversal inorder bagian pohon dengan akar b, akar a, daftaran inorder bagian pohon akar c, yang hanya c, dan daftaran inorder bagian pohon dengan root d.

Pendaftaran inorder bagian pohon dengan b dimulai dengan pendaftaran inorder bagian pohon dengan e akar, b akar, dan f. Pendaftaran inorder bagian pohon dengan root d dimulai dengan pendaftaran inorder bagian pohon dengancakar g, diikuti akar d, diikuti h, diikuti i.

Pendaftaran inorder bagian pohon dengan akar e ialah j, diikuti oleh akar e, diikuti oleh daftaran inorder bagian pohon dengan akar k. Pendaftaran inorder dari bagian pohon dengan root g adalah l, g, m. Pendaftaran inorder dari bagian pohon dengan k akar adalah n, k, o, p. Akibatnya, daftar inorder dari pohon berakar yang berurutan adalah j, e, n, k, o, p, b, f, a, c, l, g, m, d, h, i.

DEFINISI 3 Misalkan T adalah pohon berakar berurutan dengan akar r. Jika T hanya terdiri dari r, maka r adalah traversal postorder T. Jika tidak, anggaplah bahwa T1, T2,. . . , Tn adalah bagian pohon di r dari kiri ke kanan. Traversal postorder dimulai dengan T1 melintasi di postorder, maka T2 di postorder,. . . , Maka Tn di postorder, dan berakhir dengan mengunjungi r. Gambar 7 menggambarkan bagaimana postorder traversal dilakukan. Contoh 4 mengilustrasikan bagaimana postorder traversal bekerja.

Gambar 7 postorder traversal. CONTOH 4 Diurutan manakah postorder traversal mengunjungi titik dari T pohon berakar berurutan yang ditunjukkan Gambar 3? Penyelesaian: Langkah-langkah traversal postorder dari T pohon berakar berurutan ditunjukkan pada Gambar 8. Traversal postorder dimulai dengan traversal postorder dari bagian pohon dengan akar b, traversal postorder dari bagian pohon dengan akar c, yang hanya c, traversal postorder dari bagian pohon dengan akar d, diikuti oleh akar a.

Traversal postorder dari bagian pohon dengan akar b dimulai dengan traversal postorder dari bagian pohon dengan akar e, diikuti oleh f, diikuti oleh akar b. Traversal postorder pohon berakar dengan akar d dimulai dengan traversal postorder dari bagian pohon dengan akar g, diikuti oleh h, diikuti oleh i, diikuti oleh akar d.

Traversal postorder dari bagian pohon dengan akar e dimulai dengan j, diikuti oleh traversal postorder dari bagian pohon dengan akar k, diikuti oleh akar e. Traversal postorder dari bagian pohon dengan akar g adalah l, m, g. Traversal postorder dari bagian pohon dengan akar k adalah n, o, p, k. Oleh karena itu, traversal postorder T adalah j, n, o, p, k, e, f, b, c, l, m, g, h, i, d, a.

Ada cara mudah untuk mendaftar titik dari pohon berakar berurutan dalam preorder, inorder, dan postorder. Untuk melakukannya, pertama gambarlah kurva disekitar pohon berakar berurutan mulai dari akar, bergerak sepanjang tepi, seperti yang ditunjukkan pada contoh pada Gambar 9. Kita bisa mendaftar titik dalam preorder dengan membuat daftaran setiap sudut dahulu saat kurva ini melintasinya. Kita dapat mendaftar titik di inorder dengan, mendaftar daun saat pertama kalinya kurva melintasi dan mendaftar setiap sudut internal saat kedua kalinya kurva melintasinya. Kita bisa mendaftar titik di postorder dengan mendaftar titik saat terakhir kalinya dilewati dalam perjalanan kembali ke induknya. Ketika hal ini telah dilakukan dalam pohon berakar pada Gambar 9, maka bahwa preorder traversal memberikan a, b, d, h, e, i, j, c, f, g, k, traversal inorder memberikan h, d, b , i, e, j, a, f, c, k, g, dan h traversal postorder memberikan, d, i, j, e, b, f, k, g, c, a. Algoritma yang melintasi pohon berakar berurutan dalam preorder, inorder, postorder paling mudah dinyatakan secara rekursif.

ALGORITMA 1 Preorder Traversal. Prosedur preorder (T: pohon berakar berurutan) r: = akar T Daftaran r untuk setiap anak c pada r dari kiri ke kanan T (c): = bagian pohon dengan c sebagai akarnya Preorder (T(c))

ALGORITMA 2 inorder Traversal. Prosedur inorder (T: pohon berakar beratuuran) r: = akar T jika r adalah daun kemudian daftarlah r lainnya l: = anak pertama r dari kiri ke kanan T (l): = bagian pohon dengan l sebagai akarnya inorder (T (l)) Daftar r untuk setiap c anak r kecuali untuk l dari kiri ke kanan

T (c): = bagian pohon dengan c sebagai akarnya inorder (T (c))

ALGORITMA 3 postorder traversal. Prosedur postorder (T: pohon berakar berurutan) r: = akar T untuk setiap c anak r dari kiri ke kanan T (c): = bagian pohon dengan c sebagai akarnya postorder (T (c)) Daftar r

Perhatikan bahwa kedua preorder traversal dan traversal postorder menyandikan

struktur pohon berakar berurutan ketika jumlah anak dari setiap sudut ditentukan. Artinya, pohon berakar berurutan secara unik ditentukan ketika kita menentukan daftaran titik-titik yang dihasilkan oleh preorder traversal atau oleh traversal postorder pohon, dan dengan jumlah anak-anak dari masing-masing titik (Secara khusus, baik preorder traversal dan traversal postorder menyandikan struktur pohon orderedm-ary penuh. Namun, ketika jumlah anak titik tidak ditentukan, baik preorder atau postorder traversal menyandikan struktur pohon berakar berurutan

Infiks, Prefix, dan Postfix Notasi.

Kita bisa mewakili pernyataan yang rumit, seperti proposisi majemuk, kombinasi set, dan pernyataan aritmatika menggunakan pohon berakar berurutan. Misalnya, mempertimbangkan representasi dari sebuah pernyataan aritmatika yang melibatkan operator + (penambahan), - (pengurangan), * (perkalian), / (pembagian), dan ↑ (exponentiation). Kita akan menggunakan tanda kurung untuk menunjukkan urutan operasi. Pohon berakar berurutan dapat digunakan untuk mewakili pernyataan tersebut, di mana titik internal mewakili operasi, dan daun mewakili variabel atau angka. Setiap operasi beroperasi pada bagian pohon kiri dan kanan (dalam urutan itu).

CONTOH 5 Apakah pohon berakar berurutan yang mewakili pernyataan ((x + y) ↑ 2) + ((x - 4) / 3)? Penyelesaian: Pohon biner untuk pernyataan ini dapat dibangun dari bawah ke atas. Pertama, bagian pohon pernyataan x + y dibangun. Kemudian dimasukkan sebagai bagian dari bagian pohon yang lebih besar mewakili (x + y) ↑ 2. Juga, bagian pohon untuk x - 4 dibangun, dan kemudian ini dimasukkan ke dalam bagian pohon mewakili (x - 4) / 3. Akhirnya bagian pohon terwakili (x + y) ↑ 2 dan (x - 4) / 3 digabungkan untuk membentuk pohon berakar yang ((x + y) ↑ 2) + ((x - 4) / 3). Langkah-langkah ini ditunjukkan pada Gambar 10.

Dalam urutan traversal pohon biner yang mewakili pernyataan menghasilkan pernyataan asli dengan unsur-unsur dan operasi dalam urutan yang sama seperti awal terjadinya, kecuali untuk operasi unary, yang tidak mengikuti cara mereka. Misalnya, dalam traversals urutan pohon biner pada Gambar 11, yang mewakili pernyataan (x + y) / (x + 3), (x + (y / x)) + 3, dan x + (y / (x + 3)), semuanya mengarah pada pernyataan infiks x + y / x + 3. Untuk membuat pernyataan tersebut jelas perlu untuk menyertakan tanda kurung dalam traversal inorder setiap kali kita menghadapi operasi. Pernyataan kurungan penuh yang diperoleh dengan cara ini dikatakan dalam bentuk infix.

Kita memperoleh bentuk awalan dari sebuah pernyataan ketika kita melintasi pohon berakar dalam preorder. Pernyataan yang ditulis dalam bentuk prefix dikatakan dalam notasi Polandia, yang dinamai oleh ahli logika Polandia Jan _Lukasiewicz. Pernyataan dalam notasi prefix (dimana setiap operasi memiliki sejumlah langkah tertentu), adalah jelas, sehingga tidak ada tanda kurung yang diperlukan dalam pernyataan ini. Verifikasi ini dibiarkan sebagai latihan bagi pembaca. CONTOH 6 Apakah bentuk awalan untuk ((x + y) ↑ 2) + ((x - 4) / 3)? Penyelesaian: Kita memperoleh bentuk awalan untuk ungkapan ini dengan melintasi pohon biner yang mewakili preorder, ditunjukkan pada Gambar 10. Hal ini menghasilkan + ↑ + x 2 y / - 3 x 4.

Dalam bentuk awalan dari sebuah pernyataan, operator biner, seperti +, mendahului dua cara. Oleh karena itu, kita dapat mengevaluasi pernyataan dalam bentuk awalan dengan bekerja dari kanan ke kiri. Ketika kita menemukan operator, kita melakukan operasi yang sesuai dengan dua operan segera di sebelah kanan operan ini. Juga, setiap kali operasi dilakukan, kita mempertimbangkan hasil operan baru.

CONTOH 7 Berapakah nilai dari pernyataan prefix + - * 2 3 5 / ↑ 2 3 4? Penyelesaian: Langkah-langkah yang digunakan untuk mengevaluasi ungkapan ini dengan mengerjakan dari kanan ke kiri, dan melakukan operasi dengan menggunakan operan di sebelah kanan, yang ditunjukkan pada Gambar 12. Nilai dari pernyataan ini adalah 3. CONTOH 8 Apa bentuk postfix dari pernyataan ((x + y) ↑ 2) + ((x − 4)/3)? Penyelesaian: Bentuk akhir dari pernyataan tersebut diperoleh dengan melengkapi sebuah postorder traversal dari pohon biner untuk pernyataan ini yang ditunjukkan pada Gambar 10. Hal ini menghasilkan pernyataan akhir: xy + 2 ↑ x 4 − 3 / +.

Pada bentuk akhir dari sebuah pernyataan, seorang pengoprasi biner mengikuti

dua jenis operasinya. Jadi, untuk menilai sebuah pernyataan dari bentuk akhirnya, lakukanlah dari kiri ke kanan dengan melengakapi operasi-operasi setiap kali seorang operator mengikuti dua jenis operasi. Setelah operasi dilengakapi, hasil dari operasi ini menjadi sebuah jenis operasi yang baru. CONTOH 9 Berapa nilai dari pernyataan akhir 7 2 3 ∗ − 4 ↑ 9 3/+? Penyelesaian: langkah-langkah yang digunakan untuk menilai pernyataan ini dengan memulainya dari bagian kiri dan melengkapi operasinya ketika dua jenis operasi diikuti oleh seorang operator ditunjukkkan pada Gambar 13. Nilai dari pernyataan ini adalah 4.

Pohon berakar dapat digunakan untuk mewakili jenis-jenis pernyataan yang lain, seperti yang mewakili teori majemuk dan kombinasi dari bagian-bagiannya. Pada contoh-contoh operator satuan ini, seperti negasi dari sebuah teori, terjadi. Untuk mewakili operator tersebut dan jenis operasinya, sebuah titik mewakili operator dan sebuah anak dari titik ini mewakili jenis operasi yang digunakan. CONTOH 10 Carilah susunan pohon berakar yang mewakili teori majemuk (￢(p ∧ q)) ↔ (￢p

∨￢q). Kemudian gunakan pohon berakar ini untuk mencari awalan, akhiran, dan sisipan dari pernyataan ini. Penyelesaian: pohon berakar untuk teori majemuk ini dibentuk dari bawah ke atas. Pertama, cabang pohon untuk ￢p and ￢q dibentuk (di mana ￢ dianggap sebagai operator satuan). Sebuah cabang pohon untuk p ∧ q juga dibentuk. Kemudian cabang-cabang pohon untuk ￢(p ∧ q) and (￢p) ∨ (￢q) dibentuk. Akhirnya, kedua cabang pohon ini digunakan untuk membentuk puncak pohon berakar. Langkah-langkah dari prosedur ini ditunjukkan pada gambar 4.

Bentuk awalan, akhiran, dan sisipan dari pernyataan ini diperoleh dengan melintasi preorder, postorder, dan inorder pohon berakar ini (termasuk dalam tanda kurung) secara berurutan. Traversal secara berurutan ini menghasilkan ↔￢∧pq

∨￢p￢q,pq ∧￢p￢q￢ ∨↔ dan (￢(p ∧ q)) ↔ ((￢p) ∨ (￢q)).

Karena pernyataan awalan dan akhiran yang jelas dan karena mereka dapat dinilai dengan mudah tanpa peninjauan ulang, mereka digunakan secara luas dalam ilmu pengetahuan komputer. Pernyataan-pernyataan tersebut berguna terutama dalam pembentukan penyusun-penyusun.

Spanning Trees (Pohon Rentang)

DEFINISI 1 Misalkan G adalah grafik sederhana. Sebuah spanning tree (pohon rentang) dari G adalah cabang grafik dari G yang merupakan pohon yang berisi setiap titik dari G.

Sebuah grafik sederhana dengan spanning tree (pohon rentang) harus terhubung, karena adanya lintasan pada spanning tree di antara dua titik. Kebalikannya juga benar, yaitu, setiap grafik sederhana yang terhubung memiliki spanning tree. Kami akan memberikan contoh sebelum membuktikan hasil ini.

CONTOH 1 Carilah pohon rentang dari grafik sederhana G yang ditunjukkan pada Gambar 2. Penyelesaian: Grafik G terhubung, tetapi itu bukan sebuah pohon karena mengandung rangkaian sederhana. Hapus garis {a, e}. Ini menghilangkan salah satu rangkaian sederhana, dan cabang grafik yang dihasilkan masih terhubung dan masih berisi setiap titik dari G. Berikutnya hapuslah garis {e, f} untuk menghilangkan rangkaian sederhana kedua. Akhirnya, menghapus garis {c, g} untuk menghasilkan grafik sederhana tanpa rangkaian sederhana. Cabang grafik ini adalah spanning tree, karena itu merupakan sebuah pohon yang berisi setiap titik dari G. Urutan dari perpindahan garis tersebut digunakan untuk menghasilkan spanning tree yang diilustrasikan dalam Gambar 3.

TEOREMA 1 Sebuah grafik sederhana terhubung jika dan hanya jika memiliki pohon rentang. Bukti: Pertama, anggaplah bahwa grafik sederhana G memiliki spanning tree T. T yang berisi setiap titik dari G. Selain itu, ada lintasan di T di antara dua titik-titiknya. Karena T adalah cabang grafik dari G, ada lintasan di G di antara dua titik tersebut. Oleh karena itu, G terhubung.

Sekarang anggaplah G terhubung. jika G bukan sebuah pohon, harusnya itu mengandung rangkaian sederhana. Hapuslah satu garis dari salah satu rangkaian sederhana ini. Cabang grafik yang dihasilkan memiliki satu garis yang lebih pendek tetapi masih mengandung semua titik dari G dan terhubung. Cabang grafik ini masih terhubung karena ketika kedua titiknya dihubungkan oleh sebuah lintasan yang berisi garis yang telah dihapus, mereka terhubung oleh sebuah lintasan yang tidak mempunyai garis ini. Kita dapat membangun lintasan semacam itu dengan memasukkannya ke lintasan semula, pada titik di mana garis itu dihapus dulu, rangkaian sederhana dengan garis ini dihapus. Jika cabang grafik ini bukan pohon, ia memiliki rangkaian sederhana, maka seperti sebelumnya, hapuslah garis yang berada dalam rangkaian sederhana. Ulangi proses ini sampai tidak ada rangkaian sederhana tersisa. Hal ini mungkin terjadi karena hanya jumlah garis yang terbatas yang ada dalam grafik. Proses ini berakhir ketika tidak ada rangkaian sederhana yang tersisa. Sebuah pohon diproduksi karena grafiknya tetap terhubung sebagai garis-garis yang dihapus. Pohon ini adalah spanning tree karena mengandung setiap titik dari G.

CONTOH 2 Multicasting IP (Pemilihan-pemilihan Internet Protokol)

Spanning tree mempunyai peranan penting dalam pemilihan jaringan Internet Protokol. Untuk mengirim data dari komputer sumber ke beberapa komputer penerima, yang masing-masing merupakan sebuah cabang jaringan, data dapat dikirim secara terpisah untuk setiap komputer. Jenis jaringan, disebut unicasting, tidak efisien, karena banyak salinan dari data yang sama ditransmisikan melalui jaringan. Untuk membuat transmisi data ke beberapa komputer penerima lebih efisien, multicasting IP digunakan. Dengan multicasting IP, sebuah komputer mengirimkan satu salinan data melalui jaringan, dan ketika data mencapai router menengah, data akan diteruskan ke satu atau lebih router lain agar pada akhirnya semua komputer pada cabang jaringan mereka yang berbeda menerima data.

Agar data dapat mencapai komputer penerima secepat mungkin, tidak boleh ada loop (yang dalam terminologi teori grafik adalah sirkuit atau siklus) di lintasan data yang menuju jaringan. Artinya, setelah data telah mencapai router tertentu, data seharusnya tidak pernah kembali ke router. Untuk menghindari loop, router multicast menggunakan algoritma jaringan untuk membangun sebuah pohon rentang dalam grafik yang memiliki sumber multicast, router, dan cabang jaringan yang berisi komputer penerima sebagai titik,

dengan garis yang mewakili hubungan antara komputer dan/atau router. Akar spanning tree ini adalah sumber multicast. Cabang jaringan yang memiliki komputer penerima adalah daun-daun pohon. (Perhatikan bahwa cabang jaringan tidak mempunyai pusat penerima yang tidak termasuk dalam grafik.) hal ini diilustrasikan dalam Gambar 5.

Depth-First Search

Bukti dari Teorema 1 menghasilkan algoritma untuk mendapatkan spanning tree dengan menghapus garis-garis dari rangkaian sederhana. Algoritma ini tidak efisien, karena membutuhkan rangkaian sederhana yang diidentifikasi. Sebagai ganti dari membentuk spanning tree dengan menghapus garis-garis, spanning trees dapat dibangun dengan menambahkan garis secara berurutan . Dua algoritma berdasarkan prinsip ini akan dijelaskan di sini.

Kita bisa membangun sebuah pohon rentang untuk grafik sederhana yang terhubung dengan menggunakan depth-first search. Kita akan membentuk sebuah pohon berakar, dan pohon rentangnya akan berada dibawah grafik dari pohon berakar ini. Secara acak pilihlah sebuah titik dari grafik sebagai akar. Bentuklah sebuah lintasan yang dimulai dari titik ini secara berturut-turut tambahkan titik-titik dan garis-garis, di mana setiap garis baru ini dihasilkan oleh titik terakhir pada lintasan dan sebuah titik yang belum berada di lintasan. Lanjutkan menambahkan titik dan garis ke lintasan ini sepanjang mungkin. Jika lintasan sudah melewati semua titik dari grafik, pohon yang terdiri dari lintasan ini disebut pohon rentang (spanning tree). Namun, jika lintasan tidak melewati semua titik, titik-titik dan garis-garis lebih harus ditambahkan. Kembalilah ke titik terakhir selanjutnya yang berada pada lintasan, dan, jika memungkinkan, bentuklah sebuah lintasan baru yang dimulai dari titik ini melalui titik-titik yang belum dilewati. Jika hal ini tidak dapat dilakukan, kembalilah ketitik yang berada di lintasan, yaitu, dua titik yang berada di belakang lintasan dan coba lagi.

Ulangi prosedur ini, dimulai pada titik terakhir yang dilewati, kembalilah ke lintasan satu titik pada suatu waktu, bentuklah lintasan-lintasan baru sepanjang mungkin sampai tidak ada lagi titik yang dapat ditambahkan. Karena grafik memiliki jumlah garis yang terbatas dan terhubung, maka proses ini akan berakhir dengan adanya spanning tree. Setiap titik yang mengakhiri lintasan pada tahap algoritma akan menjadi daun di pohon berakar, dan masing-masing titik di mana sebuah lintasan dibangun yang dimulai dari titik ini akan menjadi titik internal.

Depth-first search juga disebut backtracking, karena algoritma kembali ke titik yang sebelumnya dilewati untuk menambahkan lintasan. Contoh 3 menggambarkan backtracking.

CONTOH 3 Gunakan depth-first search untuk mencari sebuah spanning tree untuk Grafik G yang ditunjukkan pada Gambar 6. Penyelesaian: Langkah-langkah yang digunakan oleh pencarian depth-first untuk menghasilkan pohon rentang dari G yang ditunjukkan pada Gambar 7. Secara acak kita mulai dengan titik f. Sebuah lintasan yang dibuat dengan menambahkan garis-garis yang terhubung dengan titik-titik yang belum berada pada lintasan secara berturut-turut sepanjang mungkin. Penambahan tersebut menghasilkan lintasan f, g, h, k, j (perhatikan bahwa lintasan-lintasan lain telah dapat dibangun). Selanjutnya, mundurlah ke k. Tidak ada lintasan yang dimulai pada k yang berisi titik-titik yang belum dilewati. Jadi kita kembali ke h. Buatlah lintasan h, i. Kemudian kembali lagi ke h, dan kemudian ke f. Dari f buatlah lintasan f, d, e, c, a. Kemudian mundurlah ke c dan buatlah lintasan c, b. Ini menghasilkan sebuah spanning tree.

Garis yang dipilih dengan pencarian depth-first dari sebuah grafik disebut garis

pohon. Semua garis lain pada grafik harus menghubungkan sebuah titik ke titik sebelum dan sesudahnya. Garis ini disebut garis balik. (Latihan 43 adalah bukti fakta ini.)

CONTOH 4 Dalam Gambar 8 kita menyoroti garis pohon dihasilkan dengan depth-first search dimulai dari titik f dengan menunjukkan kepada mereka dengan garis berwarna yang tebal. Garis-garis balik (e, f) dan (f, h) ditunjukkan dengan garis hitam tipis.

Kita telah menjelaskan bagaimana mendapatkan spanning tree dari grafik yang menggunakan deep-first search. Namun, diskusi kita sejauh ini belum keluar dari sifat rekursif deep-first search. Untuk membantu membuat sifat rekursif dari algoritma yang jelas, kita perlu sedikit istilah. Kami mengatakan bahwa kami mengeksplorasi dari sebuah titik v ketika kita melaksanakan langkah-langkah Depth-first search yang dimulai ketika v ditambahkan kedalam pohon dan berakhir ketika kita telah mundur dan kembali ke v untuk terakhir kalinya. Inti pengamatan yang dibutuhkan untuk memahami sifat rekursif dari algoritma ini adalah bahwa ketika kita menambahkan sebuah garis yang menghubungkan titik v ke titik w, kita selesai menjelajahi dari w sebelum kita kembali ke v untuk melengakapi penjelajahan dari v.

Dalam Algoritma 1 kita membentuk spanning tree dari graf G dengan titik v1,. . . , Vn dengan terlebih dahulu memilih titik v1 sebagai akarnya. Langkah pertama, kita menetapkan T untuk menjadi pohon hanya dengan satu titik ini. Pada setiap langkah kita menambahkan satu titik baru ke pohon T bersama-sama dengan satu garis dari satu titik yang sudah ada pada T ke titik baru ini dan kami menjelajahi dari titik baru ini. Perhatikan bahwa pada penyelesaian algoritma, T tidak mengandung rangkaian sederhana karena ujung tidak ada garis yang pernah ditambahkan yang menghubungkan dua titik dalam pohon. Selain itu, T tetap terhubung seperti yang sudah dibangun. (Kedua pengamatan terakhir dapat dengan mudah dibuktikan melalui induksi matematika.) Karena G terhubung, setiap titik di G dilewati oleh algoritma dan ditambahkan ke pohon (sebagai pembaca harus memverifikasi). Oleh karena itu, T adalah spanning tree dari G.

ALGORITMA 1 Depth-First Search. Prosedur DFS (G: graf terhubung dengan titik v1, v2, ..., vn) T: = pohon hanya terdiri dari titik v1 kunjungi (v1) Prosedur kunjungi (v: titik G) untuk setiap titik w yang berdekatan dengan v dan belum di T

tambahkan titik w dan garis {v, w} ke T kunjungi (w)

Kita sekarang menganalisis kompleksitas komputasi dari algoritma DFS.

Pengamatan utama adalah bahwa untuk setiap titik v, prosedur kunjungan (v) disebut ketika titik v pertama kali ditemukan dan tidak dilewati lagi. Dengan asumsi bahwa daftar kedekatan untuk G tersedia (lihat Bagian 10.3), tidak ada perhitungan yang diperlukan untuk menemukan titik yang berdekatan dengan v. Seperti langkah-langkah yang kita ikuti dari algoritma, kita meneliti setiap garis paling banyak dua kali untuk menentukan apakah menambahkan garis ini dan salah satu titik ujungnya ke pohon. Akibatnya, DFS prosedur menyusun sebuah pohon rentang menggunakan O (e), atau O (n2), langkah-langkah di mana e dan n adalah jumlah dari garis dan titik di G berturut-turut. [Perhatikan bahwa sebuah langkah melibatkan pemeriksaan sebuah titik untuk melihat apakah itu sudah

berada dalam spanning tree karena sedang dibangun dan menambahkan titik ini dan menyesuaikan garis jika titik belum di pohon. Kami juga telah membuat penggunaan ketidaksetaraan e ≤ n (n - 1). / 2, yang berlaku untuk setiap grafik sederhana]

Depth-first pencarian dapat digunakan sebagai dasar untuk algoritma yang memecahkan masalah yang berbeda. Contohnya, DPS dapat digunakan untuk menemukan lintasan-lintasan dan rangkaian dalam grafik, itu dapat digunakan untuk menentukan komponen yang terhubung dari grafik, dan dapat digunakan untuk menemukan titik yang terpotong dari grafik yang terhubung. Seperti yang akan kita lihat, DPS adalah dasar dari teknik backtracking digunakan untuk mencari solusi dari masalah komputasi yang sulit. (Lihat [GrYe05], [Ma89], dan [CoLeRiSt09] untuk pembahasan algoritma berdasarkan DPS.)

Breadth-First Search

Kita juga dapat menghasilkan spanning tree dari grafik sederhana dengan penggunaan Breadth-First Search. Sekali lagi, pohon berakar akan disusun, dan grafik diarahkan mendasari pohon berakar ini akan membentuk spanning tree. Pilihlah akar dari titik pada grafik. Kemudian tambahkan semua garis. Titik-titik baru yang ditambahkan pada tahap ini menjadi titik pada tingkat 1 di spanning tree. Secara acak urutkan mereka. Selanjutnya, untuk setiap titik pada tingkat 1 yang dilewati secara berurutan, tambahkan setiap garis pada titik ini ke pohon selama itu tidak menghasilkan rangkaian sederhana. Secara acak urutkan anak-anak dari tiap titik di tingkat 1. Hal ini menghasilkan titik-titik pada tingkat 2 di pohon tersebut. Ikuti prosedur yang sama sampai semua titik pada pohon telah ditambahkan. Prosedur berakhir karena hanya ada jumlah garis yang terbatas dalam grafik. Sebuah spanning tree dibuat karena kita telah menghasilkan sebuah pohon berisi setiap titik dari grafik. Contoh dari BFS diberikan pada Contoh 5.

CONTOH 5 Penggunaan BFS untuk menyusun pohon rentang untuk grafik yang ditunjukkan pada Gambar 9. Penyelesaian: Langkah-langkah prosedur BFS ditunjukkan pada Gambar 10. Kami memilih titik e menjadi akar. Kemudian kita tambahkan insiden garis dengan semua titik yang berdekatan dengan e, sehingga garis-garis dari e ke b, d, f, dan I ditambahkan. Keempat titik ini berada pada tingkat 1 di pohon. Selanjutnya, tambahkan garis-garis dari titik-titik tersebut di tingkat 1 sampai titik yang berdekatan yang belum berada di pohon. Oleh karena itu, garis-garis dari b ke c dan ditambahkan, seperti garis dari d untuk h, dari f ke j dan g, dan dari i ke k. Titik-titim baru a, c, h, j, g, dan k berada di tingkat 2. Selanjutnya, tambahkan garis dari titik-titik ke titik-titik berdekatan yang belum ada dalam grafik. Ini menambahkan garis dari g ke l dan dari k ke m.

Kita menjelaskan BFS dalam kode pseudo sebagai Algoritma 2. Dalam algoritma

ini, kita asumsikan titik dari graf terhubung G diperintahkan sebagai v1, v2,. . . , Vn. Dalam algoritma kita menggunakan "proses" istilah untuk menggambarkan prosedur penambahan titik baru, dan garis yang sesuai, untuk pohon yang berdekatan dengan titik saat ini sedang diproses selama rangkaian sederhana tidak diproduksi. Algoritma 2 Breadth-First Search

Cara BFS (G: grafik berhubungan dengan titik v1, v2…vn) T:= pohon hanya mencangkup titik v1 L:= daftar kosong Letakkan v1 pada L yang tidak memiliki titik

Sementara L tidak kosong Hapuslah titik pertama, v pada L Diantara w dan v Jika w tidak berada pada L dan T kemudian Tambahkan w di akhir daftar L Tambahkan w dan garis (v, w) pada T

Sekarang kita menguraikan hitungan breadth-First Search yang komplek. Untuk masing-masing garis v pada grafik kita ujii garis yang bersebelahan pada v dan kita tambahkan tiap garis yang belum tersmabung pada pohon T. anggapan bahwa kita memiliki daftar yang bersebelahan pada grafik yang ada, tidak ada penghitungan yang diharuskan untuk menentukkan yang mana titik-titiknya merupakan garis yang besebelahan. Seperti yang terdapat pada analisa breadth-First Search algoritma, kita lihat bahwa kita menguji tiap garis pada hampir dua kali menentukan apakah kita harus menambah garis ini dan titik akhir pukan pada pohon. Hal ini mengikuti bahwa kegunaan tahap algoritma breadth-First Search O(e) atau O(n2).

Breadth-First Search merupakan salah satu algoritma yang paling berguna pada teori grafik. Khususnya, hal ini dapat menyediakan algoritma dasar yang menyelesaikan masalah bermacam-macam. Contohnya, algoritma yang menemukan komponen berhubungan pada sebuah grafik,yang menentukan apakah sebuah grafik yang terdiri dari dua unsur, dan menemukan cara dengan grafik tersedikit diantara dua titik pada grafik dapat dibangun menggunakan Breadth-First Search.

Backtracting Applications

Ada beberapa masalah yang dapat diselesaikan hanya dengan melakukan pencarian kemungkinan penyelesaian yang menyeluruh. Sebuah cara untuk mencari penyelesaian secara sistematis menggunakan pohon penentuan, dimana tiap titik internal mewakili sebuah keputsan dan masing-masing daun sebagai penyelesaian. Untuk menemukan solusi melalui backtracting, pertama buatlah keputusan-keputusan yang berurutan pada sebuah upaya untuk mencapai solusi sepanjang mungkin. Keputusan yang berurutan ini, dapat diwakilkan oleh batang pohon. Sekali lagi, hal ini dikenal bahwa tidak ada penyelesaian yang dapat menghasilkan dari keputusan lebih jauh yang berurutan, mencari dasar titik dan mencocokan solusi dengan keputusan yang lain, jika hal ini memungkinkan. Langkah ini berlanjut sampai solusi ditemukan, atau dinaytakan bahwa tidak ada solusi. Contoh 6 sampa 8 mengilustrasikan kegunaan dari baktracting. CONTOH 6: Grafik Colorings bagaimana bisa backtracting digunakan untuk memutuskan apakah sebuah grafik dapat diwarnai menggunakan warna n? Penyelesaian: kita dapat menyelesaikan masalah ini dengan menggunakan backtracting pada cara-cara berikut. Pertama, pilihlah beberapa titik a dan beri warna 1. Kemudian pilih titik kedua b, dan jika b tidak bersebelahan dengan a, beri warna 1. Selain itu, gunakan warna 2 pada b. kemudian melanjutkan pada ketiga titik c. gunakanlah warna 1, jika memungkinkan, pada c. selain itu, gunakan warna 2, jika memungkinkan. Hanya jika baik warna 1 dan 2 tidak dapat dignakan harus warna 3 yang digunakan. Lanjutkan proses ini selama mungkin untuk memindahkan salah satu warna n pada tiap garis tambahan, selalu menggunakan salah satu warna yang diperbolehkan pertama pada daftar. Jika sebuah titik tercapai yang tidak dapat diwaranai oleh warna-warna n, jika memungkinka, menggunakan warna pertama yang diperbolehkan pada daftar. Jika hal ini tadak memungkinkan untuk merubah pewarnaan ini, backtrack lebih dulu dari pada tugas

sebelumnya, mengulangi lagi, sampai warna pada garis tambahan selama mungkin. Jika sebuah pewarnaan menggunakan warna n, backtracting akan menghasilkannya. Sayangnya, langkah ini tidak terlalu efisian.

Khususnya, mempertimbangkan masalh pewarnaan grafik pada gambar 11 dengan tiga warna. Pohon yang terpapar pada gambar 11 mengilustrasikan bagaimana backtracting dapat digunakan untuk membentuk 3 pewarnaan. Pada langkah ini, merah digunakan pertama kali., kemudian biru, dan terakhir hijau. Contoh sederhana ini dapat dalakukan secara jelas tanpa backtracting, tetapi hal ini termasuk ilustrasi teknik yang baik.

Pada pohon tersebut, bagian awal pada akar, dimana mewakili pewarnaan merah pada a, menyalurpada pewarnaan dengan a merah, b biru, c merah , dan d hijau. Hal ini tidak mungkin mewarnai e menggunakan tiga warna ketika a, b, c, dan d terwarnai. Jadi, backtrack pada induk titik mewakili pewarnaan ini. Karena tidak ada warna lain yang dapat digunakan pada d, backtrack satu lebih bertingkat. Kemudian rubah warna c menjadi hijau. Kita memperoleh pewarnaan pada grafik dengan kemudian mewarnai merah pada d dan hijau pada e.

CONTOH 7

Masalah n-queens. Masalah n-queens menanyakan bagaimana n queen dapat diletakkan pada n x n percaturan sehingga tidak ada dua queen dapat menyerang yang lain. Bagaimana bisa backtracking digunakan untuk menyelesaikan Masalah n-queens? Penyelesaian: untuk menyelesaikan masalah ini kita harus menemukan pogaris n pada n x n pencaturan sehingga tidak ada dua pogaris tersebut berada di baris yang sama, atau pada lintang bujur yang sama diagonal mencangkup semua pogaris (i, j) dengan i + j=m untuk beberapa m, atau i-j=m untuk beberapa (m). kita akan menggunakan backtracking untuk menyelesaikan masalah n-queens. Kita mulai dengan papan catur yang kosong. Pada tahap k + 1 kita upayakan meletakkan queen tambahan pada kolom papan (k+1) pertama, dimana sudah terdapat queen pada kolom k pertama. Kita perhatikan medannya pada kolom (k + l) pertma dimulai dengan deretan pertama papan., mencari pogaris untuk meletakkan queen sehingga tidak ada kesamaan baris atau tidak ada diagonal yang sama seperti peletakkan queen pada papan (kita tahu bahwa tidak pada kolom yang sama). Jika hal ini tidak memungkinkan untuk menemukan pogaris queen pada kolom (k + l) pertama, backtrack pada penempatan queen pada kolom kth, dan letakkan queen pada baris berikutnya yang diperbolehkan pada kolom ini, jika garisnya tersedia. Jika garis tidak tersedia, backtrack lebih jauh.

Khususnya, gambar 12 menunjukkan penyelesaian backtracking pada masalah empat queen. Pada penyelesaian ini, kita letakkan queen pada garis dan kolom pertama. Kemudian kita letakkan queen pada ketiga garis kedua kolom. Tetapi, hal ini tidak memungkinkan untuk meletakkan queen pada kolom ketiga. Jadi kita backtrack dan letakkan queen pada garis keempat pada kolom kedua. Ketika kita melakukan hal ini, kita dapat meletakkan queen pada garis kedua kolom ketiga. Tetapi tidak ada jalan untuk menambahkan queen pada kolom keempat. Hal ini menunjukkan bahwa tidak ada penyelesaian ketika queen diletakkan pada garis dan kolom yang pertama. Kita backtrack pada papan catur yang kosong, dan letakkan queen pada garis kedua pada kolom pertama. Hal ini menghasilkan solusi seperti yang tertera pada gambar 12.

CONTOH 8 Total dari bagian-bagian kecil dalam menanggapi masalah ini. Berikan bagian bilangan bulat positif x1.x2…..xn. temukan bagian bilangan positif yang memiliki M sebagai jumlahnya. Bagaimana bisa backtracking digunakan untuk menyelesaikan masalah ini?

Penyelesaian: kita mulai dengan jumlah yang tidak ditentukan. Kita kembangkan jumlahnya dengan menambahkan syarat secara berurutan. Sebuah bilangan bulat pada urutannya termasuk jika jumlah garisnya kurang dari M ketika bilangan bulat ini ditambahkan pada jumlahnya. Jika jumlah tercapai seperti adanya tambahan syarat lebih besar daripada M, backtrack dengan menurunkan syarat pada jumlah.

Depth-first Search in Derected Graphs Kita juga dapat merubah baik Depth-first Search dan breadth-first search sehingga mereka dapat membuat grafik lurus sebagai input. Tetapi, output tidak perlu menjadi pohon spanning, dibandingkan hutan spanning. Pada kedua algoritma kita dapat menambahkan sebuah titik hanya ketika hal ini merupakan jalan yang lurus dari titik yang akan dipertemukan dan pada titik yang belum ditambahkan. Jika pada salah satu algoritma kita temukan bahwa tidak ada garis yang menghubung pada garis yang ditambahkan pada salah satu yang belum ditambahkan., garis berikutnya ditabahkan dari algoritma menjadi akar baru sebatang pohon pada hutan spanning. Hal ini diilustrasikan pada gambar 9.

CONTOH 9 Apa output dari Depth-first Search yang diberikan grafik G tertera pada gambar 14(a) sebagai input? Penyelesaian: kita mulai depth-first search pada garis a dan tambahkan titik-titik b, c, dan g dan garis sejajar dimana kita dibatasi. Kita backtrack pada c tapi kita masih dibatasi, dan kemudian backtrack pada b, dimana kita menambahkan titik f dan e dan garis sejajar. Bactracking membawa kita kembali pada a. kemudian kita memulai pohon baru pada d dan menambahkan titik h, l, k, dan j, dan garis yang berhubungan. Kita backtracpada k, kemudian l, kemudian h, dan kembali pada d. pada akhirnya, kita mulai pahon baru pada I, melengkapi depth-first search. Output ini tertera pada gambar 14 (b).

Depth-first Search in Derected Graphs merupakan dasar dari banyak algoritma. Hal ini juga dapat digunakan untuk menemukan komponen yang berhubungan kuat pada grafik lurus. Kami simpulkan bagian ini dengan aplikasi dari depth-first search in derected graphs dan breadth-first search pada mesin pencarian pada web

CONTOH 10 Untuk membuat daftar petunjuk pada website, carilah mesin seperti Google dan Yahoo secara sitematis, telusuri web dimulai pada site yang diketahui. Mesin pencari ini menggunakan program yang disebut web spider (atau crawlers atau bot) untuk mengunjungi website dan telitilah isi-isinya. Web spider menggunakan kedua depth-first searching and breadth-first searching untuk membuat indices. Seperti yang tertera pada gambar 5 pada bagian 10.1, halaman web dan link antara mereka dapat bentuk oleh grafik lurus yang disebut grafik web. Halaman web ditunjukkan oleh titik dan linknya oleh garis. Dengan menggunakan depth-first search, halaman pertama dipilih, link mengikuti pada halaman kedua web (jika ada linknya) link pada halaman kedua web dilanjutkan pada halaman ketiga, jika ada linknya, dan seterusnya, sampai halaman dengan link kosong ditemukan. Backtracing kemudian digunakan untuk menguji link pada level sebelumnya untuk link yang baru, dan seterusnya. (karena batasan yangpraktis, web spider memiliki batas-batas dalam yang mereka cari pada depth-first search). Dengan menggunakan depth-first search, halaman web awal dipilih dan linknya dilanjutkan pada halaman kedua web, kemudian link kedua pada halaman awal dilanjutkan (jika ada), dan seterusnya, sampai semuaa link di halaman awal disusul. Kemudian link pada satu halaman dibawah dilanjutkan, halaman demi halaman dan seterusnya.

Minimum Spanning Trees Algoritma untuk minimum spanning tree Bermacam-macam masalah besar dipecahkan dengan penemuan spanning tree pada grafik berat seperti rata-rata berat pada titik-titik pohon minimal. DEFINISI 1 Minimum spanning tree yang berhubungan dengan grafik berat adalah spanning tree yang memiliki kemungkinan rata-rata berat terkecil pada titik-titiknya. Algoritma 1 prim’s algoritma

Cara prim(G:mberat yang berhubungan pada grafik tidak langsung dengan titik n) T:= garis minimal berat Untuk i:= 1 sampai n-2 E:= garis pada minimal berat terjadi pada titik a di T dan tidak membentuk rangkaian sederhana pada T jika ditambahkan pada T T:= T dengan ditambahkan e Kembalikan T (T merupakan minimum spanning tree pada G) Algotime 1 Prim’s Algoritme

Catatan bahwa pilihan pada sebuah garis untuk menambahkan pada sebuah tahap

algoritme tidak ditentukan ketika terdapat lebih dari satu garis dengan berat yang sama yang memenuhi patokan yang sesuai. Kita perlu menyusun garisnya membentuk prima yang jelas. Kita tidak akan merasa khawatir mengenai hal tersebut sebagai bagian akhir. Catatan tambahan bahwa kemungkinan ada lebih dari satu pohon spanning minimal berhubungan dengan grafik berat yang sederhana. (lihat gambar 9) contoh 1 dan 2 mengilustrasikan bagaimana Prim’s algoritme digunakan.

CONTOH 1 Gunakan Prim’s algoritme untuk membentuk minimal harga jaringan komunikasi yang menghubungkan semua komputer yang terpapar pada grafik gambar 1.

Penyelesaian: kita selesaikan masalah tersebut dengan mengetahui minimal spanning tree dalam grafik pada gambar 1. Algoritma prim dikerjakan dengan pengambilan garis pertama dari minimal berat dan penambahan titik-titiknya secara berurutan yang merupakan titik puncak pada pohon dan tidak boleh membentuk rangkaian. Titik-titik warna pada gambar 2 menunjukkan minimum spanning tree yang dikerjakan pada Prim’s algoritma, dengan pilihan yandg dibuat pada setiap langkah yang tertera.

CONTOH 2 Gunakan prim;s algoritma untuk menemukan minimum spanning treepada grafik di gambar 3. Penyelesaian: minimum spanning tree terbentuk menggunakan prim’s algoritma yang tertera pada gambar 4. Pemilihan titik secara berurutan ditunjukkan.

Penambahan titik secara berurutan dengan berat minimal yang tidak boleh

membentuk rangkaian titik-titiknya yang telah ditentukan. Berhentilah setelah n-1 titik-titiknya terpilih.

Bukti bahwa Kruskal algoritma menghasilkan minimum spanning tree pada setiap grafik berat yang berhubungan seperti pada latihan kiri. Pseudocode pada Kruskal algoritma diberikan pada algoritma 2.

Algoritma 2 Kruskal algoritma Cara Kruskal (G: berat yang berhubungan pada grafik tidal langsung dengan titik n) T:= grafik kosong Untuk i:=1 sampai n-1 E:= ada garis pada G dengan berat terkecil yang tidak membentuk rangkaian sederhana ketika menambahkan pada T T:= T dengan menembahkan e Kembalikan T (T merupakan minimum spanning tree pada G) Figure 5: minimum spanning tree dihasilkan dengan kruskal algoritma

Pembaca harus memperhatikan perbedaan antara prim dan kruskal algoritma. Pada prim algoritm garis pada berat minimal yang sampai puncak titik pada pohon, dan tidak berbentuk rangkaian , telah ditentukan: sedangkan pada Krusal algoritma garis-garis pada berat minimal tidak perlu sampai puncak titik pada pohon, dan tidak boleh membentuk sebuah rangkaian, telah ditentukan. Catatan bahwa seperti pada prim algoritma, jika gari-garisnya tidak berurutan, akan ada lebih dari satu pilihan pada satu garis untuk menambahkan pada tahapan langkah. Alhasil, garis-garis tersebut harus diurutkan untuk menjadi cara yang deterministik. Contoh 3 mengilustrasikan bagaimana kruskel algoritma digunakan.

CONTOH 3 Gunakan kruskal algoritma untuk menemukan minimum spanning tree pada grafik berat yang tertera pada gambar 3. Penyelesaian: minimum spanning tree dan pilihan-pilihan garisnya pada setiap tahapan kruskal algoritma tertera pada gambar 5.

Sekarang kita akan buktikan bahwa prim algoritma menghasilkan minimum spanning

tree yang berhubungan pada grafik berat. Bukti: biarkan G menghubungkan grafik berat. Misalnya garis berurutan yang dipilih pada prim algoritma adalah e1, e2..., en-1. Letakkan S menjadi pohon dengan e1, e2..., en-1 sesuai garis-garisnya. Dan letakkan sk menjadi pohon dengan e1, e2..., ek pada garis-garisnya. Letakkan T sebagai minimum spanning tree pada G yang terdiri dari garis-garis e1, e2..., ek, dimana k merupakan bilangan bulat yang tertinggi dengan ciri minimum spanning tree yang keberadaanya mencangkup garis K pertama yang ditentukan pada Prim algoritma. Teori ini berlaku jika kita dapat menunjukkan bahwa S=T.

Misalnya S ≠ T, maka k ‹ n-1. Alhasil, T mencangkup e1, e2..., ek, tetapi bukan ek+1. Anggaplah grafik yang dibuat T bersama dengan ek+1. Karena grafik ini berhubungan dan memiliki garis n, terlalu banyak garis yang membentuk pohon, hal ini harus mencankup rangkaian sederhana. Rangkaian sederhana ini harus meliputi ek+1 karena tidak ada rangkaian sederhana pada T. Disamping itu, hurus terdapat garis pada rangkaian sederhana yang tidak cocok pada sk=1 karena sk+1 merupakan pohon. Dengan memulai pada poin terakhir ek+1 yang juga merupakan poin akhir pada salah satu garis e1…ek, dan mengikuti rangkaian sampai ia mencapai sebuah garis tidak pada sk+1, kita dapat menemukan sebuah garis e tidak pada sk+1 yang memiliki titik akhir yang juga merupakan titik akhir dari salah satu garis-garis e1, e2..., ek.

Dengan pengapusan e dari T dan menambahkan ek+1 , kita memperoleh pohon T’ dengan n-1 garis ( ini merupakan sebatang pohon karena ia tidak memiliki rangkaian sederhana). Catatan bahwa pohon T’ mencangkup e1, e2..., ek, ek+1. Disamping itu, karena ek+1 terpilih dalam prim algoritma pada (k+1) tahap, dan e terdapat pada tahap tersebut, berat ek+1 kurang dari atau sama dengan berat e. dari penelitian tersebut, hal ini manganut

bahwa T’ juga merupakan minimal spanning tree, karena total berat pada garis-garisnya tidak melampaui total berat garis T. hal ini menyanggah pilihan pada K merupakan bilangan bulat yang tertinggi seperti minimal spanning tree yeng meliputi e1…ek. oleh karena itu, k=n-1, dan S=T. hal ini menganut bahwa prim algoritma menghasilkan minimum spanning tree.

Hal ini dapat terlihat bahwa untuk mendapatkan minimum spanning tree pada sebuah grafik dengan garis m dan titik n. krukal algoritma dapat dilakukan dengan menggunakan O operasi (m log n). Alhasil, hal ini lebih sering menggunakan kruskal algoritma pada grafik yang sedikit dan tersebar, dimana m merupakan perbandingan kecil pada C(n,2) = n(n-1)/2, jumlah keseluruhan kemungkinan garis pada sebuah grafik yang tidak langsung dengan titik n. Selain itu, ada sedikit perbedaan yang komplek pada dua grafik algoritma tersebut.