Spanning-Tree pada Graf Berarah dengan Matriks In-Degree

Tito Nurdiyanto; Ely Susanti

doi:10.25134/jes-mat.v5i1.1650

Spanning-Tree pada Graf Berarah dengan Matriks In-Degree

Tito Nurdiyanto, Ely Susanti

Abstract

ABSTRACT

Graph has a concept of tree. Tree is a connected graph which is not consist cycle. Concept of tree is an important concept because it can be used to support application of graph in any variation of science. Besides, spanning-tree is a tree in graph with every point on graph. Every graph can be formed at least there is one spanning tree. The problem of this article is how to determine the sum of spanning-tree in directed graph with matrix in-degree yang menggunakan teorema: the value of the cofactor of is equal to the number of arborescence in rooted at the vertex . Arborescence in is spanning arborescence.

Keywords : spanning-tree, directed graph, matrix in-degree

ABSTRAK

Graf memiliki konsep tree (pohon). Tree merupakan graf terhubung yang tidak memuat siklus. Konsep tree merupakan konsep yang penting karena konsep ini dapat digunakan untuk mendukung penerapan graf dalam berbagai bidang ilmu. Sedangkan spanning-tree adalah sebuah pohon pada graf yang memuat semua titik di . Dari setiap graf dapat dibentuk paling sedikit sebuah spanning-tree. Permasalahan dalam artikel ini adalah bagaimana menentukan jumlah spanning-tree pada graf berarah dengan matriks in-degree yang menggunakan teorema: nilai kofaktor dari adalah sama dengan banyaknya arborescence pada dengan titik sebagai root. Arborescence pada juga merupakan spanning arborescence.

Kata kunci: spanning-tree, graf berarah, matriks in-degree

Keywords

spanning-tree, directed graph, matrix in-degree

Full Text:

PDF

References

DAFTAR PUSTAKA

Amrullah. (2011). Aplikasi Graf Pohon pada Algoritma Huffman. I. Pijar MIPA, VI (1), 24-28.

Anggraeni, W. (2015). Aplikasi Algoritma Sollin dalam Pencarian Pohon Perentang Minimum Provinsi Jawa Tengah. Faktor Exacta, 8(4), 381-391.

Anton, H. (2004). Aljabar Liniear Elementer. Jakarta: Erlangga.

Arifanti, D. R. (2017). Visualisasi Efek Perubahan Fungsi Lahan Menggunakan Maksimum Spanning Tree dengan Pembobot Kolerasi. Al-Khwarizmi: Jurnal Pendidikan Matematika dan Ilmu Pengetahuan Alam, 5(2), 155-164.

Aziza, F., Suyitno, A., & Mulyono. (2014). Teorema Phon Matriks untuk Menentukan Banyaknya Pohon Rentang Graf Wheels W dan Kipas F. UNNES Journal of Mathematics, 3(2), 104-109

Daswa & Riyadi, M. (2017). Aplikasi Pewarnaan graf pada Masalah Penyusunan Jadwal Perkuliahan di Universitas Kuningan. JES-MAT, 3(2), 217-226.

Deo, N. (1997). Graph Theory With Aplication to Engineering and Computer Science. Prentice-Hall of India.

Hadley, G. (1961). Linier Algebra. Adison-Wesley PublishingCo.

Hayu, W., Yuliani, & Sam, M., Pembentukan Pohon Merentang Minimum dengan Algoritma Kruskal. Jurnal Scientific Pinisi, 392), 108-115.

Munir, R. (2003). Matematika Diskrit. Bandung: Informatika.

Munir, R. (2012). Matematika Diskrit. Bandung: Informatika.

Raharjo, R.S. (2009). Penentuan Jumlah Spanning-tree pada Graf Berarah dengan menggunakan Metode Pertukaran Sisi dan Matriks In-Degree. Diakses tanggal 26 Januari 2016 di www.lib.unnes.ac.id/3106/1/4788.pdf.

Rahmawati, N. D. (2016). Teorema Pohon Matriks untuk Menentukan Banyaknya Pohon Rentangan Graf bipartisi Komplit Jurnal Kajian Keismlaman dan Kemasyarakatan, 1(1), 87-100.

Rizki, S. (2012). Penerapan Teori Graf untuk Menyelesaikan Masalah Minimum Spanning Tree (MST) Menggunakan Algoritma Kruskal. Jurnal Ilmiah Mustek Anim, 1(2), 142-152.

Rubrik Matematika Majalah 1000guru. 2013 Teka-teki Jembatan Konigsberg. Diakses tanggal 1 Maret 2016 di http://majalah1000guru.net/2013/08/jembatan-konigsberg/

Sam, M. & Yuliani. (2016). Penerapan Algoritma Prim untuk Membangun Pohon Merentang Minimum (Minimum Spanning Tree) dalam Pengoptimalan Jaringan Transmisi Nasional Prvinsi Sulsel. Jurnal Dinamika, 7(1), 50-61.

Siang, J. (2002). Matematika Diskrit dan Aplikasinya pada Ilmu Komputer. Yogyakarta: Andi.

Wayangkau, I. H. (2015). Optimalisasi Particle Swarm pada Pemasangan Jaringan Pipa Air PDAM. Jurnal Ilmiah Mustek Anim, 4(1).

Weistein, Eric W. Minimum Cost Arborescences. Diakses tanggal 26 Januari 2016 di http://mathworld.worlfram.com/Arborescence.pdf

Yasin, M. & Afandi, B. (2014). Simulasi Minimum Spanning Tree Graf Berbobot Menggunakan Algoritma Prim dan Algoritma Kruskal. Eucazione, 2(2), 121-130.

DOI: https://doi.org/10.25134/jes-mat.v5i1.1650