Graf dan Komplemennya

Graf adalah himpunan sejumlah titik (vertices) dan sisi (edges). Sebagai contoh, gambar berikut menyatakan sebuah graf dengan 5 titik dan 5 sisi:

graf pentagon

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.

graf komplelen-2

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:

graf komplemen-1

Perhatikan bahwa kedua graf berorde 5 di atas ‘serupa’ atau isomorfik satu terhadap yang lainnya, karena

graf komplemen-3

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s