Graf Primitif

Salah satu yang harus dikuasai tentang graf yaitu adanya graf primitif. Definisi dari graf primitif yaitu graf terhubung dimana terdapat sebuah bilangan bulat positif k sehingga untuk setiap pasangan titik u dan v terdapat sebuah jalan Wuv dengan panjang k. Untuk lebih mudahnya sebuah graf G dikatakan primitif dapat dilihat jika G merupakan graf terhubung dan terdapat paling sedikit satu cycle ganjil. Oleh karena itu contoh sederhana untuk graf primitif adalah cycle dengan n vertex dimana n lebih besar dari satu dan merupakan bilangan ganjil. 

Gambar 1. Cycle dengan 5 vertex

Untuk melihat berapa nilai k yang didefinisikan sebelumnya, dapat dicari dengan merepresentasikan graph primitif tersebut kedalam bentuk matriks persegi non negatif. Sebagai contoh dari Gambar 1 diperoleh matriks sebagai berikut :

dan untuk mendapatkan nilai k cukup kita pangkatkan matriks A sehingga semua entri di matriks A adalah positif. Dengan bantuan program matlab, diperoleh 

saat A pangkat 4 semua entri bernilai positif. Karena 4 adalah bilangan positif sehingga cycle dengan 5 vertex tersebut merupakan graf primitif dengan nilai  k = 4. 

Sekian penjelasan tentang graf primitif..  Mohon maaf jika ada penjelasan yang kurang dan terlewatkan dari saya. Terimakasih ^^