MATROID: JEMBATAN ANTARA TEORI GRAF DAN ALJABAR LINEAR

Oleh :
Melinda Dinar Puji Anggraini - M0119058 - Fak. MIPA

Teori graf dan aljabar linear memiliki objek kajian yang berbeda, tetapi keduanya memuat pola independensi dan ketergantungan yang sebanding. Penelitian ini bertujuan menjelaskan peran matroid sebagai jembatan struktural antara kedua bidang melalui konsep himpunan independen, sirkuit, basis, rank, representasi, dan dualitas. Penelitian menggunakan kajian pustaka dengan pendekatan deskriptif-analitis. Analisis dilakukan dengan membandingkan matroid graf dan matroid representabel serta memeriksa korespondensinya melalui contoh matriks dan graf. Hasil kajian menunjukkan bahwa himpunan sisi yang tidak membentuk siklus pada graf berpadanan dengan himpunan kolom yang bebas linear pada matriks. Siklus berpadanan dengan sirkuit, pohon merentang dengan basis, sedangkan ukuran maksimum hutan berpadanan dengan rank atau dimensi ruang yang direntang. Pada contoh yang dianalisis, matroid matriks (M[A]) dan matroid graf (M(G)) memiliki koleksi sirkuit yang berkorespondensi satu-satu sehingga keduanya isomorfik. Matroid menyediakan kerangka formal untuk menjelaskan kesamaan struktur ketergantungan dalam teori graf dan aljabar linear.