Perpustakaan Digital ITB

Misalkan G=(V,E) adalah suatu graf sebarang (terhubung atau tidak terhubung) dan Π adalah suatu partisi V(G). Representasi suatu titik v∈V(G) terhadap partisi Π dinyatakan sebagai vektor jarak titik v tersebut terhadap Π. Selanjutnya Π dinamakan partisi pembeda G jika setiap titik di G memiliki representasi yang berbeda terhadap Π. Dimensi partisi dari G adalah kardinalitas minimum suatu partisi pembeda di G. Penentuan dimensi partisi suatu graf tergolong kasus NP-complete, artinya tidak terdapat solusi waktu polinomial dalam menyelesaikan dimensi partisi sebarang graf. Dengan demikian kajian dilakukan dengan membatasi untuk kelas graf tertentu atau dengan mengkarakterisasi graf yang memiliki dimensi partisi tertentu. Dalam hal G adalah graf terhubung, dimensi partisi beberapa kelas graf telah diketahui, di antaranya adalah graf lintasan, graf siklus, graf bintang, graf bintang ganda, graf lengkap, graf ulat, graf roda, graf bipartit dan graf r-partit lengkap. Untuk graf pohon secara umum yang tidak isomorfik dengan lintasan, hasil yang diperoleh baru berupa batas atas dimensi partisinya. Karakterisasi graf terhubung berorde n≥2 dengan dimensi partisi 2, n-2,n-1 atau n telah dilakukan. Namun demikian, karakterisasi graf terhubung dengan dimensi partisi lainnya masih merupakan masalah terbuka sampai saat ini. Kajian dimensi partisi juga telah dilakukan untuk graf dari hasil operasi, di antaranya adalah operasi Kartesius, perkalian kuat, operasi korona dan operasi subdivisi. Untuk graf tak terhubung G, syarat perlu sehingga dimensi partisinya adalah hingga telah diturunkan. Namun penentuan dimensi partisi graf tak terhubung masih sangat terbatas sampai sekarang. Hasil yang telah diperoleh baru untuk graf tak terhubung yang memuat graf lengkap atau komponen homogen berupa graf lintasan, graf bintang, graf bintang ganda atau graf siklus. Pada disertasi ini kajian dimensi partisi pada graf, khususnya graf tak terhubung dilanjutkan. Dimensi partisi graf tak terhubung dengan dua komponen ditentukan, yaitu saat salah satu komponennya adalah graf lintasan atau graf siklus, atau saat dua komponen tersebut memiliki dimensi partisi sama. Selanjutnya untuk graf tak terhubung dengan komponen homogen, graf yang dikaji adalah yang komponen-komponennya berupa graf siklus atau graf bipartit lengkap. Syarat cukup suatu graf berupa gabungan siklus dengan panjang yang berbeda, sehingga memiliki dimensi partisi 3 diturunkan. Selanjutnya dari syarat tersebut, dikonstruksi beberapa keluarga graf, baik terhubung maupun tak terhubung, sedemikian sehingga dimensi partisinya masih sama dengan 3. Untuk graf tak terhubung dengan komponen homogen berupa graf bipartit lengkap, selain ditentukan syarat perlu sehingga dimensi partisinya hingga, di sini dilakukan karakterisasi gabungan graf tersebut dengan dimensi partisi tertentu. Pada disertasi ini juga diturunkan batas atas dimensi partisi graf rambut dari G, yaitu graf yang diperoleh dengan menempelkan titik ujung suatu lintasan baru ke sebarang titik di G. Selanjutnya diberikan beberapa keluarga graf rambut dari G yang dimensi partisinya sama dengan dimensi partisi G, beberapa di antaranya adalah graf dengan dimensi partisi 3. Batas atas dimensi partisi graf hutan yang memuat pohon homeomorfik juga ditentukan.