Penentuan Spanning Tree dengan Menggunakan Algoritma All MST

PENDAHULUAN

Teori graf merupakan topik penelitian dengan kontribusi besar dalam bidang tersebut

komunikasi. Salah satunya adalah menggunakan teori graf untuk mengurangi penggunaan jaringan

internet menjadi lebih efisien [1]. Sebuah konsep yang digunakan untuk mengurangi jaringan dalam teori graf

adalah pohon rata-rata yang lebih kecil (MST). MST adalah parameter bobot terkait beban

semua titik dalam diagram yang tidak memiliki lingkaran kerapatan yang lebih kecil (dari sembarang sisi) [2].

Untuk menentukan MST dari citra berbobot, ada beberapa algoritma yang dapat digunakan, yaitu .

yaitu algoritma Kruskal dan algoritma Prim. Algoritma Kruskal pertama kali dikembangkan oleh

Joseph Kruskal pada tahun 1956. Kemudian disusul oleh Robert C Prim yang menunjukkan

Statistik Prim tahun 1957.

Pada citra berbobot, dimungkinkan untuk memiliki MST yang tidak seragam [3], sedangkan algoritma

Algoritma Kruskal dan Prim hanya menghasilkan satu MST. Jadi, algoritma pada dasarnya

menghasilkan hanya satu MST telah berubah menjadi algoritma yang bisa

Semua MST. Algoritma ini disebut algoritma Semua MST. Semua algoritma MST adalah

perhitungan diadaptasi dari kalkulator Kruskal. Algoritma All MST pertama kali dikembangkan oleh tiga orang

peneliti dari Departemen Ilmu Komputer, Akademi Pertahanan Nasional, Yokosuka, Kanagawa,

Jepang bernama Takeo Yamada, Seiji Kataoka, dan Kohtaro Watanabe pada tahun 2010 [4].

Pada [4] diketahui bahwa algoritma All MST berhasil menentukan semua MST dari suatu objek

grafik berbobot. Oleh karena itu, peneliti mencoba menentukan semua MST dari gambar yang berbeda

tertimbang dalam artikel ini. Tujuan dari artikel ini adalah untuk membuat MST berhasil

setiap submasalah dengan algoritma Kruskal dan rooted tree menggunakan algoritma tersebut

Depth First Search (DFS) dan ambil semua MST dengan algoritma All MST. Artikel ini

mulai dengan mendefinisikan gambar berbobot sederhana. Lalu, lanjutkan dan katakan

menentukan MST citra menggunakan algoritma Kruskal. Selain itu, jika Anda mendapatkan MST, temukan MST lain yang memungkinkan dengan semua algoritme

MST dan membuatnya menjadi rooted tree dengan perhitungan DFS.

MINIMUM SPANNING TREE (MST)

Graf x terdiri dari dua himpunan (x, x), ditulis dengan notasi x = (x, x) dimana x

himpunan simpul yang tidak kosong dan I adalah himpunan sisi (kemungkinan kosong) [5]. Arahkan ke kanan

angka dalam artikel ini diwakili oleh x atau x. Sisi yang menghubungkan dua titik x dan x

dilambangkan dengan x = (x, x). Contoh diagram dapat dilihat pada Gambar 1. Artikel ini berisi

Beberapa kata yang terkait dengan gambar adalah berdekatan, berdekatan, jalur, dan lingkaran. Dua

titik n dan x pada graf dikatakan bertetangga, jika keduanya terhubung langsung

dan tepi (x, x). Selain itu, sisi (x, x) yang masing-masing titiknya x dan x bertetangga.

Diberikan dua buah titik x dan x pada graf x, maka lintasan x − x merupakan rangkaian titik-titik

mulai dari titik x dan berakhir pada titik x tanpa mengulang kata tersebut. Lebih-lebih lagi,

lintasan yang berawal dan berakhir pada titik yang sama disebut sirkuit. Sebelum kita bahas

Untuk MST, pertama-tama kami memberikan definisi pohon, pohon berakar, dan pohon yang diperluas

Versi 1, Versi 2 dan Versi 3.

Definisi 1 [6] Graf tak berarah adalah pohon jika ada dua simpul pada graf yang terhubung

