BAB 2 DIGRAF DWI-WARNA PRIMITIF
Pada Bab ini akan dijelaskan beberapa konsep dasar seperti definisi dan teorema yang dijadikan landasan dalam penelitian ini. konsep dasar yang dimaksud adalah yang berkaitan dengan permasalahan dalam penelitian ini seperti keterhubungan, primitifitas, eksponen dan eksponen titik masuk dari digraf dan digraf dwi-warna. 2.1 Definisi Pada subbab ini akan diberikan definisi tentang digraf dan digraf dwi-warna serta notasi-notasi yang akan dipergunakan dalam pembahasan selanjutnya. 2.1.1 Digraf Graf adalah himpunan tak kosong dari titik-titik yang dihubungkan oleh garis. Jika garis yang menghubungkan titik-titik tersebut diberikan arah, maka disebut sebagai digraf, dan dinotasikan sebagai D. Dengan kata lain, sebuah digraf D terdiri dari dua himpunan, yaitu : 1. Himpunan titik yang dinotasikan dengan V = {v1, v2, v3, · · · , vn } dengan i adalah bilangan bulat positif dan vi adalah elemen dari himpunan V , n(V ) 6= 0. 2. Himpunan E yang merupakan himpunan pasangan berurut V × V yang tak harus berbeda dari semua titik, elemen dari E disebut arc dari digraf D. Jika diberikan notasi E = (v1 , v3) berarti terdapat sebuah arc dari titik v1 ke v3 atau dapat dituliskan dengan notasi v1 → v3. Contoh 2.1.1 Himpunan titik V = {v1, v2 , v3, v4} dan himpunan arc E = {(v1, v2), (v2, v3), (v3, v4), (v3 , v1), (v4, v3)} adalah sebuah digraf dengan 4 titik dan 5 arc, dan dinotasikan dengan D(4, 5). D dapat direpresentasikan seperti berikut.
4
Universitas Sumatera Utara
5
Gambar 2.1 Digraf Andaikan suatu digraf D dengan n titik, dengan u dan v adalah titik di D. Suatu walk dengan panjang m dari u dan v adalah suatu barisan arc di D dalam bentuk v0 → v1 → v2 → · · · → vm dengan m ≥ 0, v0 = u dan vm = v. Jika u = v maka walk tersebut dikatakan walk tertutup dan jika u 6= v maka walk tersebut dikatakan walk terbuka. Suatu path adalah walk dengan titik yang tidak berulang, tetapi titik awal dan titik akhir boleh berulang yang disebut path tertutup. Suatu path tertutup u → v disebut dengan cycle dan cycle dengan panjang 1 disebut loop. Berikut penjelasan berdasarkan Gambar 2.1 1. Barisan arc v1 → v2 → v3 → v1 → v2 → v3 → v4 disebut walk dari v1 ke v4 2. Barisan arc v1 → v2 → v3 → v4 disebut path dari v1 ke v4 3. Barisan arc v1 → v2 → v3 → v1 disebut path tertutup atau cycle
2.1.2 Digraf Dwi-warna Digraf dengan arc yang diwarnai dengan merah atau biru, namun tidak keduanya pada satu arc sekaligus disebut digraf dwi-warna, dinotasikan dengan D(2) (Fornasini dan Valcher, 1997). Sebuah arc merah dari titik u ke titik v akan dinor b tasikan dengan u → v dan arc biru dari titik u ke titik v dinotasikan dengan u → v. Contoh 2.1.2 Himpunan titik V = {v1, v2 , v3, v4} dan himpunan arc merah A = {(v2, v3), (v3, v1), (v4, v3 )} dan himpunan arc biru B = {(v! , v2), (v3, v4)} adalah sebuah digraf dengan 4 titik dan 5 arc, dan dinotasikan dengan D(4, 5). D dapat direpresentasikan seperti berikut.
Universitas Sumatera Utara
6
Gambar 2.2 Digraf Dwi-warna Sebuah (s, t)-walk pada digraf dwi-warna D(2) adalah sebuah walk yang terdiri dari s buah arc merah dan t buah arc biru. Andaikan sebuah walk w, dengan r(w) dan b(w) masing-masing adalah banyak arc merah dan arc biru pada walk w, maka dapat dinotasikan sebagai " l(w)# = r(w) + b(w) atau dapat direpresentasikan r(w) dalam bentuk vektor, yaitu . b(w) Suatu path adalah walk dengan titik yang tidak berulang, tetapi titik awal dan titik akhir boleh berulang yang disebut path tertutup. Suatu path tertutup u → v disebut dan cycle dengan panjang 1 disebut loop, dengan komposisi " # dengan " cycle # 1 0 atau . 0 1 Berikut adalah penjelasan berdasarkan Gambar 2.2. b
r
r
b
r
b
1. v1 → v2 → " v3 #→ v1 → v2 → v3 → v4 adalah walk dari v1 ke v4 dengan 3 komposisi . 2 " # 1 b r b 2. v1 → v2 → v3 → v4 adalah path dari v1 ke v4 dengan komposisi . 2 " # 2 b r r 3. v1 → v2 → v3 → v1 adalah path tertutup atau cycle dengan komposisi . 1 2.2 Matriks Adjacency Sebuah digraf D atau digraf D(2) dapat direpresentasikan dalam (0,1)-matriks,
Universitas Sumatera Utara
7 yaitu matriks yang elemennya adalah 0 atau 1, yang disebut sebagai matriks adjacency. 2.2.1 Matriks Adjacency Digraf Sebuah matriks adjacency dari digraf dengan n-titik adalah matriks berordo n A(D) = [aij ] dengan 1 jikaterdapatarcdariv kev , i j aij = 0 sebaliknya.
Contoh 2.2.1 Berikut ini adalah representasi digraf yang terdiri dari 6 titik dan 8 arc. Dari digraf berikut dapat dibentuk sebuah matriks adjacency dengan memperhatikan arc yang menghubungkan titik-titik pada digraf tersebut.
Gambar 2.3 Digraf dengan 6 titik dan 8 arc Matriks adjacency dari digraf di atas adalah sebagai berikut.
A(D) =
0 1 0 0 0 0
0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0
2.2.2 Matriks Adjacency Digraf Dwi-warna Matriks adjacency dari sebuah digraf dwi-warna dengan n-titik dibagi menjadi
Universitas Sumatera Utara
8 dua, yaitu matriks adjacency berorde n untuk arc merah R = [rij ] dan matriks adjacency untuk arc biru B = [bij ] dengan ketentuan sebagai berikut.
1, jikaterdapatarcmerahdariv kev i j R = [rij ] = 0, jikasebaliknya. dan
1, jikaterdapatarcbirudariv kev i j B = [bij ] = 0, jikasebaliknya.
Contoh 2.2.2 Berikut adalah digraf dwi-warna yang terdiri dari 6 titik dengan 6 arc merah dan 2 arc biru.
Gambar 2.4 Digraf dwi-warna dengan 6 titik dan 8 arc Matriks adjacency dari digraf dwi-warna di atas adalah sebagai berikut.
R=
0 1 0 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 dan B = 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
Universitas Sumatera Utara
9 2.3 Primitifitas Pada subbab ini akan dibahas mengenai digraf dan digraf dwi-warna terhubung kuat dan primitifitasnya. 2.3.1 Digraf Primitif Sebuah digraf D terhubung kuat jika untuk setiap pasang titik (vi , vj ) di D terdapat walk berarah (directed walk) dari vi ke vj dan dari vj ke vi . Digraf D primitif jika dan hanya jika terdapat bilangan bulat positif m dimana ada sebuah walk dengan panjang m dari setiap pasang titik di D. Contoh 2.3.1 Berikut adalah contoh digraf terhubung kuat dan tidak terhubung kuat.
(a)
(b)
Gambar 2.5 Digraf terhubung kuat dan tidak terhubung kuat Gambar 2.5(a) menunjukkan digraf terhubung kuat karena terdapat walk dari tiap pasang titik di digraf D, dan Gambar 2.5(b) menunjukkan digraf tidak terhubung kuat, karena tidak terdapat walk dari v3 ke v4. Digraf D yang terhubung kuat dikatakan primitif , jika terdapat suatu bilangan bulat positif m sedemikian hingga untuk setiap pasang titik u dan v di D terdapat suatu walk dengan panjang m. Lemma 2.3.1 Andaikan D adalah digraf terhubung kuat, maka setiap titik v di D terletak pada cycle. Bukti Ambil sebarang titik v di digraf D dan sebarang arc dari titik u ke v di D. Karena D terhubung kuat, maka terdapat path dari titil u ke v dan path dari v ke u di D. Oleh definisi, path tertutup adalah suatu cycle, dan v adalah sebarang
Universitas Sumatera Utara
10 titik di D, maka setiap titik v di D pasti terletak pada suatu cycle. 2.3.2
Digraf Dwi-warna Primitif
Sebuah digraf dwi-warna D(2) adalah terhubung kuat jika untuk setiap pasang titik u dan v di D(2) terdapat walk dari titik u ke titik v dan walk dari titik v ke titik u tanpa memperhatikan warna setiap arc yang dilalui. Berikut adalah contoh digraf dwi-warna D(2) terhubung kuat dan digraf dwi-warna D(2) tidak terhubung kuat. Contoh 2.3.2 Representasi dari digraf dwi-warna terhubung kuat
(a)
(b)
Gambar 2.6 Digraf dwi-warna terhubung kuat dan tidak terhubung kuat Gambar 2.6 memperlihatkan bahwa (a) adalah digraf dwi-warna D(2) terhubung kuat karena terdapat walk dari satu titik ke titik yang lain dan (b) adalah digraf dwi-warna D(2) yang tidak terhubung kuat karena tidak terdapat walk dari v1 ke v2. Sebuah digraf dwi-warna terhubung kuat D(2) disebut primitif jika terdapat bilangan tak negatif s dan t sehingga untuk setiap pasang titik u dan v di D(2) terdapat (s, t)-walk dari u ke v. Andaikan C = {C1 , C2, ..., Ct} adalah himpunan semua cycle yang terdapat di D(2) dan didefinisikan M sebagai matriks cycle dari D(2) orde 2 × t dengan setiap kolom ke-i dari M merupakan komposisi dari cycle-cycle Ci , i = 1, 2, ..., t seperti berikut M=
" r(C1 ) r(C2 ) · · · b(C1) b(C2 ) · · ·
r(Ct ) b(Ct)
#
.
Sebuah digraf dwi-warna D(2) adalah primitif jika dan hanya jika pembagi persekutuan terbesar dari determinan submatriks 2 × 2 dari M adalah ±1 (Fonarsini dan
Universitas Sumatera Utara
11 Valcher, 1997). Lemma 2.3.2 Andaikan D(2) adalah digraf dwi-warna terhubung kuat dengan paling sedikit satu arc setiap warna. Misalkan M adalah matriks cycle dari D(2) . Digraf D(2) adalah primitif jika dan hanya jika content dari matriks M adalah 1. Contoh 2.3.3 Representasi digraf dwi-warna terhubung kuat dan primitif
Gambar 2.7 Digraf dwi-warna terhubung kuat dan primitif. Digraf dwi-warna D(2) pada Gambar 2.7 adalah terhubung kuat yang "terdiri # dari 3 b b r r r b b cycle v1 → v7 → v6 → v5 → v4 → v3 → v2 → v1 dengan komposisi , dan 4 " # 2 b r r b b cycle v1 → v5 → v4 → v3 → v2 → v1 dengan komposisi dan maka matriks 3 " # 3 2 cycle dari D(2) adalah M = dengan det (M) = 1. Oleh karena det (M) 4 3 = 1, maka digraf dwi-warna terhubung kuat D(2) adalah primitif. 2.4 Matriks Tak Negatif dan Eksponen Digraf Dwi-warna Berikut ini akan dibahas pengertian matriks tak negatif dan hubungannya dengan Digraf dwi-warna D(2) . 2.4.1 Matriks Tak Negatif Matriks tak negatif A merupakan sebuah matriks yang setiap entri aij dari A adalah bilangan bulat tak negatif, sebaliknya jika setiap entri aij dari matriks A adalah
Universitas Sumatera Utara
12 bilangan bulat positif maka matriks tersebut disebut matriks positif. Perhatikan dua buah matriks berikut ini. 0 1 1 9 3 1 A = 2 0 3 , matriks tak negatif; B = 5 7 2 , matriks positif. 5 7 0
6 1 1
2.4.2 Eksponen Digraf Eksponen dari sebuah digraf D merupakan bilangan bulat positif terkecil k sehingga untuk setiap pasang titik u dan v di D terdapat walk dari u ke v dengan panjang k dan dinotasikan dengan exp(D). Proposisi 2.4.2 A adalah suatu matriks adjacency dari digraf D. Entri akij dari Ak menyatakan banyak walk dari vi ke vj dengan panjang k di digraf D. Bukti. Andaikan A adalah suatu matriks adjacency dari digraf D, maka setiap entri (i, j) dari A menyatakan arc dari titik vi ke vj di digraf D. Ini mengakibatkan jika k = 1, maka setiap entri a1ij dari A1 menyatakan walk dari titik vi ke vj dengan panjang 1. (k)
Andaikan setiap entri aij dari Ak menyatakan banyaknya walk dari titik vi ke vj yang panjangnya k di D, untuk k ≥ 1. Selanjutnya akan diperlihatkan bahwa (k+1) aij adalah banyaknya walk dari vi ke vj dengan panjang k+1 di D dengan k ≥ 1. Perhatikan setiap walk dari titik vi ke vj di D dengan panjang k + 1 yang terdiri dari walk vi ke vl dengan panjang k untuk l = 1, 2, ..., n, dan dilanjutkan (k)
dengan arc dari titik vi ke vj , sehingga ail aij menyatakan walk dengan panjang k + 1 dari titik vi ke vj di D untuk k = 1, 2, ..., n. Jika tidak terdapat walk yang (k) (k) panjangnya k dari titik vi ke vj di D, maka ail = 0 sehingga ail aij = 0. Hal ini berakibat tidak terdapat walk yang panjangnya k + 1 dari titik vi ke vj melalui titik vl di D sehingga diperoleh banyaknya walk yang panjangnya k + 1 dari titik vi ke vj di D adalah (k)
(k)
(k)
ai1 a1j + ai2 a2j + ... + ain anj =
n X
akil alj
i=1
Universitas Sumatera Utara
13 karena Ak+1 = Ak A maka (k) aij
=
n X
akil alj
i=1
(k+1)
Sehingga aij
adalah benar menyatakan banyaknya walk dari titik vi ke titik vj
yang panjangnya k + 1 di D. Berikut adalah contoh menentukan eksponen suatu digraf dengan menggunakan proposisi 2.1. Contoh 2.4.2 Perhatikan Gambar 2.5(a). Matriks adjacency dari digraf pada Gambar 2.5(a) adalah sebagai berikut 0 0 A= 1 1
1 1 0
0 0 1 0 0 0 0 0 0
Berdasarkan Proposisi 2.4.2, banyaknya walk dari titik vi ke titik vj dengan panjang k dinyatakan oleh entri akij dari matriks Ak yang semuanya positif. Eksponen dari digraf D adalah bilangan positif terkecil k yang mengakibatkan matriks Ak positif. Perhatikan matriks berikut. 0 1 1 0 0 0 0 1 a. Untuk k = 1; diperoleh A1 = 1 0 0 0 1 0 0 0
Bukan eksponen dari digraf pada contoh 2.4.2, karena tidak terdapat walk dengan panjang 1 dari titik 1 ke titik 4, titik 2 ke titik 3, titik 3 ke titik 2,
titik 4 ke titik 3 dan titik 3 ke titik 4. 1 0 0 1 0 0 b. Untuk k = 2; diperoleh A2 = 0 1 1 0 1 1
1
0 0 0
Bukan eksponen dari digraf pada contoh 2.4.2, karena tidak terdapat walk
Universitas Sumatera Utara
14 dengan panjang 2 dari titik 1 ke titik 2, titik 1 ke titik 3, titik 2 ke titik 3, titik 2 ke titik 4 , titik 3 ke titik 4, dan titik 4 ke titik 1. 1 1 1 0 0 1 1 0 3 c. Untuk k = 3; diperoleh A = 1 0 0 1 1 0 0 1 Bukan eksponen dari digraf pada contoh 2.4.2, karena tidak terdapat walk dengan panjang 3 dari titik 1 ke titik 4, titik 2 ke titik 4, titik 3 ke titik 1,
titik 3 ke titik 2, titik 4 ke titik 2 1 1 d. Untuk k = 4; diperoleh A4 = 1 1
dan titik 4 ke titik 3. 1 1 1 0 0 1 1 1 0 1 1 0
Bukan eksponen dari digraf pada contoh 2.4.2, karena tidak terdapat walk
dengan panjang 4 dari titik 2 ke titik 3, dan titik 3 ke titik 4. 2 1 1 1 1 1 1 0 5 e. Untuk k = 5; diperoleh A = 1 1 1 1 1 1 1 1
Bukan eksponen dari digraf pada contoh 2.4.2, karena tidak terdapat walk dengan panjang 5 dari titik 2 ke titik 4. 2 2 2 1 1 1 1 1 6 f. Untuk k = 6; diperoleh A = 2 1 1 1 2 1 1 1
Karena terdapat walk dengan panjang 6 dari tiap pasang titik yang ada di D, maka eksponen dari digraf pada contoh 2.4.2 adalah exp(D) = 6.
2.4.3 Eksponen Digraf Dwi-warna Pada digraf dwi-warna D(2) , eksponen dari D(2) didefinisikan sebagai bilangan bulat positif terkecil s + t dari semua bilangan bulat tak negatif s dan t yang ada
Universitas Sumatera Utara
15 sehingga untuk setiap pasang titik u dan v di D(2) terdapat sebuah (s, t)-walk dari u ke v yang terdiri dari s-arc merah dan t-arc biru. Eksponen dari digraf dwiwarna D(2) dinotasikan oleh exp(D(2) ). Andaikan A dan B adalah matiks tak negatif orde m. Untuk bilangan tak negatif s dan t, didefinisikan (s, t)-Hurwitz product, (A, B)(s,t) dari A dan B adalah jumlah keseluruhan matriks dari hasil perkalian A sebanyak s kali dan B sebanyak t kali. Sebagai contoh, (A, B)(1,0) = A, (A, B)(0,1) = B, (A, B)(1,1) = AB + BA dan (A, B)(2,2) = A2B 2 + ABAB + AB 2A + BABA + B 2A2. Lemma 2.4.3 Jika (R,B) adalah matriks adjacency dari digraf dwi-warna D(2) , maka entri (i, j) dari (R, B)(s,t) adalah jumlah (s, t)-walk dari titik u ke v di D(2) . Bukti. Akan dibuktikan dengan induksi pada (s+t) dan (s+t+1), jika s = 0 maka (0,1) t = 1 atau jika s = 1 maka t ="0. Jika =B # s = 0 maka entri (i,j) dari (R, B) 0 adalah walk dengan komposisi di D(2) . Dengan cara yang sama, jika s = 1 1 (1,0) dan t = 0 maka (R, " B)# = R adalah walk dengan entri (i, j) menyatakan walk 1 dengan komposisi di D(2) . 0 0
Anggap Lemma 2.4.3 benar untuk semua bilangan bulat tak negatif s dan 0
0
0
t dengan s + t ≤ s + t, akan diperlihatkan untuk s + t + 1 juga benar dengan catatan sebagai berikut (R, B)(s+1,t) = R(R, B)(s,t) + B(R, B)(s+1,t−1) dengan induksi matematika entri (i, j) pada R(R, B)(s,t) adalah walk dari vi ke vj yang dimulai dengan arc merah diikuti oleh sebuah (s, t)-walk dan entri (i, j) pada B(R, B)(s+1,t−1) adalah jumlah walk dari vi ke vj yang dimulai dengan sebuah arc biru dan diikuti oleh sebuah (s + 1, t − 1)-walk sedemikian hingga entri (i, j) dari (R, B)(s+1,t) adalah jumlah (s + 1, t)-walk dari i ke j. Perhatikan contoh berikut. Contoh 2.4.3 Reprensentasi D(2) dengan 4 titik, 3 arc merah dan 2 arc biru
Universitas Sumatera Utara
16
Gambar 2.8 Digraf dwi-warna dengan 4 titik dan 5 arc Matriks adjacency merah dan biru 0 1 0 0 0 0 R= 1 0 0 1 0 0
dari Gambar 2.8 0 0 0 dan B = 0 0 0 0 0
adalah 0 1 0 0 0 0 0 0
0 1 0 0
Berdasarkan Lemma 2.4.3, banyaknya walk dari titik i ke titik j dengan panjang s + t adalah entri (i, j) dari (R, B)(s,t) yang semuanya bernilai positif, dan (s + t) terkecil dari yang demikian adalah eksponen dari matriks (R, B)(s,t). Perhatikan matriks (R, B)(s,t) Untuk s + t = 1, maka 0 1 0 0 1. (R, B)(1,0) = R = 1 0 1 0 0 0 0 0 2. (R, B)(0,1) = B = 0 0 0 0 Untuk s + t = 2, maka
0 0 1. (R, B)(2,0) = R2 = 0 0
berikut 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 1 0 0
Universitas Sumatera Utara
17 0 0 2. (R, B)(0,2) = B 2 = 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 3. (R, B)(1,1) = RB + BR = 0 0 0 0
dan seterusnya hingga diperoleh Untuk s + t = 12, maka 0 0 0 0 1. (R, B)(12,0) = R12 = 0 0 0 0 2.
3.
4.
5.
0 1 0 0 1 0 1 0
untuk s + t = 12, yaitu 0 0 0 0 0 0 0 0
0 0 0 0 0 0 (11,1) (10,1) 11 (R, B) = R(R, B) + BR 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (10,2) (9,2) (10,1) (R, B) = R(R, B) + B(R, B) = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (9,3) (8,3) (9,2) (R, B) = R(R, B) + B(R, B) = 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 (R, B)(8,4) = R(R, B)(7,4) + B(R, B)(8,3) = 4 5 0 1 4 5 0 1
0 0 = 0 0
Universitas Sumatera Utara
18 10 6 6. (R, B)(7,5) = R(R, B)(6,5) + B(R, B)(7,4) = 5 5
5 4 6 4 1 3 1 6 4 1 6 4
Karena terdapat walk dengan panjang 12 dari tiap pasang titik pada di-
(2) graf dwi-warna D(2) , maka eksponen dari"digraf # dwi-warna D pada Gambar 2.8 7 adalah exp(D2 ) = 12, dengan komposisi yang terdiri 7 arc merah dan 5 arc 5 biru.
2.5 Eksponen Titik Masuk Digraf dan Digraf Dwi-warna Pada subbab ini akan dibahas mengenai definisi eksponen titik masuk digraf D dan eksponen titik masuk digraf dwi-warna D(2) serta contoh bagaimana menentukan eksponen titik masuk dari digraf D dan digraf dwi-warna D(2) . 2.5.1 Eksponen Titik Masuk Digraf Misalkan D adalah sebuah digraf primitif atas n titik v1, v2, ..., vn. Untuk sebarang vi di D, i = 1, 2, ..., n, eksponen titik vi yang dinotasikan dengan expinD (vi ) adalah bilangan bulat positif terkecil k sedemikian hingga terdapat walk dengan panjang k dari setiap titik di ke titik vi di D, dan himpunan eksponen expD (X) adalah bilangan bulat positif terkecil p sehingga untuk setiap titik vj di D terdapat sebuah walk dari paling sedikit satu titik di X ke vj dengan panjang p. Andaikan D adalah digraf primitif orde n. Jika titik-titik di D adalah (v1, v2, ..., vn) sedemikian hingga expD (v1 ) ≤ expD (v2 ) ≤ · · · ≤ expD (vn ) maka expD (vk ) adalah tipe pertama generalisasi eksponen ke-k dari D, dinotasikan expD (vk ) (Brualdi dan Liu, 1990). Contoh 2.5.1 Perhatikan Gambar 2.5(a).
Universitas Sumatera Utara
19 Matriks adjacency dari digraf pada Gambar 2.5(a) adalah sebagai berikut 0 0 A= 1 1
1 1 0 0 0 1 0 0 0 0 0 0
Berdasarkan Proposisi 2.4, eksponen titik dari D diperoleh dengan melihat entri aij dari Ak , dengan entri pada kolom ke-i harus bernilai positif. Perhatikan matriks Ak berikut 1 1 1 1 1 0 0 1 4 a. Untuk k = 4; diperoleh A = 1 1 1 0 1 1 1 0 Karena kolom pertama bernilai positif, maka expinD (v1) = 4 2 1 1 1 1 1 1 0 5 b. Untuk k = 5; diperoleh A = 1 1 1 1 1 1 1 1 Kolom kedua dan kolom ketiga bernilai positif, maka expinD (v2) = expinD (v3) = 5. 2 2 2 1 1 1 1 1 c. Untuk k = 6; diperoleh A6 = 2 1 1 1 2 1 1 1 Kolom keempat bernilai postif, maka expinD (v4) = 6. Dengan demikian eksponen titik digraf pada Gambar 2.5(a), expinD (v1 ) = 4, expinD (v2) = expinD (v3) = 5, dan expinD (v4) = 6. 2.5.2 Eksponen Titik Masuk Digraf Dwi-warna Misalkan D(2) adalah digraf dwi-warna dengan V (D(2) ) adalah himpunan semua titik di D(2) , yaitu V (D(2) = {v1 , v2, · · · , vn }. Untuk sebarang titik vk ∈ V (D(2), maka eksponen titik vk di D(2) yang dinotasikan sebagai expinD(2) (vk ) adalah bilangan bulat positif terkecil r + b sedemikian hingga terdapat sebuah (r, b)-walk
Universitas Sumatera Utara
20 dari setiap titik di D(2) ke titik vk . Andaikan D(2) adalah digraf dwi-warna primitif orde n. Jika titik-titik di D(2) adalah (v1 , v2, ..., vn) sedemikian hingga expinD(2) (v1 ) ≤ expinD(2) (v2 ) ≤ · · · ≤ expinD(2) (vk ) maka expD(2) (vk ) adalah tipe pertama generalisasi eksponen titik ke-k dari digraf dwi-warna D(2) (Gao dan Shao, 2009). Untuk mencari eksponen titik digraf dwi-warna primitif D(2) , dapat dilakukan dengan operasi (s, t)-matriks Hurwitz Product R dan B yang dapat didefinisikan secara rekurensif. Untuk bilangan bulat tak negatif terkecil s dan t, jika k adalah adalah titik di D(2) , maka semua entri pada kolom ke-k dari matriks tersebut bernilai positif. Contoh 2.5.2 Perhatikan kembali digraf dwi-warna primitif pada Contoh 2.4.3. Berikut akan dicari eksponen titik masuk dari masing-masing titik pada digraf dwi-warna D(2) pada Gambar 2.8 dengan melihat entri (i, j) dari (R, B)(s,t) pada kolom ke-i bernilai positif. Menggunakan Contoh 2.4.3 telah diperoleh matriksmatriks (R, B)(s,t), maka
a. Untuk s+t = 5 dengan (R, B)
(3,2)
= R(R, B)
(2,2)
+B(R, B)
maka expin(v1) = 5 yang terdiri dari 3-arc merah dan 2-arc biru.
b. Untuk s+t = 6 dengan (R, B)
(4,2)
= R(R, B)
(3,2)
+B(R, B)
1 0 0 0 1 1 0 1 1 positif,
1 2 0 0
0 = 2 2 bernilai
(4,1)
Karena semua entri pada kolom kedua dengan (R, B)(4,2)
2 1 0 1
1 = 1 1 bernilai
(3,1)
Karena semua entri pada kolom pertama dengan (R, B)(3,2)
1 0 0 1 0 1 1 0 1 positif,
maka expin(v2) = 6 yang terdiri dari 4-arc merah dan 2-arc biru.
Universitas Sumatera Utara
21
1 0 2 1
1 c. Untuk s+t = 6 dengan (R, B)(3,3) = R(R, B)(2,3)+B(R, B)(3,2) = 0 0 (3,3) Karena semua entri pada kolom ketiga dengan (R, B) bernilai maka expin(v3) = 6 yang terdiri dari 3-arc merah dan 3-arc biru.
0 1 1 0 1 0 0 1 0 positif,
3 1 1 2
2 1 0 1 d. Untuk s+t = 7 dengan (R, B) = R(R, B) +B(R, B) = 1 0 2 1 1 0 2 1 (4,3) Karena semua entri pada kolom keempat dengan (R, B) bernilai positif, maka expin(v4) = 7 yang terdiri dari 4-arc merah dan 3-arc biru. (4,3)
(4,3)
(4,2)
2.6 Sistem Persamaan Diophantine Persamaan diophantine adalah suatu persamaan dalam bentuk a 1 x1 + a 2 x2 + · · · + a n xn = b
(1)
dengan solusi dari persamaan tersebut adalah bilangan bulat untuk semua bilangan bulat a1, a2 , ... , an , b. Andaikan bahwa n ≥ 1 dan koefisien-koefisien a1 , a2 ,..., an tak semuanya nol. Teorema 2.6.1 Persamaan (1) adalah punya solusi bulat jika dan hanya jika gcd(a1 , a2, ..., an) membagi b. Sistem persamaan diophantine adalah himpunan dari m persamaan diophantine dalam n variabel yang sama dengan m dan n adalah bilangan bulat positif seperti berikut a11x1 + a12x2 + · · · + a1n xn = b1 a21x1 + a22x2 + · · · + a2n xn = b2 .. .
(2)
am1x1 + am2x2 + · · · + amn xn = bm
Universitas Sumatera Utara
22
Sistem persamaan diophantine pada persamaan (2) dapat juga dituliskan sebagai sebuah persamaan matriks Ax = b, dimana
a11
a12
···
a1n
a21 a22 · · · a2n A= .. .. .. .. . . . . am1 am2 · · · amn
,
x=
x1 x2 .. . xn
,
b=
b1 b2 .. . bm
.
Kolom-kolom dari matriks A adalah koefisien-koefisien dari variabel x1 , x2 , ..., xn pada persamaan (2). Teorema 2.6.2 Sistem persamaan diophantine Ax = b dari persamaan (2) memiliki solusi bilangan bulat jika dan hanya jika pembagi persekutuan terbesar dari determinan submatriks 2 × 2 dari A adalah ±1. 2.7 Formula Eksponen Titik Masuk Digraf Dwi-warna Pada bagian akan dibahas cara menentukan batas bawah dan batas atas eksponen titik digraf dwi-warna primitif yang memuat dua cycle sebagaimana yang ditawarkan oleh Suwilo (2011). Terlebih dahulu akan dibahas mengenai teknik untuk menentukan batas bawah eksponen titik digraf dwi-warna primitif. Lemma 2.7.1 Andaikan D(2) adalah digraf dwi-warna primitif yang memuat dua " # r(C1 ) b(C2 ) cycle dengan matriks cycle M = . Misalkan vk adalah sembarang b(C1) r(C2 ) titik di D"(2) dan dari setiap titik# vj di D(2) ke titik vk # terdapat " #sebuah (s, " t)-walk # " r(pj,k ) s g g untuk sembarang bide-ngan =M , maka ≥ M −1 b(pj,k ) t h h langan bulat tak negatif g, h, dan untuk suatu path p(j,k) dari vj ke vk . Bukti Untuk sembarang 1 ≤ j ≤ n, misalkan pjk adalah path dari titik vj ke titik vk . D(2) memuat dua cycle sehingga setiap walk di D(2) dapat dituliskan seperti berikut.
Universitas Sumatera Utara
23
"
#
s t
=M
"
x1 x2
#
+
"
r(pj,k ) b(pj,k )
#
(3)
(2) dengan " # x1 , x"2 ≥# 0. Karena D primitif, maka M invertible. Menggunakan s g =M dan persamaan (3) diperoleh persamaan berikut t h
"
# " # x1 r(pj,k ) M =M + x2 b(pj,k ) " # " # " # x1 s r(pj,k ) M =M − x2 t b(pj,k ) " # # " # " r(p ) x1 s j,k ≥0 = − M −1 b(pj,k ) x2 t sehingga
"
s t
#
≥ M −1
"
s t
#
r(pj,k ) b(pj,k )
"
#
dan Lemma (2.7.1) terbukti.
Dari pembuktian Lemma 2.7.1 , maka diperoleh teorema berikut.
Teorema 2.7.1 Andaikan D(2) adalah digraf dwi-warna primitif yang terdiri dari cycle C1 dan C2 . Misalkan vk adalah titik di D(2) . Untuk sembarang titik vi dan vj di D(2) , didefinisikan " #gk = b(C " 2)r(p # j,k ) − r(C2 )b(pj,k ) dan hk = r(C1 )b(pj,k ) − s gk b(C1)r(pj,k ). Maka ≥M , sehingga expin(vk ) ≥ l(C1)gk + l(C2)hk . t hk Bukti. eksponen titik masuk vk dicapai oleh (s, t)-walk den" #Andaikan " bahwa # s g gan =M dan diperoleh persamaan berikut t h "
g h
#
≥ M −1
"
r(pj,k ) b(pj,k )
#
=
"
b(C2)r(pj,k ) − r(C2 )b(pj,k ) r(C1 )b(pj,k ) − b(C1)r(pj,k )
#
(4)
untuk sembarang path pj,k dari titik vj ke titik vk . Jika untuk sembarang titik vj , j = 1, 2, ..., n diperoleh nilai b(C2 )r(pj,k ) − r(C2 )b(pj,k ) ≥
Universitas Sumatera Utara
24 0, maka didefinisikan gk = b(C2 )r(pj,k ) − r(C2 )b(pj,k ) ≥ 0
(5)
dan jika untuk sembarang titik vi , dimana i = 1, 2, ..., n diperoleh nilai r(C1 )b(pi,k ) − b(C1)r(pi,k ) ≥ 0, maka didefinisikan hk = r(C1 )b(pi,k ) − b(C1)r(pi,k ) ≥ 0
(6)
sehingga g ≥ gk dan h ≥ hk . Oleh Lemma (2.6.1) diperoleh "
s t
#
=M
"
g h
#
≥M
"
gk hk
#
(7)
sehingga expin(vk ) = s + t ≥ (r(C1 ) + b(C1))gk + (r(C2 ) + b(C2 ))hk = l(C1)gk + l(C2)hk . Proposisi berikut dapat digunakan untuk menentukan batas bawah eksponen titik masuk digraf dwi-warna primitif dari sebuah titik yang ditentukan, misalkan titik v. Didefinisikan bahwa d(vk , v) adalah panjang walk terpendek dari vk ke v. Proposisi 2.7.1 Asumsikan D(2) adalah digraf dwi-warna primitif atas n titik. Mi-salkan v adalah sebuah titik di D(2) dengan expin(v). Untuk sembarang titik vk , k = 1, 2, ..., n di D(2) , expin(vk ) ≤ expin(v) + d(vk , v). Bukti. Untuk setiap k = 1, 2, ..., n misalkan pv,k adalah (r(pv,k ), b(pv,k ))-path dari v ke titik vk dengan panjang d(v, vk ). Karena eksponen titik masuk v adalah expin(v), maka terdapat (s, t)-walk dengan panjang expin(v) = s + t dari setiap titik vj , j = 1, 2, ..., n ke titik v. Ini menunjukkan bahwa setiap titik vk di D(2) terdapat suatu (s + r(pv,k ), t + b(pv,k ))-walk dari setiap titik v ke setiap titik vk . Walk tersebut ber-awal dari v menuju vk melalui (r(pv,k) , b(pv,k ))-path dan kemudian menuju vj melalui suatu (s, t)-walk dari vj ke v. Oleh karena itu diperoleh expin(vk ) ≤ expin(v) + d(v, vk ) Proposisi berikut digunakan untuk menentukan batas atas eksponen titik
Universitas Sumatera Utara
25 masuk digraf dwi-warna yang memuat dua cycle. Proposisi 2.7.2 Andaikan D(2) adalah digraf dwi-warna yang terdiri atas cycle C1 dan C2 . Misalkan vk adalah titik di D(2) yang terdapat pada cycle C1 dan cycle C2. Jika untuk setiap i = 1, 2, ..., n dan sembarang bilangan bulat positif s dan t, terdapat path pi,k dari vi ke vk sehingga sistem persamaan Mx +
"
r(pi,k ) b(pi,k )
#
=
"
s t
#
(8)
punya solusi bilangan bulat tak negatif, maka expin(vk ) ≤ s + t. Bukti. Misalkan bahwa solusi dari sistem persamaan (8) adalah x = (x1 , x2)T . Karena D(2) primitif, maka matriks cycle M invertible, sehingga x1 dan x2 tidak dapat nol kedua-duanya. Karena x1 , x2 6= 0 dan kedua cycle C1 dan C2 memuat titik vk , maka terdapat tiga kemungkinan berikut. Jika x1 > 0 dan x2 > 0, maka walk dari titik vi ke titik vk akan bergerak sebanyak x1 kali mengelilingi cycle C1 dan bergerak sebanyak x2 kali mengelilingi cycle C2 dan kembali lagi ke titik vi, kemudian terus bergerak menuju titik vk di sepanjang path pi,k adalah sebuah (s, t)-walk dari vi ke vk . Jika x1 = 0 dan x2 > 0, maka walk dari titik vi ke titik vk akan bergerak sebanyak x2 kali mengelilingi cycle C2 dan kembali lagi ke titik vi, kemudian terus bergerak menuju titik vk di sepanjang path pi,k adalah sebuah (s, t)-walk dari vi ke vk . Jika x1 > 0 dan x2 = 0, maka walk dari titik vi ke titik vk akan bergerak sebanyak x1 kali mengelilingi cycle C1 dan kembali lagi ke titik vi , kemudian terus bergerak menuju titik vk di sepanjang path pi,k adalah sebuah (s, t)-walk dari vi ke vk . Dengan demikian, untuk setiap titik vi , i = 1, 2, ..., n terdapat sebuah (s, t)-walk dari vi ke vk , sehingga expin(vk ) ≤ s + t.
Universitas Sumatera Utara
