Matching Maksimum pada Graf Petersen Berarah Berdasarkan Multiplisitas Geometri Terbesar

Abstract

Matching pada graf berarah merupakan himpunan bagian dari himpunan sisi pada graf berarah tanpa simpul awal atau simpul akhir yang sama. Simpul-simpul matching pada graf berarah memiliki kaitan erat dengan multiplisitas geometri terbesar dari matriks ketetanggaan graf berarah. Penelitian ini bertujuan untuk mengidentifikasi matching maksimum pada graf Petersen berarah dengan pendekatan multiplisitas geometri terbesar. Hasil penelitian menuntuujan bahwa matching maksimum pada graf Petersen berarah tanpa 2 sikel faktor berkaitan dengan multiplisitas geometri terbesar matriks ketetanggaan graf, sedangkan graf Petersen berarah dengan 2 sikel faktor mempunyai perfect matching maksimum yang diperoleh dari bentuk kanonik kolom dari matriks ketetanggaan graf berarah.

Kata kunci:  Matching, Multiplisitas geometri, Graf Petersen berarah, Sikel faktor.