Enumerasi Burnside-Polya pada Graph sederhana non Isomorfik

ABSTRAK

Matematika diskrit adalah cabang matematika yang mengkaji objek-objek diskrit. Diskrit artinya terdiri dari elemen-elemen yang berbeda atau tidak terhubung. Integer adalah contoh sistem bilangan diskrit, sedangkan real adalah contoh sistem malar (continue). Beberapa topik yang terkait dengan Matematika Diskrit meliputi: Himpunan, Relasi dan Fungsi, Induksi Matematika, Kombinatorial, Aljabar Bolean, Graph, Pohon dan Kompleksitas Algoritma.

Banyak bidang-bidang keilmuan yang sering mengacu ke pokok-pokok bahasan Matematika Diskrit Graph misalnya, banyak digunakan dalam Teori Transportasi, Optimalisasi, Antrian dan lain-lain. Masalah untuk menentukan banyak graph sederhana berlabel dengan n titik mudah untuk diselesaikan. Dari konsekuensi Lemma Jabat Tangan ada n(n-l)/2 banyak sisi yang mungkin dan setiap sisi dapat ada atau tidak ada (pilihan atas dua kemungkinan). Jadi banyak graph sederhana berlabel dengan n titik adalah 2"(""2٠/(ا Ketika menghitung graph tidak berlabel yang tidak isomorfik akan memakan waktu yang lama jika harus mendaftar semua graph yang mungkin. Untuk itu perlu ditemukan cara lain menghitungnya. Pada tahun 1935 George Polya menemukan rumus umum yang dapat dipakai untuk menghitung banyak graph tidak berlabel dengan sembarang banyak titik dan sisi yang kemudian dikenal dengan Teorema Bumside-Polya.

Teorema Polya I yang dirumuskan dengan Z(G;r,r.r,.../)berhubungan dengan banyaknya graph sederhana yang terdiri dari n titik dan tidak isomorfis antara satu graph dengan yang lainnya. Sedangkan Teorema Polya II yaitu ممدل...,2ئ,ادذ٢و)تم) berhubungan dengan banyaknya graph sederhana yang memuat n titik dan k garis serta tidak isomorfis antara satu graph dengan yang lainnya.

Teknik menghitung banyak (jumlah) graph sederhana yang tidak isomorfis dengan Teorema Bumside-Polya dimulai dengan membangkitkan grup permutasi titik terlebih dahulu.

Meskipun penghitungan dengan Teorema Polya akan memakan waktu yang lama akan tetapi dengan Teorema Polya penggambaran graph komplit sederhana dapat ditentukan titik dan garisnya dengan teliti, hal ini mengakibatkan untuk jumlah titik yang lebih banyak akan lebih mudah dicari bentuk-bentuk tidak isomorfisnya.

Tulisan ini akan menyajikan proses pembuktian Teorema Bumside-Polya dan aplikasinya pada enumerasi graph sederhana non isomorfik.