Penentuan Banyaknya Graf Sederhana Yang Tidak Isomorfis Dengan Teorema Polya

Nefiyondra, Nefiyondra (2008) Penentuan Banyaknya Graf Sederhana Yang Tidak Isomorfis Dengan Teorema Polya. Masters thesis, Program Pascasarjana Unand.

PDF (Penentuan Banyaknya Graf Sederhana Yang Tidak Isomorfis Dengan Teorema Polya) - Supplemental Material Available under License Creative Commons Public Domain Dedication. Download (325Kb)

Abstract

Salah satu masalah pokok dalam Teori Graf adalah masalah enumerasi, yaitu masalahyang berhubungan dengan penghitungan atau pencacahan graf. Dalam tulisannya Santosa R.G (2003) menentukan banyaknya graf sederhana yang dapat dibentuk dari 4 titik, sedangkan Alfajri (2007),menentukan banyaknya graf sederhana dari 5 titik. Oleh karena penelitian tersebut hanya meneliti sampai 5 titik, maka penulis akan melanjutkannya sampai 6 titik. Tujuan penelitian adalah untuk menunjukkan penggunaan Teorema polya I dan Teorema Polya II pada enumerasi graf sederhana. Penelitian ini dilaksanakan dari bulan Januari hingga bulan Mei 2008, di Jurusan Matematika Universitas Andalas padang. Adapun langkah-langkah yang dilakukan dalam penelitian ini adalah : 1. Menentukan indeks siklik S6. 2. Menentukan indeks siklik R6. 3. Penggunaan Teorema polya I. 4. Penggunaan Teorema polya II. Dengan menggunakan Teorema polya I, untuk n = 6 dapat dibentuk 156 buah graf sederhana yang tidak isomorfis satu sama lain. Selanjutnya dengan menggunakan Teorema Polya II dapat diketahui bahwa dari 156 buah graf tersebut terdiri dari graf sederhana yang saling tidak isomorfis sebanyak: 1 graftanpa sisi 24 graf dengan 8 sisi 1 grafdengan 1 sisi 21 grafdengan 9 sisi 2 graf dengan 2 sisi 15 grafdengan l0 sisi 5 grafdengan 3 sisi 9 grafdengan 11 sisi 9 grafdengan 4 sisi 5 grafdengan 12 sisi 15 grafdengan 5 sisi 2 grafdengan 13 sisi 21 grafdengan 6 sisi 1 grafdengan 14 sisi 24 graf dengan 7 sisi 1 grafdengan 15 sisi. Dari hasil penelitian ini dapat disimpulkan bahwa: 1. Teorema Polya I dapat kita gunakan untuk menghitung banyaknya graf sederhana yang terdiri dali n buah titik yang tidak isomorfis satu sama lain. 2. Teorema Polya II dapat kita gunakan untuk menghitung banyaknya graf sederhana yang terdiri dan n buah titik dan /r buah sisi (edge) serta tidak isomorfis satu sama lain.

Actions (login required)

View Item