dan lacak tanpa sirkuit.

Pohon tersebut dapat dilihat pada Gambar 2 (a). Banyak pohon dapat membentuk hutan. Hutan itu

sekelompok pohon yang terpisah satu sama lain. Dengan kata lain, hutan adalah kumpulan gambar yang terhubung

tanpa sirkuit [7]. Berdasarkan Gambar 2 (a), diasumsikan sisi (x9, x12) dihilangkan

pada pohon sehingga muncul dua pohon. Sedemikian rupa sehingga disebut

hutan. Hutan yang dihasilkan dapat dilihat pada Gambar 2 (b).

Definisi 2 [6] Sebuah pohon dengan satu titik dianggap sebagai akar dan masing-masing sisi

menjauh dari akar disebut pohon berakar.

Pohon berakar dapat dilihat pada Gambar 3. Selanjutnya berdasarkan Gambar 3 dikenal istilah tersebut

1 adalah akar di dalamnya. Akar pohon yang berakar selalu berada di atas. Inilah masalahnya

terjadi karena setiap titik pada pohon berakar harus dimulai dari akar, yang memungkinkannya melewati pohon

berakar selalu dimulai dari atas ke bawah [3].

Ada beberapa referensi pohon akar yang digunakan dalam artikel ini, yaitu

anak, orang tua, keturunan, kakek, dan saudara [3]. Biarkan x menjadi titik pada pohon

debu berakar di dalamnya. Suatu titik x dikatakan anak dari titik x jika ada sisi yang menghubungkan titik x dan x.

Jadi, x disebut titik induk. Selanjutnya, suatu tempat dikatakan sebagai keturunan dari

n, jika terdapat lintasan dari x ke x dan x adalah akar. Sedemikian rupa sehingga ruang yang ada

kakek dari d. Angka untuk level atau level pada pohon berakar dimulai dari 0 dan merupakan level maksimum

dari pohon berakar disebut kedalaman [3]. Saudara-saudara di pohon berpasir adalah

kesenjangan dengan satu orang tua.

Definisi 3 [2] Sebuah pohon dikatakan sebagai pohon yang diperluas dalam graf I, jika pohon tersebut adalah

subgraf dengan semua simpul pada grafik x.

Berdasarkan diagram pada Gambar 4 (a), diperoleh 4 tulangan yang diperpanjang dengan menghilangkan setiap sisi yang membentuk rangkaian secara bergantian. Apalagi jika grafik x adalah grafik dari

setiap pasang titik memiliki nilai atau bobot, dengan kata lain citra berbobot. Hingga berat pohon

rentang grafik x adalah jumlah bobot semua sisi grafik x. Pohon rentang memiliki

bobot minimum ini disebut extended tree atau MST [3].

Ada beberapa algoritma yang dapat digunakan dalam deteksi MST, tetapi dalam artikel ini

Algoritma yang digunakan adalah Algoritma Kruskal. Dalam pencarian MST, konsep algoritma

Kruskal memulai dengan memilih sisi dari yang paling ringan hingga yang paling berat

[8] . Lebih jelasnya Contoh 4 diberikan.

Contoh 4 Misalkan sebuah graf adalah graf asli seperti yang ditunjukkan pada Gambar 1, dan x adalah MST yang akan

ingin melihat. Maka x adalah jumlah dari semua sisi. Pada dasarnya, gambar yang mencakup segalanya

graf titik e tanpa sisi, sehingga x(x) = {x1, x2, x3, x4, x5} dan x(x) = ∅. Setelah itu, pilih

sisi yang beratnya paling kecil dan tidak membentuk lingkaran, lalu dijumlahkan

θ(e) Pilih komponen x2, x4, dan x7 dengan bobot masing-masing 1, sehingga x(x) =

{x2, x4, x7} seperti yang terlihat pada Gambar 5 (a). Jika semua interval dalam x terhubung dan tidak terhubung

gambarlah lingkaran sehingga n(x) = {x1, x2, x3, n4, n5} dan n(x) = {x2, x1, x4, x7} .

dengan bobot total 5. Gambar 5 (b) adalah MST yang diperoleh dengan menggunakan

