BAB 1 PENDAHULUAN
1.1 Latar Belakang Penelitian
Penelitian mengenai eksponen digraf dwiwarna telah banyak dilakukan. Shader dan Suwilo (2003) adalah yang pertama sekali melakukan penelitian tersebut. Pada tahun 2002 , Wielandt ( Schneizer,H ) melakukan penelitian mengenai eksponen matrik tak negatif. Andaikan A adalah sebuah matriks tak negatif berordo n × n. Matriks tak negatif A dikatakan primitif jika dan hanya jika terdapat bilangan bulat positif k sehingga Ak bernilai positif dan bilangan bulat terkecil k disebut sebagai eksponen dari A.
Selanjutnya Digraf D(A) adalah sejumlah titik yang terhubung dengan garis berarah (arc) pada setiap pasang titik (vi , vj ) di D(A) jika dan hanya jika entri dari matriks tak negatif A, yaitu ai,j > 0, untuk i, j = 1, 2, · · · , n. Digraf D(A) dikatakan terhubung kuat jika untuk setiap pasang titik (vi, vj ) di D(A) terdapat walk dari vi ke vj dan dari vj ke vi dengan i, j = 1, 2, · · · , n. Suatu digraf D(A) dikatakan primitif jika dan hanya jika terdapat bilangan bulat positif l sehingga untuk setiap pasangan titik (vi, vj ) terdapat walk dengan panjang l, maka bilangan bulat terkecil l disebut sebagai eksponen dari digraf D(A) yang dinotasikan sebagai exp(D) (Brualdi dan Ryser,1991). Eksponen titik dari digraph D(A) adalah jumlah walk dengan panjang 0
minimum l yang menghubungkan titik vk , k = 1, 2, · · · , n ke setiap titik di D(A), dinotasikan dengan expD (vk ).
Pada tahun 1997, Fornasini dan Valcher mendefinisikan digraf dwiwarna sebagai berikut. Digraf dwiwarna D(2) merupakan suatu digraf yang setiap arcnya diberi warna merah atau biru. Digraf dwiwarna D(2) terhubung kuat dikatakan primitif 1
Universitas Sumatera Utara
2 jika terdapat suatu bilangan bulat tak negatif m dan n dengan m + n > 0 sehingga untuk setiap pasang titik (vi , vj ) di D(2) terdapat (m, n)-walk dari vi ke vj dan walk dari vj ke vi , dengan m dan n masing-masing merupakan jumlah arc merah dan arc biru, kemudian bilangan bulat positif terkecil dari m + n disebut sebagai eksponen digraf dwiwarna D(2) yang dinotasikan dengan expD(2) (Shader dan Suwilo,2003). Eksponen titik dari digraph dwiwarna D(2) adalah jumlah walk dengan panjang 0
0
minimum m + n yang menghubungkan titik vk , k = 1, 2, · · · , n ke setiap titik di D(2) 0
0
, untuk m dan n masing-masing adalah jumlah arc merah dan arc biru, dinotasikan dengan expD(2) (vk ).
Pada tahun 2009 Gao dan Shao mulai memperkenalkan konsep eksponen lokal. Andaikan D(2) adalah sebuah digraf dwiwarna primitif. Eksponen titik keluar dari digraf dwiwarna adalah bilangan bulat positif terkecil g + h sehingga terdapat (g, h)-walk untuk setiap pasang titik vk , k = 1, 2, · · · , n ke setiap titik di D(2) , dinotasikan dengan expoutD(2) (vk ) . Sedangkan eksponen titik masuk dari digraf dwi0
0
0
0
warna adalah bilangan bulat positif terkecil g + h sehingga terdapat (g , h )-walk untuk setiap titik di D(2) ke titik vk di D(2) , dinotasikan dengan expinD(2) (vk ) .
Bai dan Shao (2007) melakukan penelitian menentukan eksponen dari kelas digraf dwiwarna dengan n-titik ganjil dengan batasan eksponen serta karakteristik ekstermal dari digraf dwiwarna D(2) yang primitif atas n-titik ganjil yang memiliki dua cycle yakni n-cycle dan 21 (n + 1)-cycle. Sedangkan penelitian kali ini meneruskan penelitian yang dilakukan oleh Bai dan Shao untuk menentukan eksponen titik keluar dari digraf dwiwarna D(2) .
1.2 Perumusan Masalah
Andaikan D(2) adalah digraf dwiwarna yang primitif atas n-titik ganjil. Kemudian, mencari bagaimana pola dari eksponen titik keluar untuk setiap titik vk pada ekstermal digraf dwiwarna D(2) . Universitas Sumatera Utara
3
1.3 Tinjauan Pustaka
Pada digraf dwiwarna, komponen terpenting dari sebuah walk ditentukan oleh jumlah busur merah dan busur biru. Sebuah (h, k)-walk adalah sebuah walk yang terdiri dari h buah busur berwarna merah dan k buah busur berwarna biru. Andaikan w adalah sebuah walk dari digraf dwiwarna, dengan r(w) adalah banyaknya busur berwarna merah dari w dan b(w) adalah banyaknya busur berwarna biru. Sehingga r(w) disebut sebagai komposisi dari w. vektor b(w) Andaikan D(2) adalah sebuah digraf dwiwarna terhubung kuat dan C = {c1 , c2, ...., ct} adalah himpunan semua cycle di D(2) . Sebuah matriks cycle dari D(2) adalah sebuah matriks 2 × t dalam bentuk r(c1 ) r(c2 ) ... r(ct ) S= b(c1) b(c2 ) ... b(ct)
setiap kolom ke-i dengan i = 1, 2, ..., t dari matriks tersebut adalah komposisi dari cycle ct. Fornansi Valcher (1997) memberikan karakteristik secara aljabar bagi primitifitas digraf dwiwarna. Sebuah digraf dwiwarna terhubung kuat adalah primitif jika dan hanya jika pembagi persekutuan terbesar dari determinan submatriks 2 × 2 dari S adalah 1.
Andaikan D(2) merupakan digraf dwiwarna yang terdiri dari 2 cycle, sehingga setiap walk pada D(2) dapat didekomposisi kedalam path pi,j dari titik vi ke setiap titik vj dengan menggunakan sistem persamaan berikut r(pi,j ) g x1 + = , i, j = 1, 2, ..., n S x2 b(pi,j ) h
untuk memperoleh solusi bulat tak negatif x1 , x2 ≥ 0.
Penelitian mengenai eksponen digraf dwiwarna dimulai oleh Shader dan Suwilo (2003). Pada penelitian tersebut Shader dan Suwilo (2003) memperlihatkan bahwa Universitas Sumatera Utara
4 bila D(2) adalah digraf dwiwarna yang primitif atas n-titik, maka eksponen terbesar D(2) terletak pada interval [ 21 (n3 − 5n2 ), 12 (3n3 − 2n2 − 2n)]. Bai dan Shao (2007) melakukan penelitian menentukan eksponen dari kelas digraf dwiwarna dengan n-titik ganjil dengan batasan eksponen serta karakteristik ekstermal dari digraf dwiwarna D(2) yang primitif atas n-titik ganjil yang memiliki 2 cycle yakni n-cycle dan 21 (n + 1)-cycle. Gao dan Shao (2009) melakukan penelitian menentukan eksponen lokal keluar dari titik-titik pada digraf dwiwarna tipe Wiedlant. Gao dan Shao mendefinisikan eksponen lokal sebagai walk dengan komposisi sama yang berasal dari satu titik tertentu dan menuju kesemua titik lainnya. Suwilo (2011) menentukan eksponen lokal keluar dari titik-titik pada digraf ministrong ekstermal dwiwarna, sedangkan Syahmarani dan Suwilo (2012) menentukan eksponen lokal keluar dari digraf Hamilton dwiwarna dengan eksponen terbesar dan dengan eksponen terkecil.
Bai dan Shao membagi digraf dwiwarna D(2) berdasarkan warna arc yang terletak pada arc v1 → v 1 (n+1) menjadi dua tipe yakni : 2
1. Tipe pertama, jika arc v1 → v 1 (n+1) berwarna biru maka batasan eksponen 2
terletak pada
[ 12 (4n2
− n − 1), 4n2 − 5n] .
2. Tipe kedua, jika arc v1 → v 1 (n+1) berwarna merah maka batasan eksponen 2
terletak pada
[ 12 (4n2
− 3n + 1), 4n2 − 6n].
Penelitian kali ini bertujuan untuk menentukan bentuk umum eksponen titik keluar dari ekstermal digraf dwiwarna yang primitif atas n-titik ganjil dari tipe kedua dengan dua arc biru berturut-turut pada penelitian yang dilakukan oleh Bai dan Shao. Dalam hal ini terdapat dua karakter posisi arc biru berturut-turut yaitu :
1. arc biru tepat berada pada posisi arc v2 → v1 dan arc v1 → vn Universitas Sumatera Utara
5
Gambar 1.1 : Karakter Pertama D(2) 2. arc biru tepat berada pada posisi arc v 1 (n+1) → v 1 (n−1) dan arc v 1 (n+3) → 2
2
2
v 1 (n+1) 2
Gambar 1.2 : Karakter Kedua D(2)
1.4 Tujuan Penelitian
Tujuan dari penelitian ini adalah menentukan bentuk umum eksponen titik keluar dari digraf dwiwarna yang primitif dengan n-titik ganjil dan dua arc biru berturutturut berdasarkan warna arc.
Universitas Sumatera Utara
6 1.5 Manfaat Penelitian
Penelitian ini dilakukan untuk memperkaya literature dan menambah pengetahuan mengenai eksponen digraf dwiwarna dengan n-titik ganjil yang primitif.
Universitas Sumatera Utara
