DIMENSI METRIK PADA GRAF PANEKUK

Abstract

Dimensi metrik merupakan salah satu topik yang menarik dalam teori graf, khususnya untuk pengkarakterisasian dan perhitungan batas atas serta bawah dimensi metrik dari berbagai kelas graf. Pada penelitian ini, fokus diberikan pada graf Panekuk, yang memiliki keterkaitan erat dengan masalah pancake sorting problem. Penelitian ini menentukan dimensi metrik graf Panekuk $P_n$ untuk $n = 3, 4$ secara pasti, yaitu $\beta(P_3) = 2$ dan $\beta(P_4) = 3$. Selain itu, batas atas dan bawah dimensi metrik untuk $5 \leq n \leq 10$ juga ditentukan, dengan hasil bahwa $\beta(P_5)$ berkisar antara 4 hingga 6, $\beta(P_6)$ antara 5 hingga 8, $\beta(P_7)$ antara 6 hingga 11, dan seterusnya. Penelitian ini juga menghasilkan algoritma untuk menentukan batas bawah dimensi metrik graf Panekuk.