Seminar Tugas Akhir

Ikhwan Al Amin
g54100052

Pelabelan Total Sisi-Ajaib pada Graf Petersen

Seorang ahli matematikawan asal Swiss, Leonardo Euler, pada tahun 1736 memperkenalkan salah satu cabang ilmu matematika yang disebut “Teori Graf”. Ketika itu Euler memperkenalkan teori tersebut untuk menyelesaikan masalah jembatan Königsberg yang merupakan salah satu masalah transportasi yang terjadi di kota Kaliningrad, Rusia. Ia memodelkan permasalahan tersebut ke dalam model matematika berupa bagan yang terdiri dari simpul dan sisi. Contoh graf yang sangat populer saat ini adalah graf Petersen. Salah satu permasalahan utama dalam teori graf adalah bagaimana menandai suatu simpul dan sisi, sedemikian sehingga setiap simpul dan sisi yang saling terhubung memiliki tanda yang berbeda. Ada beberapa metode yang dapat digunakan untuk menandai suatu simpul/sisi, salah satunya adalah metode pelabelan. Pelabelan pada suatu graf merupakan fungsi bijektif yang memetakan setiap unsur himpunan simpul dan setiap unsur himpunan sisi ke bilangan asli yang disebut label. Salah satu contoh pelabelan adalah pelabelan ajaib. Suatu pelabelan total pada graf G dengan banyaknya simpul v dan banyaknya sisi e adalah pemetaan satu-satu dari himpunan V (G)∪E(G) ke himpunan bilangan bulat positif {1, 2, ... , v + e}. Jika penjumlahan label sisi dan label dua simpul yang menempel pada sisi tersebut yang disebut sebagai bobot sisi memiliki bobot sisi yang sama untuk setiap sisi di G, maka pelabelan ini disebut pelabelan total sisi-ajaib. Karya ilmiah ini membuktikan dua buah teorema pelabelan total sisi-ajaib pada graf umum Petersen.