COURSE NOTE : DIGRAPH
Pada catatan kuliah ini akan dibahas tentang konsep digraph (graph berarah) yang merupakan
konsep penting dalam kuliah teori graph
Definisi Digraph
Suatu digraph (graph berarah) adalah himpunan tak kosong dari himpunan titik-titik dan
himpunan sisi berarah yang disebut arc. Masing masing arc menghubungkan dua titik
dengan arah tertentu.
Contoh :
Berikut adalah digraph dengan empat titik, yaitu u, v, w, x dan arc yaitu 1, 2, 3, 4, 5, dan 6. Arc 1
menghubungkan titik x ke u, arc 2 menghubungkan titik u ke w, arc 3 menghubungkan titik w ke v,
arc 5 menghubungkan titik x ke w, dan arc 6 menghubungkan titik x ke x.
Arc dinotasikan dengan dua titik berurutan yang menyatakan arah. Sebagai contoh arc 1
dinotasikan arc 1 = xu, yang menyatakan arah dari titik x ke titik u. perlu diperhatikan bahwa xu
tidak sama dengan ux.
Definisi Multiple Arc, Loop dan Digraph Sederhana
Dalam suatu digraph, dua atau lebih arc menghubungkan pasangan titik yang sama dengan
arah arc yang sama disebut dengan multiple arc. Suatu arc yang menghubungkan suatu titik
dengan titik itu sendiri disebut loop. Suatu digraph yang tidak mempunyai multiple arc dan
loop disebut digraph sederhana.
Contoh :
Pada gambar di bawah, digraph (a) mempunyai multiple arc, digraph (b) mempunyai loop,
sehingga digraph (a) dan digraph (b) bukanlah digraph sederhana. Pada digraph (c), tidak
mempunyai multiple arc dan loop, sehingga digraph (c) adalah digraph sederhana.
Analog dengan adjensi dan insidensi pada graph, ajensi dan insidensi pada digraph serupa dengan
graph hanya saja pada digraph memperhatikan sisi berarahnya.
Definisi Adjensi dan Insidensi
Titik v dan w dari suatu digraph adalah titik yang adjensi jika titik v dan w dihubungkan
dengan suatu arc e. Suatu arc e yang menghubungkan titik v ke w adalah insidensi dari v
dan insidensi ke w. v insidensi ke arc e dan w insidensi dari arc e.
Contoh :
Pada digraph di atas, titik u dan x adjensi, karena titik u dan x dihubungkan oleh suatu arc. Titik w
insidensi dari arc 2 dan arc 5 dan titik w insidensi ke arc 3 dan arc 4. Arc 1 insidensi dari x dan
insidensi ke u.
Diperoleh dari definisi bahwa suatu digraph secara lengkap ditunjukkan oleh titik dan arc, dan dua
digraph adalah sama jika keduanya mempunyai titik yang sama dan arc yang sama. Berikut
disajikan definisi dari digraph isomorfik
Definisi Digraph Isomorfik
Dua digraph C dan D adalah isomorfik jika D dapat diperoleh dengan melabeli ulang titik
titik di C, yang berarti bahwa jika ada suatu korespondensi satu satu antara titik C dan D
sedemikian sehingga arc yang menghubungkan masing-masing titik di C memiliki jumah arc
yang sama dengan arah arc yang sama pula dengan pasangan korespondensi dari titik titik
di D.
Contoh :
Perhatikan gambar di graph berikut.
Digraph C dan digraph D adalah grap isomorfik, karena kita dapat melabeli titik titik di digraph C
untuk mendapatkan digraph D dengan menggunakan korespondensi satu-satu . berikut :
C
u
v
w
x
D
2
3
4
1
perhatikan bahwa arc di C berkorespondensi dengan arc di D. sebagai contoh
dua arc dari u ke v di C berkorespondensi dengan dua arc dari 2 ke 3 di D. arc wx dan xw di C
berkorespondensi ke arc 41 dan 14 di D. loop ww di C berkorespondensi dengan loop 44 di D.
Definisi Derajat Titik pada Digraph
Dalam suatu digraph, derajat keluar (out-degree) dari titik v adalah banyaknya arc yang
insiden dari v, dan dinotasikan out-deg v, derajat masuk (in-degree) dari titik v adalah
banyaknya arc yang insiden ke v, dan dinotasikan dengan in-deg v.
Barisan out-degree dari digraph D adalah barisan yang diperoleh dengan mendaftar
outdegre dari D dalam urutan yang naik, dengan perulangan jika diperlukan. Untuk barisan
indegree dari D analog dengan barisan outdegree.
Contoh :
Dari digraph dibawah sebutkan derajat dari masing-masing titik
out-deg u = 1
out-deg v = 3
out-deg w = 2
in-deg u = 0
in-deg v = 1
in-deg w = 1
out-deg x = 0
out-deg y = 2
out-deg z = 2
in-degx = 0
in-deg y = 6
in-deg z = 2
barisan out-degree : (0, 1, 2, 2, 2, 3) dan barisan in-degree : (0, 0, 1, 1, 2, 6)
Latihan.
1.
Tulis semua titik dan arc dari tiap-tiap digraph berikut. Kemudian selidiki apakah digraph
tersebut digraph sederhana?
2.
Gambarlah suatu digraph dengan titik-titik dan arc yang didefinisikan. Kemudian selidiki
apakah digraph tersebut merupakan digraph sederhana?
3.
a. titik : {u, v, w, x}
arc : {vw, wu, wv, wx, xu}
b. titik : {1, 2, 3, 4, 5, 6, 7, 8}
arc : {12, 22, 23, 34, 35, 67, 68, 78}
Manakah dari pernyataan pernyataan berikut dipenuhi oleh digraph yang diberikan.
a. titik v dan w adjensi
b. titik v dan x adjensi
c. tiik u insidensi ke arc 2
d. arc 5 insidensi dari titik v.
4.
Perhatikan digraph D yang di tunjukkan pada gambar berikut. Manakah dari pernyataan
berikut dipenuhi oleh digraph D, dan berikan alasannya.
a. Titik u dan x adjansi
b. arc 2 insidensi ke titik w
c. titik x insidensi dari arc 3
5.
Dengan melabeli ulang titik titik, tunjukkan bahwa digraph berikut adalah isomorfik.
6.
Apakah digraph di bawah isomorfik? Beri alasannya
7.
Dari empat digraph berikut, manakah dua digraph yang sama, pasangan digraph mana yang
isomorfik, dan digraph mana yang tidak isomorfik dengan yang lainnya.
8.
Tulislah barisan out-degree dan barisan in-degree dari tiap-tiap digraph berikut :
9.
Untuk tiap tiap digraph pada soal no 9, tulislah
a. banyaknya arc
b. jumlah out-degree dari semua titik
c. jumlah in-degree dari semua titik
apa hubungan yang dapat Anda temukan dari masalah di atas?