Algoritma Kruskal.

CONTOH-CONTOH PENENTUAN SEMUA MST PADA BEBERAPA GRAF

Bagian ini menjelaskan contoh pengidentifikasian semua MST pada banyak

grafik dan Semua algoritma MST. Dua gambar berbobot dengan 12 simpul dan 17 sisi masing-masing diberikan

κ1 berbobot dan graf berbobot x2 seperti terlihat pada Gambar 10 (a) dan Gambar 10 (b).

Untuk tugas yang sama seperti Contoh 11 dalam menentukan semua MST dengan algoritma

Semuanya MST. Ditemukan bahwa bayangan berbobot x1 dan bayangan berbobot 22 dapat dibuat menjadi sebuah pohon

rooted yang dapat dilihat pada Gambar 11 dan Gambar 12.

Berdasarkan hasil semua submasalah dari langkah pemrosesan semua MST dengan algoritma Semua MST

pada citra berbobot x1 dan citra berbobot x2. Semua pohon di semua submasalah (x,x)

rentang x dan (x,x)-dapat diterima, sehingga grafik x1 ditemukan menghasilkan 2 MST

setelah menguji 21 submasalah dengan bobot total 22. Grafik x2 menghasilkan 3 MST

setelah meneliti sekitar 23 subproblem dengan bobot total 22. Berikut adalah 2 MST

dan 3 MST yang dihasilkan dari graf berbobot dan graf berbobot x2 dapat dilihat pada Gambar 13

dan Gambar 14 .

KESIMPULAN

Berdasarkan diskusi tersebut, ditarik kesimpulan sebagai berikut:

1. Semua algoritma MST dapat digunakan untuk menentukan semua MST dalam peta bobot

memiliki MST nonsingular, dalam hal ini variasi statistik Kruskal digunakan untuk

menerima setiap MST.

2. Pohon berakar ditemukan menggunakan algoritma Depth First Search (DFS).

adalah semacam simulasi penerapan algoritma All MST yang menentukan urutannya

masuk ke setiap masalah kecil di pohon berakar.

3. Semua MST pada contoh graf berbobot pada artikel ini adalah sebagai berikut:

sebuah. Dalam grafik berbobot dengan 5 simpul dan 7 tepi, menghasilkan 3 MST setelah beberapa percobaan

11 submasalah dengan bobot total masing-masing 5.

b. Dalam dua gambar berbobot, x1 dan x2 dengan 12 simpul dan 17 sisi:

I. Grafik berbobot be1 menghasilkan MST 2 pada 22 subtes dan.

berat total masing-masing 22.

ii. Grafik berbobot be2 menghasilkan 3 MST pada 23 subtes dan.

berat total masing-masing 22.

DAFTAR PUSTAKA

[1] Triami, N. J. Yundari, dan Fran, F. Minimum Spanning Tree pada Jaringan Fiber Optic di
Universitas Tanjungpura. Buletin Ilmiah Math Stat dan Terapannya (Bimaster). 2020; Vol. 09,
No. 1: 223–230.
[2] Rosen, K. H. Discrete Mathematics and Its Applications. Singapore: Mc Graw Hill; 2012.
[3] Munir, R. Matematika Diskrit Edisi Ketiga. Bandung: Informatika; 2010.
[4] Yamada, T. Kataoka, S, dan Watanabe, K. Listing All the Minimum Spanning Trees in an
Undirected Graph. International Journal of Computer Mathematics. 2010; Vol. 87, No. 14: 3175–
3185.
[5] Chartrand, G. dan Zhang, P. Chromatic Graph Theory. Boca Raton, FL: Chapman dan Hall/CRC
Press Company; 2009.
[6] Gross, J. L. dan Yellen, J. Graph Theory and Its Applications Second Edition. Boca Raton, FL:
Chapman dan Hall/CRC Press Company; 2006.
[7] Wijaya, A. Matematika Diskrit. Bandung: Politeknik Telkom; 2013.
[8] Siang, J. J. Riset Operasi dalam Pendekatan Algoritmis. Yogyakarta: Andi; 2014.
[9] Munir, R. BFS dan DFS. Bandung: Institut Teknologi Bandung; 2005.