Risky Samodra Raharjo, 4150405515 (2009) Penentuan Jumlah Spanning-tree pada Graf Berarah dengan Menggunakan Metode Penukaran Sisi dan Matriks In-degree. Under Graduates thesis, Universitas Negeri Semarang.

Preview

PDF (Penentuan Jumlah Spanning-tree pada Graf Berarah dengan Menggunakan Metode Penukaran Sisi dan Matriks In-degree) - Published Version Download (361kB) | Preview

Abstract

Graf memiliki banyak konsep. Salah satu diantaranya adalah konsep pohon (tree). Pohon adalah graf terhubung yang tidak memuat siklus. Konsep pohon merupakan konsep yang paling penting dan populer karena konsep ini mampu mendukung penerapan graf dalam berbagai bidang ilmu. Sedangkan Spanning-tree adalah sebuah pohon pada graf G yang memuat semua titik di G. Dari setiap graf dapat dibentuk paling sedikit sebuah spanning-tree. Permasalahan dalam skripsi ini adalah bagaimana menentukan jumlah spanning-tree pada graf berarah, baik dengan menggunakan metode penukaran sisi maupun dengan matriks in-degree. Metode yang digunakan dalam penelitian ini adalah studi pustaka. Langkah pertama yang dilakukan dalam penelitian ini adalah menemukan masalah. Kemudian merumuskan masalah, selanjutnya dengan menggunakan analisis pemecahan yang dapat dilakukan dengan dua cara yaitu menggunakan metode penukaran sisi dan menggunakan matriks in-degree sehingga tercapai tujuan penulisan skripsi. Pada pembahasan, untuk menentukan banyaknya spanning-tree pada graf berarah G dengan metode penukaran sisi dapat dilakukan dengan cara: membuat spanning-tree awal, kemudian menambahkan chord dan menghapus branch maka akan terbentuk spanning-tree baru. Untuk selanjutnya, dengan langkah yang sama maka akan terbentuk spanning-tree yang lain dengan berdasar pada spanning-tree awal. Sedangkan untuk menentukan banyaknya spanning-tree dengan matriks indegree dapat digunakan teorema: nilai kofaktor kqq dari K(G) adalah sama dengan banyaknya arborescence pada G dengan titik vq sebagai root. Arborescence pada G juga merupakan spanning arborescence. Berdasarkan hasil penelitian tersebut penulis menyarankan kepada pembaca untuk melakukan penelitian lebih lanjut dalam menentukan jumlah spanning-tree pada graf berarah yang bukan arborescence.

Actions (login required)

View Item