BAB 1 PENDAHULUAN
1.1. Latar Belakang Sebuah graph G adalah sebuah objek yang terdiri atas sekumpulan titik yang disebut verteks dan garis yang menghubungkan dua buah verteks yang disebut sisi atau edge. Pada graph G terdapat pengulangan setiap pasangan verteks (u, v) dan (v, u) yang dapat ditulis dengan (u, v). Sebuah graph dikatakan terhubung apabila terdapat bilangan bulat positif k, sehingga untuk pasangan verteks u dan v terdapat jalan dengan panjang k dari verteks u ke v dan dari v ke u. Sebuah graph G adalah primitif jika dan hanya jika G terhubung dan G memuat sedikitnya satu cycle ganjil, dimana cycle ganjil adalah cycle dengan panjang ganjil (Bo, 2003). Eksponen graph G adalah bilangan bulat positif terkecil k sehingga untuk setiap pasangan verteks u dan v di G terdapat jalan dengan panjang k yang menghubungkan u dan v ditulis exp(G). Andaikan G adalah sebuah graph atas n verteks {v1, v2, . . . , vn }. Sebuah matriks ketetanggaan dari graph G adalah sebuah matriks bujursangkar A yang berordo n. Matriks A adalah primitif jika setiap entri Am > 0, dan bilangan bulat positif terkecil m disebut eksponen dari graph G ditulis exp(G). Konsep dari graph primitif digunakan dalam berbagai hal, diantaranya pada jaringan Google dan Automata. Penerapan graph pada Google yaitu keterhubungan antara suatu web dengan kata kunci yang dimasukkan. Dengan kata kunci yang dimasukkan, maka Google akan mencari kata-kata pada web-web yang ada yang berkaitan dengan kata kunci tersebut. Kata-kata kunci dan web yang berkaitan membentuk sebuah graph. Page dan Brin (Langville dan Meyer, 2006) mengungkapkan bahwa graph Google harus primitif karena bila tidak primitif maka pencarian tidak akan berhasil. Selanjutnya Langville dan Meyer (2006) menambahkan graph Google harus berupa matriks bujursangkar S dengan S m > 0, dan m > 0. Dari pendapat Langville dan Meyer, graph Google adalah primitif karena semua entri dari S m adalah positif. Penggunaan graph primitif berikutnya yaitu pada Automata. Penggunaan graph primitif pada automata yaitu tentang sinkronisasi automata. Culik II, et. al. (2002) menyebutkan bahwa setiap Automata yang primitif adalah sinkron dan jika imprimitif maka automata tidak sinkron. 1
Universitas Sumatera Utara
2 Digraph atau graph berarah merupakan bagian dari teori graph. Seperti halnya graph, sebuah digraph D adalah sebuah objek yang terdiri atas sekumpulan titik yang disebut sebagai verteks dan garis berarah yang menghubungkan dua buah verteks di D yang disebut sebagai busur atau arc. Suatu digraph D dikatakan terhubung kuat apabila untuk setiap pasangan verteks u dan verteks v atau (u, v) di D terdapat jalan dari verteks u ke verteks v dan dari verteks v ke verteks u. Sebuah digraph D dikatakan primitif jika dan hanya jika D terhubung kuat dan pembagi persekutuan terbesar dari panjang cycle-cycle di D adalah 1 (Brualdi dan Ryser, 1991). Brualdi dan Ryser (1991) menambahkan suatu digraph D adalah primitif jika dan hanya jika terdapat bilangan bulat positif k sedemikian sehingga untuk setiap pasangan verteks (u, v) di D terdapat jalan dengan panjang k. Bilangan bulat positif k bervariasi dan nilai terkecil dari k disebut sebagai ekponen dari digraph D dan ditulis dengan exp(D). Bo (2003) mendefinisikan exp(D; u, v) sebagai bilangan bulat positif terkecil k sedemikian sehingga terdapat jalan dengan panjang m dari verteks u ke verteks v untuk setiap m ≥ k dan exp(D) = maxu,v∈V (D) exp(D; u, v). Penelitian tentang digraph primitif telah banyak dilakukan (Brualdi dan Ryser, 1991). Secara khusus Wielandt (Schneider, 2003) memberi penjelasan tentang digraph primitif D dengan n verteks. Wielandt memperlihatkan bahwa jika A adalah primitif maka A(n−1)
2 +1
> 0 dan exp(D) = (n − 1)2 + 1, dimana A
merupakan sebuah matriks ketetanggaan dari digraph D dengan ordo n. Kirkland (1997) tentang kasus hamiltonian pada digraph primitif D atas n verteks yang terdiri dari 2 cycle dengan n ≥ 3 dan memperlihatkan bahwa exp(D) = b[(n − 1)2 + 1]/2c + 2. Penelitian tentang digraph primitif terus berkembang hingga sampai kepada kelas digraph dwiwarna. Sebuah digraph dwiwarna atau disingkat D(2) adalah sebuah digraph yang busurnya memuat dua buah warna. Hal ini sejalan dengan pendapat Fornasini dan Valcher (1997) yaitu sebuah digraph dwiwarna adalah sebuah digraph yang setiap busurnya diberi warna merah atau biru. Sebuah digraph dwiwarna D(2) dikatakan primitif bila terdapat bilangan bulat positif h dan k sedemikian sehingga untuk setiap pasangan verteks u dan v di D(2) terdapat jalan dari u ke v dengan panjang h + k yang terdiri atas h busur berwarna merah dan k busur berwarna biru. Bilangan bulat positif terkecil h + k disebut sebagai eksponen dari digraph dwiwarna D(2) yang dinotasikan dengan exp(D(2) ). Universitas Sumatera Utara
3 Penelitian tentang eksponen dari digraph dwiwarna dimulai oleh Shader dan Suwilo (2003). Mereka memperlihatkan bahwa bila D adalah digraph dwiwarna primitif atas n verteks, maka 2-eksponen terbesar dari D terletak pada interval [ 21 (n3 − 5n2 ), 32 n3 + n2 − n]. Lee dan Yang (2005) memperlihatkan untuk digraph dwiwarna primitif dengan dua cycle dengan panjang (n− 1) dan (n− 2), eksponen terbesarnya terletak diantara [2n2 − 8n + 7, 2n2 − 5n + 3]. Gao dan Shao (2005) memperlihatkan bila digraph dwiwarna D terdiri dari dua cycle dengan selisih satu, exp(D) = 2n2 − 3n + 1. Suwilo (2009) memerlihatkan digraph dwiwarna primitif yang asimetrik yang terdiri atas n verteks dan terdapat cycle s dengan s ≤ n, eksponennya terletak antara [(n2 − 1)/2, 3n2 + 2n − 2] ketika n ganjil dan [n2 /2, 3n2 + 2n − 2] ketika n genap. Suwilo (2012) memperlihatkan untuk digraph dwiwarna primitif yang terdiri dari dua cycle yaitu C1 dan C2 , ekponen dari D(2) adalah exp(D(2) ) = `(C1 )`r + `(C2 )`b . Lebih lanjut Gao dan Shao (2009) mengembangkan konsep eksponen lokal dari digraph ke eksponen lokal dari digraph dwiwarna. Eksponen lokal keluar dari sebuah verteks vi pada sebuah digraph dwiwarna D(2) , expout(D(2) , vi), adalah bilangan bulat positif terkecil s+t sehingga untuk setiap verteks vj , j = 1, 2, . . . , n di D(2) terdapat jalan dari vi ke vj yang terdiri atas s busur merah dan t busur biru. Eksponen lokal keluar dari beberapa kelas-kelas tertentu digraph dwiwarna yang terdiri atas dua cycle telah dibicarakan dalam literatur Gao dan Shao (2009), Suwilo (2011), Syahmarani dan Suwilo (2012). Namun demikian, eksponen lokal untuk kelas digraph dari dua cycle secara umum belum terdapat dalam literatur. Digraph dwiwarna dua cycle adalah semua digraph dwiwarna yang terdiri atas dua cycle, baik bersinggungan maupun berpotongan. Sejalan dengan ekponen lokal keluar, pada penelitian ini difokuskan pada eksponen lokal masuk. Eksponen lokal masuk dari sebuah verteks vi di D(2) , dinotasikan expin(D(2) , vi), didefinisikan sebagai bilangan bulat positif terkecil s0 + t0 sehingga untuk setiap verteks vk , k = 1, 2, . . . , n di D(2) terdapat sebuah jalan dari verteks vk menuju ke verteks vi yang terdiri atas s0 busur merah dan t0 busur biru. Bila R dan B masing-masing adalah matriks ketetanggaan merah dan biru dari digraph dwiwarna D(2) , maka eksponen lokal masuk dari verteks vi , i = 1, 2, . . . , n dapat dipandang sebagai persoalan optimisasi 0 0
expin(D(2) , vi ) = 0min {s0 + t0 : (R, B)(s ,t ) (:, i) > 0} 0 s ,t ,≥0
dimana (R, B)
(s0 ,t0 )
0 0
(:, i) adalah kolom ke i dari (R, B)(s ,t ) . Universitas Sumatera Utara
4 Hasil-hasil dari penelitian ini penting bagi penentuan batas bawah bagi reset treshold untuk automata tersinkronkan. Sebuah automata atas n state {v1 , v2, . . . , vn } dan dua alpabet {a, b} dikatakan tersinskronkan apabila terdapat sebuah state u sehingga untuk setiap state vi dapat bergerak ke state u dengan menggunakan sebuah barisan yang terdiri dari h alpabet a dan k alpabet b. Reset treshold dari sebuah automata A, dinotasikan dengan rt(A), adalah bilangan bulat terkecil h + k sehingga A adalah tersinkronkan. Bila D(2) adalah representasi digraph dwiwarna dari automata A dengan dua alpabet, maka expin(D(2) ) ≤ rt(A). 1.2. Perumusan Masalah Penelitian tentang eksponen digraph sampai ke eksponen digraph dwiwarna telah dilakukan sejak tahun 1997. Penelitian yang telah dilakukan membahas tentang eksponen dan eksponen lokal keluar. Namun penelitian tentang eksponen lokal masuk pada digraph dwiwarna khusus untuk kelas digraph dwiwarna dengan dua cycle belum dibicarakan dalam literatur. 1.3. Tujuan Penelitian Tujuan dari penelitian ini adalah menentukan nilai dari expin(D(2) , vi) bila D(2) adalah digraph dwiwarna primitif atas n verteks yang terdiri atas tepat dua cycle dengan panjang selisih dua. 1.4. Manfaat Penelitian Penelitian ini memberikan teori baru tentang eksponen lokal masuk dari digraph dwiwarna atas n verteks yang terdiri tepat atas dua cycle dengan panjang selisih dua. 1.5. Metodologi Penelitian Metodologi penelitian yang dilakukan adalah bersifat literatur dengan langkahlangkah sebagai berikut: 1. Menggambar digraph dwiwarna primitif yang terdiri atas dua buah cycle dengan panjang masing-masing s dan s + 2 dimana s ≥ 3 merupakan bilangan ganjil. Warna dari setiap gambar berbeda disesuaikan dengan kombinasi warna yang dapat dibuat. Universitas Sumatera Utara
5 2. Membuat matriks ketetanggaan dari masing-masing warna yaitu merah R dan biru B. 3. Dengan menggunakan code program yang ditulis dengan MATLAB akan ditentukan kandidat bagi bilangan-bilangan tak negatif s0 dan t0 sehingga expin(D(2) , v` ) = s0 + t0. Hal ini dilakukan dengan menghitung hasil kali (h, k)-Hurwitz dari matriks ketetanggaan R dan B secara rekursif. 4. Dengan s0 dan t0 yang sudah ditemukan pada proses komputasi di atas, langkah selanjutnya adalah menentukan batas bawah dan batas atas bagi vektor x dalam persamaan-persamaan diopanthin h i r(pj,` ) s0 Mx + = t0 . b(pj,` ) Batas bawah bagi x dilakukan dengan membandingkan panjang path dari vj , j = 1, 2, . . . , n, ke v` dan cycle dari v` ke v` . Yakni dengan menentukan nilai x dari persamaan
h i h 0i r(pj,` ) s0 s Mx + = t0 dan My = t0 . b(pj,` ) Batas atas dilakukan dengan membuktikan bahwa sistem persamaan h i 0 r(pj,` ) Mx + = s0 , j = 1, 2, . . . , n b(pj,` ) t mempunyai solusi tak negatif untuk semua verteks vj dan untuk beberapa path pj,` dari vj ke v` . 5. Mempelajari hubungan setiap gambar dengan nilai eksponen lokal masuk (s0 + t0) sehingga diperoleh kesimpulan. 6. Membuat teorema baru yang berkaitan dengan permasalahan yang diangkat. 7. Memberikan pembuktian terhadap teorema yang telah dibuat.
Universitas Sumatera Utara
