6 BAB 2 DIGRAF PRIMITIF
Pada bagian ini, peneliti akan menjelaskan bahwa digraf k Dn merupakan sebuah digraf primitif. Penjelasan tersebut diperkuat dengan memaparkan beberapa definisi digraf dan beberapa unsur-unsur lainnya. Lalu dilanjutkan dengan penjelasan digraf dikatakan primitif, Definisi dari pembagi persekutuan terbesar, dan pemaparan dari m-kompetisi indeks. 2.1 Definisi Digraf Digraf D adalah sebuah objek yang terdiri atas sebuah himpunan V (D) berjumlah n buah dan tak kosong yang unsur-unsurnya merupakan semua titik vi untuk i = 1, 2, 3, · · · , n di digraf D dan sebuah himpunan A(D) yaitu sebuah pasangan berurut V × V yang terdiri atas semua unsur (vi , vj ) dimana vi ∈ V dan vj ∈ V . Sehingga secara umum, digraf merupakan sebuah objek yang tersusun atas elemen-elemen titik yang tidak kosong dimana setiap titik dapat dihubungkan oleh sebuah penghubung berarah yang dinamakan busur. Sebagai contoh, gambar 2.1 akan menjadi ilustrasi pendukung untuk memahami pengertian dari digraf D. diberikan sebuah digraf D seperti pada gambar 2.1
Gambar 2.1. Contoh digraf D
Universitas Sumatera Utara
7 Maka digraf D terdiri atas himpunan V (D) = {v1 , v2 , v3 , v4 } dan himpunan A(D) = {(v1 , v1 ), (v1 , v2 ), (v2 , v3 ), (v3 , v1 ), (v3 , v4 ), (v4 , v1 )}. Terdapat beberapa istilah penting yang mendukung dalam penelitian ini, a. Jika v ∈ V (D) maka himpunan k-step out-neighborhood dari titik v didefink isikan sebagai N + (Dk : v) = {x ∈ V (G) : v → x} atau semua titik tujuan dari titik v di D dengan panjang jalan k. Seperti pada contoh diatas, perhatikan titik v1 , N + (D : v1 ) = {v1 , v2 } , N + (D2 : v1 ) = {v1 , v2 , v3 }, N + (D3 : v1 ) = {v1 , v2 , v3 , v4 } . b. Jalan pada digraf D merupakan sebuah barisan antara busur di D dinotasikan dengan W tersusun atas barisan (u, v1 ), (v1 , v2 ), · · · , (vn−1 , vn ), (vn , v). biasanya penulisan pada barisan Wuv dapat diilustrasikan dengan u → v1 → v2 → v3 → · · · → vn → v dan panjang dari jalan Wuv dinotasikan dengan ord(Wuv ). Seperti pada contoh diatas, beberapa jalan untuk titik asal adalah v2 dan titik tujuan v1 yaitu (1) Wv2 ,v1 : v2 → v3 → v1 , (2) Wv2 ,v1 : v2 → v3 → v4 → v1 , (3) Wv2 ,v1 : v2 → v3 → v4 → v1 → v1 → v1 . Perhatikan bahwa banyaknya jalan dengan titik asal v2 dan titik tujuan v1 dapat lebih dari satu selama ada busur yang menghubungkan setiap titik yang dikehendaki. Untuk jalan pada poin 1, panjangnya adalah ord(Wv2 ,v1 ) = 2, panjang jalan pada poin 2 adalah ord(Wv2 ,v1 ) = 3, dan panjang jalan pada poin 3 adalah ord(Wv2 ,v1 ) = 5 c. Lintasan pada digraf D merupakan sebuah jalan tanpa perulangan titik dinotasikan dengan P . Pada dasarnya jalan di digraf D tidak memperhatikan adanya perulangan titik pada busurnya, tetapi pada lintasan sebuah barisan busur tidak memperbolehkan adanya perulangan titik pada titik asal hingga titik tujuan. Perhatikan contoh jalan pada bagian c, jalan pada poin 1 dan poin 2 merupakan sebuah lintasan tetapi jalan pada poin 3 bukan merupakan lintasan. d. Lingkaran pada digraf D merupakan sebuah lintasan tertutup yang tersusun atas barisan (u, v1 ), (v1 , v2 ), · · · , (vn−1 , vn ), (vn , u). Perhatikan contoh pada gambar 2.1, Wv1 v1 : v1 → v2 → v3 → v1 merupakan lingkaran pada digraf D.
Universitas Sumatera Utara
8 e. Lingkaran Hamiltonian pada digraf D merupakan sebuah lintasan tertutup dimana lintasan tersebut melalui semua titik yang ada di D. Pada gambar 2.1, Wv1 ,v1 : v1 → v2 → v3 → v4 → v1 . f. Loop pada digraf D merupakan sebuah lintasan tertutup dengan panjang 1. Pada gambar 2.1, Wv1 ,v1 : v1 → v1 merupakan loop. g. jarak antara 2 buah titik u dan w di D adalah panjang jalan terpendek yang bisa ditempuh oleh titik awal u ke titik tujuan w yang dinotasikan dengan d(u, w). h. Girth pada sebuah digraf D adalah panjang dari sebuah lingkaran terpendek dari semua lingkaran di D. Maka, sebuah digraf D yang memiliki loop mempunyai girth sebesar 1. Sebuah digraf dapat direpresentasikan ke dalam sebuah matriks ketetanggan dengan definisi matriks bujursangkar A = (aij ) dengan besar ordo A merupakan banyak titik pada digraf D yang setiap entri pada matriks A adalah
aij =
1,
bila (i, j) ∈ A(D)
0,
bila (i, j) ∈ / A(D)
berdasarkan definisi digraf, tidak ada jaminan bahwa aij = aji untuk semua 1 ≤ i, j ≤ n. Ini mengakibatkan bahwa representasi matriks ketetanggaan di digraf D bukan merupakan matriks simetris. Perhatikan digraf pada contoh 5, Representasi matriks ketetanggaan untuk digraf pada gambar 2.1 adalah 1 0 A= 1 1
1 0 0 0
0 1 0 0
0 0 1 0
Sebuah matriks A dikatakan non negatif jika semua entri (aij ) ≥ 0 dan sebuah matriks A dikatakan positif jika semua entri (aij ) ≥ 1. Matriks A pada gambar
Universitas Sumatera Utara
9 2.1 merupakan matriks non negatif. untuk matriks A5 yaitu, 6 3 A5 = 6 4
4 2 3 2
2 2 2 1
1 1 2 1
merupakan matriks positif, karena tidak ada entri pada matriks A5 yang bernilai 0. Selanjutnya pengertian dari sebuah digraf yang dikatakan terhubung kuat. Sebuah digraf D dikatakan terhubung kuat jika dan hanya jika setiap pasang u, v ∈ V (D), terdapat sebuah lintasan berarah dari titik u ke v dan dari titik v ke u. Perhatikan contoh gambar 2.2 berikut,
Gambar 2.2 : Digraf 1 D4
Dengan memperhatikan setiap pasang (v1 , v2 ), (v1 , v3 ), (v1 , v4 ), (v2 , v3 ), (v2 , v4 ), dan (v3 , v4 ), untuk a. pasangan titik (v1 , v2 ) terdapat sebuah lintasan yaitu Pv1 ,v2 : v1 → v2 dan Pv2 ,v1 : v2 → v3 → v4 → v1 b. pasangan titik (v1 , v3 ) terdapat sebuah lintasan yaitu Pv1 ,v3 : v1 → v2 → v3 dan Pv3 ,v1 : v3 → v4 → v1 c. pasangan titik (v1 , v4 ) terdapat sebuah lintasan yaitu Pv1 ,v4 : v1 → v2 → v3 → v4 dan Pv4 ,v1 : v4 → v1 d. pasangan titik (v2 , v3 ) terdapat sebuah lintasan yaitu Pv2 ,v3 : v2 → v3 dan Pv3 ,v2 : v3 → v4 → v1 → v2
Universitas Sumatera Utara
10 e. pasangan titik (v1 , v3 ) terdapat sebuah lintasan yaitu Pv2 ,v4 : v2 → v3 → v4 dan Pv4 ,v2 : v4 → v1 → v2 f. pasangan titik (v1 , v3 ) terdapat sebuah lintasan yaitu Pv3 ,v4 : v1 → v3 → v4 dan Pv4 ,v3 : v4 → v1 → v2 → v3 Karena setiap pasang (vi , vj ) di digraf Dv1 memenuhi definisi dari terhubung kuat, maka digraf Dv1 merupakan sebuah digraf yang terhubung kuat. Teorema 2.1 : Andaikan sebuah digraf D dengan n titik v1 , v2 , · · · , dan vn , setiap titik di D terletak dalam sebuah lingkaran jika dan hanya jika digraf D terhubung kuat Bukti. Diberikan sebuah digraf D dengan n titik v1 , v2 , · · · , dan vn . Perhatikan karena semua titik vi di D untuk i = 1, 2, · · · , n berada di sebuah lingkaran, maka dapat dibentuk sebuah jalan dimisalkan dengan Wv1 ,v1 : v1 → v2 → v3 → · · · → vn → v1 . Didapat bahwa untuk sembarang pasangan vi , vj di D, maka didapat lingkaran dengan jalan yaitu Wvi ,vi dan Wvj ,vj . Karena Wvi ,vi dan Wvj ,vj ada, maka pasti terdapat sebuah jalan dari vi ke vj dengan memanfaatkan lingkaran Wvi ,vi dan sebuah jalan dari vj ke vi dengan memanfaatkan lingkaran Wvj ,vj . Sehingga karena setiap pasang titik vi , vj di D mempunyai jalan dari titik vi ke vj dan dari titik vj ke vi maka digraf D terhubung kuat. Akan dibentuk lingkaran dengan setiap titik di D terletak didalamnya. Karena D terhubung kuat, maka setiap pasang titik (u, v) di D, terdapat sebuah jalan berarah sederhana dari u ke v dan dari v ke u. Sehingga dengan menghubungkan jalan berarah pada jalan Wu,v dengan Wv,u maka akan terbentuk sebuah lingkaran Wu,u yang memuat seluruh titik di D. Ini merupakan akhir dari pembuktian pada teorema ini. 2.2 Definisi digraf Primitif Sebuah digraf D dikatakan primitif jika terdapat sebuah jalan berarah dengan panjang tepat k dari setiap titik u ke setiap titik v. Nilai terkecil dari k merupakan eksponen dari digraf D dinotasikan dengan exp(D) (Akelbek dan Kirkland, 2008). Sebagai contoh, perhatikan kembali gambar 2.2. Digraf D pada gambar 2.2
Universitas Sumatera Utara
11 merupakan sebuah digraf primitif karena setiap pasangan titik (vi , vj ) di D mempunyai jalan dengan panjang yang sama dengan panjang jalan terpendek adalah 6. Sebuah digraf D dikatakan primitif jika dan hanya jika D adalah terhubung kuat dan pembagian persekutuan terkecil untuk setiap lingkaran di D adalah 1 (Shao et al, 2012). Proposisi 2.2 : (Akelbek dan Kirkland, 2008) Andaikan D merupakan sebuah digraf primitif dengan n titik dan s merupaka girth pada D. Maka exp(D) ≤ n + s(n − 2). Proposisi 2.3: Andaikan D merupakan sebuah digraf primitif dengan n titik dan memiliki loop didalamnya. Maka exp(D) ≤ 2n − 2 Bukti. Dengan menggunakan proposisi 2.2. Diketahui bahwa loop merupakan lingkaran terpendek di D sehingga girth pada D adalah 1. Maka dengan mensubtitusikan s = 1 ke pertidaksamaan di proposisi 2 didapat exp(D) ≤ 2n − 2 2.3 Digraf s Dn Sebagai Digraf Primitif Setelah beberapa pemaparan tentang bagaimana cara sebuah digraf dikatakan primitif maka akan dibuktikan bahwa digraf s Dn merupakan sebuah digraf primitif. Didefinisikan bahwa digraf s Dn adalah digraf dengan lingkaran Hamiltonian dimana terdapat s buah loop yang diletakkan saling berdekatan. Sehingga, Akibat 2.7 Jika k merupakan banyak loop yang diletakkan berdekatan dan n merupakan banyak titik di s Dn Maka s Dn merupakan digraf primitif. Bukti. Untuk membuktikan bahwa s Dn merupakan digraf primitif hanya perlu dibuktikan bahwa s Dn merupakan digraf yang terhubung kuat dan semua panjang setiap lingkaran pada s Dn saling relatif prima. Berdasarkan teorema 2.1 digraf s Dn merupakan digraf yang terhubung kuat. Perhatikan bahwa semua lingkaran yang dimiliki digraf s Dn adalah v1 → v1 , v2 → v2 , v3 → v3 , · · · , vi → vi dan v1 → v2 → v3 → · · · → vn → v1 dengan masing masing panjang adalah 1 dan n. Karena GCD(n, 1) = 1 untuk setiap n bilangan bulat positif maka telah terbukti bahwa s Dn merupakan digraf primitif.
Universitas Sumatera Utara
12
2.4 Definisi M -Kompetisi Indeks Definisi 2.8 : Untuk bilangan bulat positif m dan n dengan 1 ≤ m ≤ n, didefinisikan m-kompetisi indeks dari sebuah digraf primitif D, dinotasikan dengan km (D) adalah bilangan bulat positif terkecil k sehingga untuk setiap pasang k x dan y, terdapat m titik berbeda yaitu v1 , v2 , v3 , · · · , vm sehingga x → vi dan k y → vi , dalam artian ada jalan Wxvi dan Wyvi dengan panjang yang sama untuk setiap i = 1, 2, · · · , m. Sebelum memasuki contoh, diperkenalkan terlebih dahulu beberapa definisi pembantu dalam pengerjaan m-kompetisi indeks. Definisi 2.9 : Misalkan D merupakan sebuah digraf primitif. Indeks m-kompetisi lokal pada sebuah titik x dan y di D adalah panjang jalan terpendek k untuk sebuah pasangan titik (x, y) sehingga terdapat m titik berbeda v1 , v2 , v3 , · · · , vm dari x → vt dan y → vt untuk t = 1, 2, 3, · · · , m, dinotasikan dengan k
k
km (D : x, y) = min{k|x → vt dan y → vt , t ≥ k} Maka dari definisi 2.9, nilai dari m-kompetisi indeks km (D) dari digraf D adalah km (D) = max km (D : x, y) x,y∈V (D)
sehingga dari definisi 2.8, untuk setiap m = 1, 2, 3, · · · , n didapat km (D : x, y) ≤ km (D) Definisi 2.10 : k-step common out-neighborhood titik x dan y adalah semua himpunan titik vt di D terdiri atas n buah titik yang bisa dikunjungi dengan panjang k k jalan k yaitu x → vt dan y → vt untuk t = 1, 2, 3, · · · ,n yang dinotasikan dengan k k N + (Dk : x, y) = {vt ∈ V (D)|x → vt dan y → vt }. Proposisi 2.11 : (Shao et al, 2012) untuk 1 ≤ m ≤ n, Andaikan D merupakan digraf primitif dengan n titik , 1 ≤ m ≤ n, dan exp(D) merupakan eksponensial
Universitas Sumatera Utara
13 dari D. Maka, k(D) = k1 (D) ≤ k2 (D) ≤ k3 (D) ≤ · · · ≤ kn (D) = exp(D) Akibatnya scrambling index merupakan 1-kompetisi indeks dari sebuah digraf D dan n-kompetisi indeks merupakan eksponen dari digraf D. Sebagai contoh perhatikan kembali gambar 2.2. Untuk mendapatkan nilai dari m-kompetisi indeks dari digraf tersebut terlebih dahulu dicari nilai m-kompetisi indeks lokalnya dan untuk mendapatkan m-kompetisi indeksnya, diambil nilai m-kompetisi lokal terbesar. Maka, a. Untuk 1-kompetisi indeks didapat, v1
v2
v3
v4
min(km (vi , vj ))
k1 (v1 , v2 ) =
3
4
5
6
3
k1 (v1 , v3 ) =
2
3
4
5
2
k1 (v1 , v4 ) =
1
2
3
4
1
k1 (v2 , v3 ) =
3
4
5
6
3
k1 (v2 , v4 ) =
3
4
5
6
3
k1 (v3 , v4 ) =
2
3
4
5
2
Sehingga, k(D) = max{3, 2, 1, 3, 3, 2} = 3.
b. Untuk 2-kompetisi indeks didapat, (v1 , v2 ) (v1 , v3 ) (v1 , v4 ) (v2 , v3 ) (v2 , v4 ) (v3 , v4 ) (km (vi , vj )) k1 (v1 , v2 ) =
4
5
6
4
4
5
4
k1 (v1 , v3 ) =
3
4
5
4
5
4
3
k1 (v1 , v4 ) =
2
3
4
3
4
4
2
k1 (v2 , v3 ) =
4
5
6
4
4
5
4
k1 (v2 , v4 ) =
4
5
6
4
4
5
4
k1 (v3 , v4 ) =
3
4
5
4
5
4
3
Universitas Sumatera Utara
14 Sehingga, k2 (D) = max{4, 3, 2, 4, 4, 3} = 4 c. Untuk 3-kompetisi indeks didapat, (v1 , v2 .v3 )
(v1 , v3 , v4 )
(v2 , v3 , v4 )
(v1 , v2 , v4 ) (km (vi , vj ))k1 (v1 , v2 ) =
k1 (v1 , v3 ) =
4
5
5
5
4
k1 (v1 , v4 ) =
3
4
4
4
5
k1 (v2 , v3 ) =
5
6
6
6
5
k1 (v2 , v4 ) =
5
6
6
6
5
k1 (v3 , v4 ) =
4
5
5
5
4
Sehingga, k3 (D) = max{5, 4, 3, 5, 5, 4} = 5. d. Untuk 4-kompetisi indeks didapat, (v1 , v2 .v3 , v4 )
(km (vi , vj ))
k1 (v1 , v2 ) =
6
6
k1 (v1 , v3 ) =
5
5
k1 (v1 , v4 ) =
4
4
k1 (v2 , v3 ) =
6
6
k1 (v2 , v4 ) =
6
6
k1 (v3 , v4 ) =
6
5
Sehingga, k4 (D) = max{6, 5, 4, 6, 6, 5} = 6. Ini merupakan akhir dari tinjauan pustaka pada penelitian ini.
2.5 Batas Atas M -Kompetisi Indeks Digraf Primitif. Pada umumnya, pembuktian rumus umum m-kompetisi indeks digraf primitif dilakukan dengan membuktikan batas atas dan batas bawah rumusnya. Tetapi, karena keterbatasan waktu, peniliti hanya membuktikan batas atas dari rumus umum m-kompetisi indeks dari digraf primitif. Setiap jalan berarah pada suatu digraf s Dn dapat diuraikan menjadi sebuah lin-
Universitas Sumatera Utara
5
15 tasan berarah, jalan yang mengililingi lingkaran, dan jalan yang mengelilingi loop. Untuk membuktikan batas atas km (s Dn ) ≤ f (m, n, s) cukup dibuktikan bahwa untuk setiap pasangan titik (vi , vj ) di s Dn terdapat sebuah jalan dengan panjang f (m, n, s) dari titik vi ke masing-masing titik vt , t = 1, 2, 3, · · · , vm dan dari titik vj ke masing-masing titik vt , t = 1, 2, 3, · · · , vm . Dengan menggunakan gambar 2.2 sebagai contoh, akan dibuktikan masing-masing batas atas dari digraf 1 D4 . 1. Untuk k1 (1 D4 ) ≤ 4. Cukup dengan membuktikan bahwa setiap titik v1 , v2 , v3 dan v4 ada jalan dengan panjang 4 ke titik v1 . Sehingga setiap titik v1 , v2 , v3 dan v4 dengan menggunakan jalan yaitu : a. v1 → v1 → v1 → v1 b. v2 → v3 → v4 → v1 c. v3 → v4 → v1 → v1 d. v4 → v1 → v1 → v1 ada jalan dengan panjang 4 ke titik v1 . 2. Untuk k2 (1 D4 ) ≤ 5. Cukup dengan membuktikan bahwa setiap titik v1 , v2 , v3 dan v4 ada jalan dengan panjang 5 ke titik v1 dan v2 . Sehingga setiap titik v1 , v2 , v3 dan v4 dengan menggunakan jalan yaitu : a. v1 → v1 → v1 → v1 → v1 v1 → v1 → v1 → v1 → v2 b. v2 → v3 → v4 → v1 → v1 v2 → v3 → v4 → v1 → v2 c. v3 → v4 → v1 → v1 → v1 v3 → v4 → v1 → v1 → v2 d. v4 → v1 → v1 → v1 → v1 v4 → v1 → v1 → v1 → v2 ada jalan dengan panjang 5 ke titik v1 dan v2 .
Universitas Sumatera Utara
16 3. Untuk k3 (1 D4 ) ≤ 6. Cukup dengan membuktikan bahwa setiap titik v1 , v2 , v3 dan v4 ada jalan dengan panjang 5 ke titik v1 , v2 dan v3 . Sehingga setiap titik v1 , v2 , v3 dan v4 dengan menggunakan jalan yaitu : a. v1 → v1 → v1 → v1 → v1 → v1 v1 → v1 → v1 → v1 → v1 → v2 v1 → v1 → v1 → v1 → v2 → v3 b. v2 → v3 → v4 → v1 → v1 → v1 v2 → v3 → v4 → v1 → v1 → v2 v2 → v3 → v4 → v1 → v2 → v3 c. v3 → v4 → v1 → v1 → v1 → v1 v3 → v4 → v1 → v1 → v1 → v2 v3 → v4 → v1 → v1 → v2 → v3 d. v4 → v1 → v1 → v1 → v1 → v1 v4 → v1 → v1 → v1 → v1 → v2 v4 → v1 → v1 → v1 → v2 → v3 ada jalan dengan panjang 6 ke titik v1 , v2 dan v3 . 4. Untuk k4 (1 D4 ) ≤ 6. Cukup dengan membuktikan bahwa setiap titik v1 , v2 , v3 dan v4 ada jalan dengan panjang 5 ke titik v1 , v2 , v3 dan v4 . Sehingga setiap titik v1 , v2 , v3 dan v4 dengan menggunakan jalan yaitu : a. v1 v1 v1 v1
→ v1 → v1 → v1 → v1
→ v1 → v1 → v1 → v1
→ v1 → v1 → v1 → v1
→ v1 → v1 → v1 → v2
→ v1 → v1 → v2 → v3
→ v1 → v2 → v3 → v4
b. v2 v2 v2 v2
→ v3 → v3 → v3 → v3
→ v4 → v4 → v4 → v4
→ v1 → v1 → v1 → v1
→ v1 → v1 → v1 → v2
→ v1 → v1 → v2 → v3
→ v1 → v2 → v3 → v4
c. v3 → v4 → v1 → v1 → v1 → v1 → v1 v3 → v4 → v1 → v1 → v1 → v1 → v2
Universitas Sumatera Utara
17 v3 → v4 → v1 → v1 → v1 → v2 → v3 v3 → v4 → v1 → v1 → v2 → v3 → v4 d. v4 v4 v4 v4
→ v1 → v1 → v1 → v1
→ v1 → v1 → v1 → v1
→ v1 → v1 → v1 → v1
→ v1 → v1 → v1 → v2
→ v1 → v1 → v2 → v3
→ v1 → v2 → v3 → v4
ada jalan dengan panjang 6 ke titik v1 , v2 , v3 dan v4 . Ini merupakan akhir dari bab 2.
Universitas Sumatera Utara
