Wendy Lestyo Purnomo, 4150406029 (2011) Penggunaan Teorema Polya Dalam Enumerasi Graf. Under Graduates thesis, Universitas Negeri Semarang.

Preview

PDF (Penggunaan Teorema Polya Dalam Enumerasi Graf) - Submitted Version Download (1MB) | Preview

Abstract

Salah satu yang dipelajari dalam ilmu aljabar abstrak adalah teori grup. Munculnya teori grup didasari dari penyelidikan permutasi suatu himpunan berhingga. Dalam konsep tindakan suatu grup terhadap himpunan berhingga yang tidak kosong terdapat beberapa teorema yang bisa digunakan untuk menyelesaikan masalah enumerasi, diantaranya adalah Teorema Polya. Masalah enumerasi merupakan masalah kombinatorika yang mempelajari pengaturan objek-objek yang berkisar pada persoalan pencacahan dari suatu pengaturan. Pada penelitian kali ini penulis tertarik untuk mengkaji tentang enumerasi graf dengan n simpul. Enumerasi graf yang dimaksud dalam penelitian ini adalah banyaknya graf yang dapat dibentuk dari n simpul yang takisomorfik satu dengan yang lainnya. Permasalahan dalam skripsi ini adalah sebagai berikut. Pertama, bagaimana hasil enumerasi graf n simpul dengan menggunakan Teorema Polya. Kedua, bagaimana perbandingan hasil penyelesaian masalah enumerasi graf yang diselesaikan dengan Teorema Polya dan dengan menggunakan software Maple dan The Graph Isomorphism Algorithm Demonstration Program. Metode yang digunakan dalam penelitian ini yaitu identifikasi masalah, perumusan masalah, studi pustaka, pemecahan masalah, dan penarikan simpulan. Kesimpulan yang didapat dalam penelitian ini sebagai berikut: Banyaknya multigraf tak isomorfis yang terbentuk dari dua simpul ada sebanyak 3, banyaknya graf tak isomorfis yang terbentuk dari dua simpul ada sebanyak 6, banyaknya multigraf tak isomorfis yang terbentuk dari tiga simpul ada sebanyak 10, banyaknya graf tak isomorfis yang terbentuk dari tiga simpul ada sebanyak 20, banyaknya multigraf tak isomorfis yang terbentuk dari empat simpul ada sebanyak 66, banyaknya graf tak isomorfis yang terbentuk dari empat simpul ada sebanyak 90, banyaknya multigraf tak isomorfis yang terbentuk dari lima simpul ada sebanyak 792, banyaknya graf tak isomorfis yang terbentuk dari lima simpul ada sebanyak 544, banyaknya multigraf tak isomorfis yang terbentuk dari enam simpul ada sebanyak 25.506, banyaknya graf tak isomorfis yang terbentuk dari enam simpul ada sebanyak 5.096, banyaknya multigraf tak isomorfis yang terbentuk dari tujuh simpul ada sebanyak 2.302.938, banyaknya graf tak isomorfis yang terbentuk dari tujuh simpul ada sebanyak 79.264, banyaknya multigraf tak isomorfis yang terbentuk dari delapan simpul ada sebanyak 591.901.884, banyaknya graf tak isomorfis yang terbentuk dari delapan simpul ada sebanyak 2.208.612. Dengan software Maple dan The Graph Isomorphism Algorithm Demonstration Program diperoleh semua graf yang terbentuk dari n simpul tak isomorfik satu dengan yang lainnya. Saran dari penulis yaitu adanya penelitian mengenai Teorema Polya yang dikembangkan pada pewarnaan graf dan enumerasi graf berarah.

Actions (login required)

View Item