Klasifikasi Graf Petal berdasarkan teorema Vising

Oleh :
Martopo - M0102034 - Fak. MIPA

ABSTRAK Berdasarkan teorema Vizing, graf dapat diklasikasikan sebagai kelas 1 dan kelas 2. Pengklasikasian ini termasuk masalah yang rumit. Beberapa ilmuwan telah berusaha menyederhanakan permasalahan ini dengan membuat dugaan dan teorema. Cariolaro dan Cariolaro [2] kemudian mengklasikasikan graf-graf yang mempunyai kesamaan sifat. Graf ini disebut sebagai graf petal karena bentuknya menyerupai petal. Tujuan dari penulisan skripsi ini adalah memperkenalkan tentang ukuran petal. Selain itu, skripsi ini juga bertujuan mengklasikasikan graf petal menjadi kelas 1 dan kelas 2. Skripsi ini ditulis dengan menggunakan metode studi literatur yaitu dengan menuliskan kembali pengklasikasian graf petal yang dilakukan oleh Cariolaro dan Cariolaro [2]. Beberapa lema pengantar dibuktikan terlebih dahulu sebelum membuktikan teorema utama yang digunakan untuk pengklasikasian graf petal. Pada akhir skripsi ini disimpulkan bahwa ukuran petal adalah jarak antarbasepoints di core dari graf dan bahwa semua graf petal adalah kelas 1 kecuali graf petal yang isomors dengan graf Petersen yang dihapus salah satu vertexnya.