Minggu Ke XIV 14.1 Uraian dan Contoh Suatu graf berarah (directed graph) D atau digraph terdiri dari dua komponen : (i) Himpunan V yang elemen-elemennya disebut titik-titik, (ii) Himpunan A dari pasangan-pasangan berurutan titik-titik yang disebut arc. Akan ditunjukkan digraf (digraph) dengan D (V, A) apabila diinginkan untuk menekankan dua bagian dari D. Juga digambarkan digraf dengan diagram-diagram dalam bidang datar. Lagi tiap titik v dalam V diwakili oleh suatu dot (atau lingkaran kecil); tetapi tiap arc a = (u, v) dinyatakan dengan suatu arrow, yaitu kurva berarah dari titik asal u ke titik akhir v. Suatu contoh gambar 2 – 2 menyatakan digraf D (V, A) di mana (i) V terdiri dari empat titik A, B, C, D, dan (ii) A terdiri dari tujuh arc : A1 =
, a2 = , a3 = , a4 = , a5 = , a6 = , a7 = . Arc a, disebut loop karena titik asal B sama dengan titik akhirnya. Arc a2 dan a3 disebut arc-arc yang paralel, karena mereka mempunyai titik asal yang sama B dan titik akhir yang sama A. Biasanya menunjukkan digraf dengan menarik diagramnya daripada mendaftar titik-titik dan arc-arcnya. Jika arc-arc dan/atau titik-titik dari suatu digraf dibubuhi label dengan suatu macam data, maka dikatakan digraf berlebel (labeled directed graph). Graf demikian seringkali digunakan untuk menggambar situasi-situasi dinamis. Untuk contoh, andaikan tiga anak A, B, C sedang melemparkan bola ke tiap yang lain sedemikian sehingga A selalu melempar bola-bola itu ke B, tetapi B dan C baru melempar bola itu ke A sebagaimana mereka sedang melempar kepada tiap yang lain. Gambar 14.3 mengilustrasikan situasi dinamis ini, di mana arc-arc dibubuhi label dengan probalitas masing-masing, yaitu A melempar bola ke B dengan probalitas 1, B melempar bola ke A dan C masing-masing dengan probalitas ½. A
½
½ ½
B
C
Gambar 14.1
77
Misal D (V, A) suatu digraf. Dikatakan D (V, A) adalah berhingga jika himpunan V dari titik-titiknya adalah berhingga dan himpunan A dari arc-arcnya adalah berhingga. Misal V himpunan bagian dari V dan A’ himpunan bagian dari a yang titik-titik asal titiktitik akhirnya kepunyaan V’. Maka D (V’, A’) adalah suatu digraf dan disebut graf bagian dari D (V, A). Jika A’ memuat semua arc dari A yang titik-titik asal dan titik-titik akhirnya kepunyaan V’, maka D (V’, A’) disebut graf bagian yang dibangun oleh V’. Suatu contoh, pandang digraf Gambar 14.2 a1
v2
D (V, A) = a3
v1 a6
a4
a2
a7
v3
v4
Gambar 14.2 Titik µ. Semiwalk adalah sama sebagaimana walk tetapi arc ai boleh mulai pada vi-1 atau vi dan berakhir pada titik yang lain. Semitrail dan semipath mempunyai definisi yang analog. So .. Suatu contoh, panjang digraf dalam Gambar 14.2 w1 = (v3, a2, v2, a1, v1) adalah suatu walk w2 = (v4, a5, v3, a4, v1, a6, v4, a5, v3) adalah suatu walk. Panjang w1 = 2, panjang w2 = 4. w3 = (v3, a2, v2, a1, v1, a6, v4) adalah suatu walk tertutup w2 = (v4, a5, v3, a3, v2, a1, v1, a6, v4, a7, v3) adalah suatu trail. P1 = (v1, a4, v3, a3, v2) adalah suatu path. C1 = (v1, a4, v3, a2, v2, a1, v1) adalah suatu cycle. WS = (v1, a4, v3, a2, v2, a3, v3) adalah suatu semiwalk. W6 = (v1, a1, v2, a3, v3, a4, v1, a4, v3, a2, v2) adalah suatu semiwalk. Ada tiga macam konektivitas dalam digraf D. Dikatakan bahwa D terhubung lemah (weakly connected) atau weak jika ada suatu semipath di antara sebarang dua titik µ dan v dari D. Dikatakan bahwa D terhubung unilateral (unilaterally connected) atau unilateral jika untuk sebarang dua titik µ dan v dari D ataukah µ, dapat dicapai dari v ataukah v dapat dicapai dari µ, yaitu ada path dari satu dari mereka ke titik yang lain. Dikatakan D adalah terhubung kuat (strongly connected) atau strong jika untuk sebarang dua titik µ dan v dari D, maka µ dapat dicapai dari v dan v dapat dicapai dari µ. Perhatikan bahwa berhubung kuat mengakibatkan terhubung unilateral, dan bahwa terhubung unilateral mengakibatkan terhubung lemah. (atau: D = terhubung D = terhubung unilateral D = terhubung lemah).
78
Dikatakan bahwa D adalah strictly unilateral jika ia unilateral tetapi tidak strong, dan dikatakan D adalah strictly weak jika ia adalah weak tetapi tidak unilateral. Dalam gambar 14.4 (a) adalah strictly weak (b) adalah strictly unilateral dan (c) adalah strong.
(a)
(b) Gambar 14.4 Perhatikan lagi gambar 14.5 sebagai contoh : a) adalah strongly b) adalah unilateral c) adalah weak d) adalah strictly unilateral e) adalah strictly weak.
(a)
(d)
(b)
(c)
(c)
(e) Gambar 14.5
Konektivitas dapat dikarakteristikkan menggunakan spanning walk sebagai berikut : Teorema 1 : Misal D suatu digraf berhingga. Maka (a) D adalah weak jika dan hanya jika D mempunyai suatu spanning semiwalk. (b) D adalah unilateral jika dan hanya jika D mempunyai suatu spanning walk (c) D adalah strong jika dan hanya jika D mempunyai suatu spanning walk tertutup.
79
Perhatikan Gambar 14.6 (a) adalah weak sebab ada suatu spanning semiwalk yaitu (A, B, C, D, E). (b) adalah unilateral sebab ada suatu spanning walk yaitu (A, B, C, D, E). (c) adalah strong sebab ada suatu spanning walk tertutup yaitu (A, B, C, D, E, A). C
D
C
D
B
A
B
A
(a)
(b) C
D
D
B
A
(c) Gambar 14.6 Digraf dengan source dan sink tampak dalam banyak kegunaan yaitu diagramdiagram alir). Suatu syarat cukup adanya source dan sink adalah terdapat dalam teorema berikut ini : Teorema 14.2 : Jika digraf berhingga D tidak memuat cycle berarah (directed cycles), maka D mempunyai suatu source dan sink. Bukti : Karena D berhingga maka pasti ada path dengan panjang maksimum, misal P = (v0, v1, …, vn). Maka titik akhir vn pasti merupakan suatu sink, sebab jika tidak sama suatu arc(vn, µ) akan ataukah memperpanjang P ataukah membentuk suatu cycle berarah (yaitu jika µ = vi untuk suatu indeks i). Hal ini bertentangan dengan sifat D tanpa cycle berarah dan P maksimum. Secara sama, titik pertama v0 pasti merupakan suatu source. Sekarang misal D adalah suatu graf berarah dengan titik-titik v1, v2, v3,…, vm. Matriks ajasensi (adjacency matrix) dari D adalah matriks MD = (mij) di mana mij = banyak arc yang mulai pada vi dan berakhir pada vj.
80
Jika D tidak mempunyai arc-arc paralel, maka elemen-elemen MD hanyalah nol atau satu, jika tidak, elemen-elemen MD akan menjadi bilanganbilangan bulat non negatif. Sebaliknya, setiap matriks M bertipe m x m dengan elemen-elemen bilanganbilangan bulat non negatif secara tunggal menentukan suatu digraf dengan m titik. Suatu contoh, perhatikan digraf dalam Gambar 14.7 dan matriks ajasensi M untuk digraf tersebut. v1
v4 0 1 0 0
M=
0 1 0 0 0 0 0 1 2 0 1 0
v2
v3
Gambar 14.7 Suatu contoh, kebalikannya, perhatikan matriks M dan digraf D yang ditentukan oleh matriks M, gambar 14.8. 2 1 0 1 1
1 0 3 1 0 M=
1 1 2 0 2 3 1 2 0 0 0 1 0 1 0
v3
v2
v4
v1
Gambar 14.8
81
14.2 Latihan Sekarang cobalah anda kerjakan semua soal latihan berikut ini. Jika anda mengalami kesulitan, lihatlah petunjuk penyelesaian yang terdapat pada bagian akhir latihan ini. 1) Pertimbangan digraf D yang digambar dalam gambar 14.9. a. Hitung banyak path dari x ke z ! b. Hitung banyak path dari x ke z ! c. Adakah Source atau sink, kalau ada tunjukkan ! d. Tentukan matriks ajasensi MD digraf D ! e. Tunjukkan D terhubung lemah, terhubung unilateral, terhubung kuat atau tidak ketiga-tiganya ! x
y
z
w Gambar 14.9
2) Pertimbangan digraf D yang digambar dalam gambar 14.10. a. Adakah source, sink, kalau ada tunjukkan ! b. Tunjukkan D terhubung lemah, terhubung unilateral atau terhubung kuat, dan jelaskan ! c. Tentukan matriks MD !. x
y
z
w Gambar 14.10
Jawaban : (1) a. ada tiga path dari x ke z : b. Hanya ada satu path dari y ke z : (y, y, z) c. x adalah source, karena ia bukan titik berhenti untuk sebarang garis berarah, yaitu indegree-nya adalah nol. Tidak sink, karena setiap titik mempunyai outdegree yang bukan nol, yaitu tiap titik merupakan titik asal suatu garis berarah (arc).
82
0 1 1 1
d. MD :
0 0 0 1 0 1 0 1
0 0 1 0 e. Digraf D bukan terhubung kuat, karena x adalah source yang berarti tidak ada path dari sebarang titik yang lain, katakan dari y ke x. D adalah terhubung unilateral, karena path (x, y, w, z) melalui semua titik, sehingga ada path bagian yang menghubungkan sebarang dua titik.
(2) a. Tidak ada source (sebab, setiap titik mempunyai indegree yang bukan nol) dan tidak ada sink (sebab, setiap titik mempunyai outdegree yang bukan nol). b. D adalah terhubung lemah, sebab ada spanning semiwalk pada D (yaitu semiwalk yang melalui semua titik), yaitu : (x,y,w,z), (x,z,w,y), (z,y,w,x), … dan lain-lain. D adalah terhubung unilateral sebab ada spanning walk pada D (yaitu walk yang melalui semua titik), yaitu : (x,y,w,z), (y,x,z,w), …, dan sebagainya. D adalah tidak terhubung kuat, sebab tidak ada spanning walk yang tertutup pada D.
14.3 Rangkuman a. Ada pengertian graf berlabel, multigraf berlabel. Tidak dibedakan antara digraf multigraf; jadi pengertian digraf mencakup keduanya. Ada pengertian digraf berlabel. b. Dengan arc (µ, v) dimaksud garis berarah pada digraf yang mulai pada titik asal µ dan berakhir pada titik akhir v. Outdegree dari v dimaksud banyak arc yang mulai pada v indegree dari v dimaksud banyak arc yang berakhir pada v. Source adalah titik dengan indegree nol. Sink adalah titik dengan outdegree nol. Jika digraf berhingga D tidak mempunyai cycle (berarah) maka D mempunyai source dan sink. Walk adalah barisan titik-titik dan arc-arc. (v0, a1, v1, a2, v2, a3, v3, …, vn-1, an, vn) atau (v0, a1, v2, v3, …, vn) atau (a1, a2, a3, …, an) di mana ai = vi-1, vi adalah arc, untuk setiap i. Panjang walk adalah banyak arc pada walk tersebut. Spanning walk adalah walk dengan semua garis berlain-lainan. Path adalah walk dengan semua titik berlain-lainan. Cycle adalah path tertutup. Semiwalk adalah barisan titik-titik dan arc-arc. (v0, v1, v2, v3, …, vk) dengan (vi-1, vi) adalah arc atau (vi, vi-1) adalah arc.
83
c. Digraf D terhubung lemah atau weak, jika untuk sebarang dua titik µ dan v pasti ada semiwalk dari µ ke v. Digraf D adalah weak, jika dan hanya jika, ada spanning semiwalk pada D. Digraf D terhubung unilateral, jikab untuk sebarang dua titik µ ke v atau ada path dari v ke µ (sekurang-kurangnya satu titik dari mereka dapat dicapai dari titik-titik yang lain). Karakteristik terhubung unilateral : Digraf D unilateral, jika dan hanya jika, ada spanning walk pada D. Digraf D. terhubung kuat atau strong, jika untuk sebarang dua titik µ dan v ada path dari µ ke v (µ dapat dicapai dari v dan v dapat dicapai dari µ). Karkteristik terhubung kuat : Digraf D strong, jika dan hanya jika, ada spanning walk tertutup pada D. Digraf D strictyle weak, jika D adalah weak dan tidak unilateral digraf D strictly unilateral, jika D adalah unilateral dan tidak strong. Koleksi semua digraf yang strong adalah himpunan bagian dari koleksi semua digraf yang unilateral, dan koleksi semua digraf yang unilateral adalah himpunan bagian dari koleksi semua digraf yang weak d. Misal D adalah suatu graf berarah dengan titik-titik v1, v2, v3, …, vn. Matriks ajasensi (Adjacency matrix) digraf D adalah matriks MD = (Mij) dengan mij = banyak arc (vi, vj).
14.4 Soal Latihan (1) Tentukanlah matriks ajasensi untuk digraf D yang mempunyai diagram Gambar 14.11 v1
v2
v3
v4 Gambar 14.11
84
Jawab : A. 0 2 2 1
M=
0 0 1 1 2 1 1 0 0 0 1 1
B. 0 2 0 1
M=
0 0 1 1 2 1 1 0 0 0 1 1
C. 0 2 0 1
M=
2 0 2 1 2 1 1 0 0 0 1 1
D. 0 2 0 1
M=
0 0 1 1 2 2 3 3 0 0 1 1
(2) Perhatikan digraf Gambar 14.11 Tentukan banyak path dari v1, ke v3 ! Jawab : A. 4 B. 6 C. 5 D. 3 (3) Perhatikan digraf gambar 14.11. Tentukan jumlah indegree semua titik ! Jawab : A. 11 B. 9 C. 20 D. 10
85
(4) Perhatikan digraf D gambar 14.11. Digraf D adalah terhubung lemah, terhubung unilateral atau terhubung kuat ? Jawab : A. Hanya terhubung lemah B. Hanya terhubung unilateral C. Hanya terhubung kuat D. Terhubung lemah, unilateral dan kuat.
13.5 Daftar Pustaka Harary, F; Graph Theory; Addison – Wesley Publishing Company, 1972 Lipschutz, S; Discrete Mathematics, Schaum’s Outline Series in Mathematics, Mc Graw – Hill Book Company, 1976. Wilson, R.I.; Introduction to Graph Theory, Longman Group Limited., 1975.
86
