Graf adalah himpunan sejumlah titik (vertices) dan sisi (edges). Sebagai contoh, gambar berikut menyatakan sebuah graf dengan 5 titik dan 5 sisi:
Dalam kehidupan sehari-hari, graf ini mungkin menyatakan hubungan pertemanan di antara 5 orang. Orang pertama berteman dengan orang kedua dan kelima, tetapi orang kedua tidak berteman dengan orang kelima, dan seterusnya.
Graf dengan 5 titik disebut sebagai graf berorde 5. Pada graf berorde 5, ada 10 sisi yang mungkin menghubungkan satu titik dengan titik lainnya. Graf berorde 5 dengan 10 sisi, seperti tampak di bawah ini, merupakan graf lengkap.
Nah, diberikan sebuah graf, kita dapat mengamati graf komplemen-nya, yaitu graf yang bila ‘digabungkan’ dengan graf semula akan menjadi graf lengkap. Sebagai contoh, kedua graf berikut merupakan komplemen satu terhadap yang lainnya:
Perhatikan bahwa kedua graf berorde 5 di atas ‘serupa’ atau isomorfik satu terhadap yang lainnya, karena
Dengan perkataan lain, graf berorde 5 yang berwarna biru isomorfik dengan graf komplemennya yang berwarna merah.
Dari pengamatan awal ini, kita mempunyai problem riset yang menarik, yaitu menentukan semua graf yang isomorfik dengan graf komplemennya. Dengan hitung-hitungan sederhana, kita peroleh bahwa suatu graf akan isomorfik dengan graf komplemennya hanya jika graf tersebut memiliki orde 4k atau 4k + 1.
Jika Anda tertarik dengan problem ini, mulailah bekerja dengan graf orde 4, 5, 8, dan 9, terlebih dahulu. Tentukan semua graf berorde 4, 5, 8, dan 9, yang serupa dengan graf komplemennya. Bila Anda beruntung, Anda mungkin akan menemukan ide bagaimana mencari graf berorde lebih tinggi yang isomorfik dengan graf komplemennya.
*
Bandung, 20-05-2016
Bermatematika 