Keanalogan graf dan matroid pada operasi penghapusan, pengerutan, dual, dan definisi keterhubungan

Abstract

Teori matroid merupakan teori yang diambil dari konsep matriks dan graf. Matroid terdiri atas koleksi himpunan bagian-himpunan bagian dari suatu himpunan berhingga dan himpunan berhingga itu sendiri. Pada matroid terdapat suatu matroid yang diperoleh dari suatu graf, matroid ini disebut cycle matroid. Dalam cycle matroid, himpunan berhingga yang dimaksud adalah himpunan sisi-sisi pada graf sedangkan himpunan bagian dari himpunan sisi-sisinya adalah himpunan sisi-sisi yang membentuk cvele. Penulisan ini membahas mengenai pembentukan suatu cycle matroid dan keanalogan operasi penghapusan, pengerutan, dual dan definisi keterhubungan pada graf dan matroid. Operasi penghapusan dan pengerutan pada tulisan ini merupakan operasi penghapusan dan pengerutan pada sisi-sisi dari graf. Dalam operasi penghapusan dan pen pengerutan pada graf dan matroid terdapat operasi yang analog yaitu operasi pembentukan cycle matroid dari graf yang mengalami pengerutan atau penghapusan dengan suatu cycle matroid yang mengalami pengerutan atau penghapusan. Operasi penghapusan dan pengerutan pada graf dan matroid dapat dihubungkan dengan operasi lain yaitu operasi dual. Operasi dual adalah operasi yang mengkonstruksikan suatu graf atau matroid yang berbeda dari graf atau matroid asalnya. Pada dual graf dan matroid, terdapat sifat dual graf yaitu (G/e)*=G*\c* yang analog dengan sifat dual matroid (M/T)*=M*\T, dengan e∈ E(G) dan TCE(M). Sedangkan dalam definisi keterhubungan antara graf dan matroid terdapat hubungan keanalogan graf dan matroid pada definisi keterhubungan graf dan matroid menurut Tutte. Keanalogan ini ditunjukkan dengan samanya nilai keterhubungan pada graf dan matroid.