BAB 2 LANDASAN TEORI
2.1. Graf 2.1.1. Definisi Graf
Teori Graf merupakan suatu diagram yang memuat informasi tertentu jika diinterpretasikan secara tepat. Dalam kehidupan sehari-hari graf digunakan untuk mengambarkan berbagai macam struktur yang ada. Tujuannya adalah sebagai visualisasi objek-objek agar lebih mudah dimengerti. Beberapa contoh graf yang sering dijumpai, antara lain struktur organisasi, bagan alir, pengambilan mata kuliah, peta, rangkaian listrik, dan lain-lain (Hendardi, A. 2012). Banyak sekali struktur yang bisa dipresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan graf. Sering kali graf digunakan untuk mempresentasikan suatu jaringan. Misalkan jaringan jalan raya dengan kota sebagai simpul (vertex) dan jalan yang menghubungkan setiap kota sebagai sisi (edge) dan bobotnya (weight) adalah panjang dari jalan tersebut. Secara matematis graf mendefinisikan sebagai pasangan himpunan (V, E), ditulis dengan notasi G= (V, E), yang dalam hal ini V adalah himpunan tidak kosong dari simpulsimpul (vertex atau node) dan E adalah himpunan sisi (edge) yang menghubungkan sepasang simpul (Munir, R. 2009) Simpul (vertex) pada graf dapat dinyatakan dengan huruf, bilangan atau gabungan keduanya. Sedangkan sisi-sisi yang menghubungkan simpul u dengan simpul v dinyatakan dengan pasangan (u, v) atau dinyatakan dengan lambang ππ1 , ππ2 , ππ3 dan seterusnya. 2.2. Teori Dasar Graf
Graf G didefinisikan sebagai pasangan himpunan (V,E), ditulis dengan notasi G=(V,E), yang dalam hal ini V adalah himpunan tidak kosong dari simpul-simpul dan E adalah himpunan sisi yang menghubungkan sepasang simpul (Munir, R. 2005). Garis yang hanya berhubungan dengan satu titik ujung disebut loop. Dua garis berbeda yang menghubungkan titik yang sama disebut garis paralel. Dua titik dikatakan berhubungan (adjacent) jika garis menghubungkan keduanya. Titik yang tidak memiliki
garis yang berhubungan dengannya disebut titik terasing (isolating point). Graf yang tidak memiliki titik (sehingga tidak mewakili garis) disebut garis kosong. Jika semua garisnya berarah, maka grafnya disebut graf berarah (directed graph), atau sering disingkat digraph. Jika semua garisnya tidak berarah, maka grafnya disebut graf tak berarah (undirected graph). Sehinga dapat ditinjau dari arahnya, graf dapat dibagi menjadi dua yaitu graf berarah dan graf tidak berarah.
2.2.1. Graf Berarah (Directed Graf = Digraph)
Pada graf berarah, arah sisi/urutan ikut diperhatikan. Dalam suatu graf, lintasan (path) adalah urutan simpul, atau sisi yang dibentuk untuk bergerak dari satu simpul ke simpul yang lain. Dalam graf berarah, titik akhir dari sebuah busur akan menjadi titik awal dari busur berikutnya. Sirkuit adalah lintasan yang memiliki simpul awal dan akhir yang sama. Panjang lintasan adalah banyaknya sisi yang dilalui lintasan tersebut. Suatu Graf berarah G terdiri dari himpunan titik-titik V(G) {π£π£1 , π£π£2 , β¦}, himpunan
garis-garis E(G) {ππ1 , ππ2 , β¦ }, dan suatu fungsi yang mengawankan setiap garis dalam
E(G) ke suatu pasangan berurutan titik (π£π£ππ , π£π£ππ ). Jika ππππ = (π£π£ππ , π£π£ππ ) adalah suatu garis dalam G, maka π£π£ππ disebut titik awal ππππ dan π£π£ππ disebut titik akhir ππππ . Arah garis adalah dari π£π£ππ ke
π£π£ππ .
Jumlah garis yang keluar dari titik π£π£ππ disebut derajat keluar (out degree) titik π£π£ππ
yang disimbolkan dengan ππ +(π£π£ππ ), sedangkan jumlah garis yang menuju ke titik π£π£ππ disebut derajat masuk (in degree) titik π£π£ππ , yang disimbolkan dengan ππβ(π£π£ππ ).
Titik terasing adalah titik dalam G dimana derajat keluar dan derajat masuknya
adalah 0. Titik pendant (tergantung) adalah titik dalam G dimana derajat masuk dan derajat keluarnya adalah 1. Dua garis berarah dikatakan paralel jika keduanya memiliki titik awal dan titik akhir yang sama.
Contoh: V2 e1 e5 e4
V1
V3 e2
e3
e6
e7 V6
e8 V5
V4 e9
Gambar 2.1 Graf Berarah
Tentukan: a. Himpunan titik-titik, himpunan garis-garis, dan fungsi perkawanan. b. Derajat masuk dan derajat keluar tiap titik. c. Titik terasing dan titik pendant. d. Garis paralel.
Penyelesaian: a. V(G) = { π£π£1 , π£π£2 , π£π£3 , π£π£4 , π£π£5 , π£π£6 } E(G)
= { ππ1 , ππ2 , ππ3 , ππ4 , ππ5 , ππ6 , ππ7 , ππ8 , ππ9 }
Fungsi mengawankan garis-garis dengan pasangan titik-titik berikut ππ1 dengan (π£π£1 , π£π£2 ) ππ2 dengan (π£π£4 , π£π£1 ) ππ3 dengan (π£π£1 , π£π£4 )
ππ4 dengan (π£π£1 , π£π£3 )
ππ5 dengan (π£π£3 , π£π£3 ) ππ6 dengan (π£π£3 , π£π£4 )
ππ7 dengan (π£π£3 , π£π£5 ) ππ8 dengan (π£π£5 , π£π£4 ) ππ9 dengan (π£π£5 , π£π£4 )
b. ππ + (π£π£1 ) = 3
ππ β (π£π£1 ) = 1
ππ+ (π£π£3 ) = 3
ππ β (π£π£3 ) = 2
ππ+ (π£π£2 ) = 0
ππ+ (π£π£4 ) = 1
ππ+ (π£π£5 ) = 2
ππ+ (π£π£6 ) = 0
ππ β (π£π£2 ) = 1 ππ β (π£π£4 ) = 4
ππ β (π£π£5 ) = 1 ππ β (π£π£6 ) = 0
Dapat dilihat bahwa dalam setiap graf berarah, βππ ππ+ (π£π£ππ ) = βππ ππ β (π£π£ππ )
c. Titik terasing adalah π£π£6 . Titik pendant π£π£2 .
d. Garis paralel adalah ππ8 dan ππ9 , dapat dilihat bahwa ππ2 dan ππ3 bukanlah garis paralel karena arahnya berbeda.
2.2.1.1. Path Berarah dan Sirkuit Berarah Pengertian walk, path, dan sirkuit dalam graf berarah sama dengan walk, path dan sirkuit dalam graf tak berarah. Hanya saja dalam graf berarah, perjalanan yang dilakukan harus
mengikuti arah garis. Untuk membedakan dengan graf tak berarah, maka walk, path berarah, dan sirkuit dalam graf berarah disebut walk berarah, path berarah, dan sirkuit berarah. Suatu graf berarah yang tidak memuat sirkuit berarah disebut Asiklik (Siang, J.J. 2009).
Contoh: Ada 4 macam golongan darah, masing-masing A, B, AB, dan O. Darah golongan O dapat diberikan kepada semua golongan. Darah golongan A dan B dapat diberikan ke golongannya sendiri atau ke golongan O. Darah golongan AB hanya dapat diberikan pada pasien dengan golongan darah AB . Gambarkan graf berarah untuk menyatakan keadaan tersebut. Anggaplah garis dari π£π£ππ ke π£π£ππ menyatakan bahwa darah dari π£π£ππ dapat diberikan
pada π£π£ππ . Apakah graf Asiklik? Penyelesaian:
Graf berarah menyatakan keadaan transfusi darah yang mungkin dilakukan. Dapat dilihat bahwa dalam graf berarah tersebut tidak ada sirkuit berarah sehingga grafnya Asiklik. AB
A
B
O
Gambar 2.2 Path berarah
2.2.1.2. Graf Berarah Terhubung
Suatu graf tak berarah disebut terhubung jika ada walk yang menghubungkan setiap dua titiknya. Pengertian itu berlaku juga bagi graf berarah. Berdasarkan arah garisnya, dalam graf berarah dikenal dua jenis keterhubungan, yaitu terhubung kuat dan terhubung lemah. Misalkan G adalah suatu graf berarah dan v, w adalah sembarang 2 titik dalam G. G disebut terhubung kuat jika ada path berarah dari v ke w. G disebut terhubung lemah, jika G tidak terhubung kuat, tetapi graf tak berarah yang bersesuaian dengan G terhubung.
Contoh: Manakah di antara graf-graf pada Gambar 2.3.yang terhubung kuat dan yang terhubung lemah? V1
V1
e1
e5 V2
e1
e3
e4 V3
e5
e6
V2
πΊπΊ1
V3
e3
e6 V4
e2
V4
e2
e4
πΊπΊ2
Gambar 2.3 Graf berarah terhubung
Penyelesaian: Dalam πΊπΊ1 , setiap dua titik dapat dihubungkan dengan path berarah sehingga graf berarah
πΊπΊ1 adalah graf terhubung kuat. Sebaliknya dalam πΊπΊ2 , tidak ada path berarah yang menghubungkan π£π£4 ke π£π£3 . Akan tetapi, jika semua arah garis dihilangkan (sehingga πΊπΊ2
menjadi graf tidak berarah), maka πΊπΊ2 merupakan graf yang terhubung. Jadi, πΊπΊ2 merupakan graf terhubung lemah.
2.2.1.3. Isomorfisma dalam Graf Berarah
Pengertian isomorfisma dalam graf berarah sama dengan isomorfisma pada graf tak berarah. Hanya saja pada isomorfisma graf berarah, korespondensi dibuat dengan memperhatikan arah garis.
Contoh Tunjukkan bahwa graf πΊπΊ1 pada Gambar 2.4 isomorfis dengan πΊπΊ2 , sedangkan πΊπΊ3 tidak isomorfis dengan πΊπΊ1 V1
V2
V3
V3 V2 V3
V4
G1
V2
V1
V1
V5
V4
V5
V5
V4 G2
Gambar 2.4 Isomofisma dalam Graf Berarah
G3
Penyelesaian: Untuk membuktikan bahwa πΊπΊ1 isomorfis dengan πΊπΊ2 , maka harus dibuat fungsi g : V(πΊπΊ1 ) β V(πΊπΊ2 ) dan h : E(πΊπΊ1 ) β E(πΊπΊ2 )
yang mempertahankan titik-titik ujung serta arah garis. Dalam πΊπΊ1 , ada 4 garis yang keluar dari ππ3 . Titik yang memiliki sifat seperti itu dalam πΊπΊ2
adalah titik π£π£1 , sehingga dibuat fungsi g sedemikian hingga
g(π£π£3 ) = π£π£1 , g(π£π£1 ) = π£π£2 , g(π£π£2 ) = π£π£3 , g(π£π£5 ) = π£π£4 , dan g(π£π£4 ) = π£π£5
fungsi h adalah sebagai berikut:
h ((π£π£1 , π£π£2 )) = (π£π£2 , π£π£3 ) ; h ((π£π£2 , π£π£5 )) = (π£π£3 , π£π£4 )
h ((π£π£5 , π£π£4 )) = (π£π£4 , π£π£5 ) ; h ((π£π£4 , π£π£1 )) = (π£π£5 , π£π£2 )
h ((π£π£3 , π£π£1 )) = (π£π£1 , π£π£2 ) ; h ((π£π£3 , π£π£2 )) = (π£π£1 , π£π£3 ) h ((π£π£3 , π£π£5 )) = (π£π£1 , π£π£4 ) ; h ((π£π£3 , π£π£4 )) = (π£π£1 , π£π£5 )
pada fungsi g dan h dapat dilihat bahwa πΊπΊ1 isomorfis dengan πΊπΊ2 . Selanjutnya, akan
dibuktikan bahwa πΊπΊ3 tidak isomorfis dengan πΊπΊ1 . Dalam πΊπΊ3 , ada garis (π£π£1 , π£π£4 ) dan (π£π£4 , π£π£1 ).
Jika πΊπΊ1 isomorfis dengan πΊπΊ3 , maka harus ada fungsi h πΊπΊ3 β πΊπΊ1 demikian, sehingga h(π£π£1 , π£π£4 ) dan h(π£π£4 , π£π£1 ) merupakan garis-garis dalam πΊπΊ1 (dengan kata lain, ada titik π£π£ππ dan π£π£ππ
dalam πΊπΊ1 demikian, sehingga ada garis dari π£π£ππ ke π£π£ππ dan dari π£π£ππ ke π£π£ππ ). Dalam πΊπΊ1 tidak ada garis seperti itu sehingga πΊπΊ3 tidak isomorfis dengan πΊπΊ1 . 2.2.2. Graf Tak Berarah (Undirected Graph)
Suatu graf G terdiri dari dua himpunan yang berhingga, yaitu himpunan simpul-simpul tak kosong (V(G)) dan himpunan jalur-jalur (E(G)). Jika semua jalurnya tidak berarah, maka grafnya disebut graf tak berarah (Siang, J.J. 2009).
2.2.2.1. Graf Bipartite (Bipartite Graph)
Suatu graf G disebut Graf Bipartite apabila V(G) merupakan gabungan dari dua himpunan tak kosong π£π£1 dan π£π£2 dan setiap garis dalam G menghubungkan suatu titik dalam π£π£1
dengan titik dalam π£π£3 . Apabila dalam Graf Bipartite setiap titik dalam π£π£1 berhubungan
dengan setiap titik dalam π£π£2 , maka grafnya disebut Graf Bipartite lengkap. Jika π£π£1 terdiri
dari m titik dan π£π£2 terdiri dari n titik, maka Graf Bipartite lengkapnya sering diberi simbol πΎπΎππ ,ππ .
Contoh : Tentukan mana di antara graf-graf pada Gambar 2.5 yang merupakan Graf Bipartite dan Bipartite Lengkap. v1 e2
v4
v1
e3
e1
e1
v2
v3
e6
v3 (a)
v4
e3
v3 e5
e4 v4
(b)
v4
e3
v5
e2
e1 v2
e6
e4 v5
e2
v6
e2
v2 e5
v1
v1
e1
(c)
e3
e4
e5
v5 e6 v3
v2 (d)
Gambar 2.5 Graf Bipartite
Penyelesaian: a. Jelas bahwa titik-titik grafnya terbagi menjadi dua bagian, yaitu π£π£1 = {π£π£1 , π£π£2 , π£π£3 } dan π£π£2 = {π£π£4 , π£π£5 }. Setiap titik dalam π£π£1 dihubungkan dengan setiap titik dalam π£π£2 sehingga grafnya merupakan πΎπΎ3,2 .
b. Hanya merupakan Graf Bipartite saja karena titik-titik dalam graf terbagi menjadi dua bagian, yaitu π£π£1 = {π£π£1 , π£π£3 } dan π£π£2 = {π£π£2 , π£π£4 }. Akan tetapi tidak semua titik dalam π£π£1
dihubungkan dengan semua titik dalam π£π£2 (π£π£1 tidak dihubungkan dengan π£π£4 ).
c. Dengan pengaturan letak titik-titiknya, maka graf gambar (c) dapat digambarkan sebagai graf. e2
v1 e1 v3
v2 e3 v4
e4 e5
v5
e6
v6
Gambar 2.6 Graf Bipartite Tampak bahwa titik-titiknya terbagi menjadi dua bagian, yaitu π£π£1 = {π£π£1 , π£π£3 , π£π£5 } dan π£π£2
= {π£π£2 , π£π£4 , π£π£6 }. Setiap menghubungkan sebuah titik dalam π£π£1 dengan sebuah titik dalam π£π£2 sehingga grafnya merupakan Graf Bipartite.
d. Bila dilihat bahwa meskipun tampil berbeda, sebenarnya graf pada Gambar 2.5 bagian (d) sama dengan graf pada Gambar 2.5 bagian (a) sehingga graf pada Gambar 2.5 bagian (d) adalah πΎπΎ3,2 .
Posisi titik-titik dalam penggambaran graf kadang-kadang mempengaruhi pandangan, seperti halnya pada Gambar 2.5 bagian (c) dan (d). Dalam kedua graf tersebut, semua titik tampaknya terhubung dan tidak dapat dipisahkan walaupun kenyataannya tidaklah demikian. Oleh karena itu harus jeli dalam menentukan apakah suatu graf merupakan Graf Bipartite. 2.2.2.2. SubGraf Konsep subgraf sama dengan konsep himpunan bagian. Dalam teori himpunan, himpunan A dikatakan merupakan himpunan bagian B bila hanya setiap anggota A merupakan B. Oleh karena graf merupakan himpunan yang terdiri dari titik dan garis, maka H dikatakan subgraf G, jika semua titik dan garis H juga merupakan titik dan garis dalam G. Secara formal, subgraf dapat didefinisikan sebagai berikut. Misalkan G adalah suatu graf. Graf H dikatakn subgraf G bila dan hanya bila a. V(H) β V(G) b. E(H) β E(G)
c. Setiap garis dalam H memiliki titik ujung yang sama dengan garis tersebut dalam G. Dari definisi tersebut ada beberapa hal yang dapat diturunkan 1. Sebuah titik dalam G merupakan subgraf G. 2. Sebuah garis dalam G bersama-sama dengan titik-titik ujungnya merupakan subgraf G. 3. Dalam subgraf berlaku sifat transitif, jika H adalah subgraf G dan G adalah subgraf K, maka K adalah subgraf K. Contoh: Gambarlah semua Subgraf yang mungkin dibentuk dari graf G pada Gambar 2.7. e2 v2 e1 v1
Gambar 2.7 Sub Graf Penyelesaian: G terdiri dari dua titik dan dua garis. Subgraf G yang mungkin dibentuk terdiri dari satu atau dua titik dan 0, satu atau dua garis. Semua Subgraf G yang mungkin dibuat dapat digambarkan sebagai berikut:
Jumlah garis = 0
v2
v2 v1
v1
e2
e1
Jumlah garis = 1
v2
v2
v1
e1 v1
v1
e2 v2 Jumlah garis = 2
e1 v1 Gambar 2.8 Sub-Graf dari Gambar 2.7
2.2.2.3. Derajat (Degree)
Misalkan v adalah titik dalam suatu graf G. derajat titik v (simbol d(v)) adalah jumlah garis yang berhubungan dengan titik v dan garis suatu loop dihitung dua kali. Derajat total G adalah jumlah derajat semua titik dalam G. Contoh:
Tentukan derajat tiap-tiap titik dalam graf pada Gambar 2.9. Berapa derajat totalnya
v5
e1 v1
v3 e3
e2
e4
v4
v6 e5
v2 Gambar 2.9 Derajat (Degree)
Penyelesaian: d (π£π£1 ) = 4 garis yang berhubungan dengan π£π£1 adalah ππ2 , ππ3 dan loop ππ1 yang dihitung dua kali.
d (π£π£2 ) = 2 garis yang berhubungan dengan π£π£2 adalah ππ2 dan ππ3 .
d (π£π£3 ) dan d (π£π£5 ) = 1 karena garis yang berhubungan dengan π£π£3 dan π£π£5 adalah ππ4 .
d (π£π£4 ) = 2 garis yang berhubungan dengan π£π£4 adalah loop ππ5 yang dihitung dua kali. d (π£π£6 ) = 0 karena tidak ada garis yang berhubungan dengan π£π£6 .
Derajat total = β6ππ=1 ππ (π£π£ππ ) = 4 + 2 + 1 + 2 + 1 + 0 = 10. 2.2.2.4. Path dan Sirkuit
Misalkan G adalah suatu graf. Misalkan pula v dan w adalah dua titik dalam G. Suatu Walk dari v dan w adalah barisan titik-titik berhubungan dan garis secara berselang-selang, diawali dari titik v dan diakhiri pada titik w. Walk dengan panjang n dan v ke w dituliskan sebagai berikut π£π£0 ππ1 π£π£1 ππ2 π£π£2 β¦ π£π£ππ β1 ππππ π£π£ππ
dengan π£π£0 = v, π£π£ππ = w, π£π£ππ β1 , dan π£π£ππ adalah titik-titik ujung garis ππππ . Path dengan panjang n
dari v ke w adalah walk dari v ke w yang semua garisnya berbeda. Path dari v ke w
dituliskan sebagai v = π£π£0 ππ1 π£π£1 ππ2 π£π£2 β¦ π£π£ππ β1 ππππ π£π£ππ = w dengan ππππ β w untuk i β j. Walk v w v = v0 v1 e2 v2 β¦ vn-1 en vn = w vj-1 dan vi adalah titik-titik ujung garis ei Semua garis berbeda
Path v
Titik awal dan akhir
Semua titik berbeda
Path sederhana v
v0 = vn)
Sama (
w
Sirkuit
Titik awal dan akhir Sama (
w
v0 = vn)
Semua titik berbeda Kecuali
v0 = vn
Sirkuit sederhana
Gambar 2.10 Bagan Alur Path dan Sirkuit Path sederhana dengan panjang n dan v ke w adalah path dari v ke w berbentuk v = π£π£0 ππ1 π£π£1 ππ2 π£π£2 β¦ π£π£ππβ1 ππππ π£π£ππ = w dengan ππππ β w untuk i β j dan π£π£ππ β π£π£ππ untuk k β m.
Sirkuit dengan panjang n adalah path yang dimulai dan diakhiri pada titik yang sama.
Sirkuit adalah path yang berbentuk v = π£π£0 ππ1 π£π£1 ππ2 π£π£2 β¦ π£π£ππ β1 ππππ π£π£ππ = w dengan π£π£0 = π£π£ππ . Sirkuit sederhana dengan panjang n adalah Sirkuit yang semua titiknya berbeda. Sirkuit
sederhana berbentuk v = π£π£0 ππ1 π£π£1 ππ2 π£π£2 β¦ π£π£ππβ1 ππππ π£π£ππ = w dengan ππππ β ππππ untuk i β j dan π£π£ππ β π£π£ππ untuk k β m, kecuali π£π£0 = π£π£ππ .
2.2.2.5. Sirkuit Euler Sirkuit Euler adalah Sirkuit yang melalui tiap sisi dalam graf tepat satu kali (Siang, J.J. 2009) Untuk mengenang ahli matematika Leonhard Euler yang berhasil memperkenalkan graf untuk memecahkan masalah tujuh jembatan Koningsberg pada tahun 1736. Kota Koningberg dibangun pada pertemuan dua cabang sungai Pregel. Kota tersebut terdiri dari sebuah pulau di tengah-tengah dan tujuh jembatan yang mengelilinginya.
Gambar 2.11 Jembatan Konigsberg
2.2.2.6. Graf Terhubung dan Tidak Terhubung
Misalkan G adalah suatu Graf. Dua titik v dan w dalam G dikatakan terhubung hanya ada walk dari v ke w. Graf G dikatakan terhubung bila hanya setiap dua titik dalam G terhubung. Graf G dikatakan tidak terhubung bila ada dua titik dalam G yang tidak terhubung. Contoh Tentukan mana di antara graf pada Gambar 2.12 yang merupakan Sirkuit Euler. carilah rute perjalanan kelilingnya v3
e2
v1
e3
v2 e1
e3
v4
e4
v6
v1 e5
e14
v5
e11
v10
e7 e8
e10 e13 v9
e6
e12
e4 e2
e3
v2
e4
v6
e1
e1
v1 e2
v5 e6
v3 e5
e7
e6
e8
e5
v8 v7 e9 (a)
v3
v5
v4 (b)
Gambar 2.12 Graf terhubung dan Graf tak terhubung
v4 (c)
Penyelesaian: a. d(π£π£2 ) = d(π£π£3 ) = d(π£π£4 ) = d(π£π£6 ) = d(π£π£10 ) = 2 d(π£π£5 ) = 4
d(π£π£7 ) = d(π£π£8 ) = d(π£π£9 ) = 3 d(π£π£1 ) = 5
karena ada titik yang berderajat ganjil, maka (a) bukanlah Sirkuit Euler. b. Meskipun semua titiknya berderajat dua (genap), tetapi grafnya tidak terhubung. Jadi, (b) bukanlah Sirkuit Euler. c. d(π£π£1 ) = d(π£π£3 ) = 2
d(π£π£2 ) = d(π£π£4 ) = d(π£π£5 ) = 4
karna graf (c) terhubung dan semua titiknya berderajat genap, maka (c) merupakan Sirkuit Euler.
2.2.2.7. Sirkuit Hamilton
Suatu graf terhubung G disebut Sirkuit Hamilton bila ada sirkuit yang mengunjungi setiap titiknya tepat satu kali kecuali titik awal yang sama dengan titik akhirnya. Perhatikan perbedaaan Sirkuit Euler dan Sirkuit Hamilton. Dalam Sirkuit Euler, semua garis harus dilalui tepat satu kali, sedangkan semua titiknya boleh dikunjungi lebih dari satu kali. Sebaliknya, dalam Sirkuit Hamilton semua titik harus dikunjungi tepat satu kali dan tidak harus melalui semua garis. Dalam Sirkuit Euler, yang dipentingkan adalah garisnya. Sebaliknya dalam Sirkuit Hamilton, yang dipentingkan adalah kunjungan pada titiknya(Munir, R. 2009).
2.3. Representasi Graf dalam Matriks
Matriks dapat digunakan untuk menyatakan suatu graf. Hal itu sangat membantu untuk membuat program komputer yang berhubungan dengan graf. Dengan menyatakan graf sebagai suatu matriks, maka perhitungan-perhitungan yang diperlukan dapat dilakukan dengan mudah. Kesulitan utama dalam mempresentasikan graf dalam suatu matriks adalah keterbatasan matriks untuk mencakup semua informasi yang ada dalam graf. Akibatnya, ada bermacam-macam matriks untuk menyatakan suatu graf tertentu. Tiap-tiap matriks
tersebut memiliki keuntungan yang berbeda-beda saat menyaring informasi yang dibutuhkan pada graf.
2.3.1. Representasi Graf Tak Berarah dalam Matriks 2.3.1.1. Matriks Hubung Matriks Hubung (Adjacency Matrix) digunakan untuk menyatakan graf dengan cara menyatakannya dalam jumlah garis yang menghubungkan titik-titiknya. Jumlah baris (kolom) matriks hubung sama dengan jumlah titik dalam graf. Misalkan G adalah graf tak berarah dengan titik-titik π£π£1 , π£π£2 , β¦ π£π£ππ ( n berhingga).
Matriks hubung yang sesuai dengan graf G adalah matriks A = (ππππππ ) dengan ππππππ = jumlah garis yang menghubungkan titik π£π£ππ dengan titik π£π£ππ , i, j = 1, 2,β¦, ππ. 2.3.1.2. Matriks Biner Misalkan G adalah graf tanpa loop dengan n titik π£π£1 , π£π£2 , β¦ , π£π£ππ dan k garis ππ1 , ππ2 , β¦ ππππ .
Matriks Biner yang sesuai dengan graf G adalah matriks A berukuran n x k yang elemennya adalah ππππππ
1 jika titik vi berhubungan dengan garis ej
0 jika titik vi tidak berhubungan dengan garis ej
Nama Matriks Biner diambil dari sifat matriks yang hanya berisi bilangan 0 atau 1 saja. Matriks Biner kadang-kadang disebut matriks (0-1) atau matriks insidensi (incidence matrix).
2.3.1.3 Matriks Sirkuit
Misalkan G adalah graf yang memuat q buah sirkuit sederhana dan e buah garis. Matriks sirkuit A = (ππππππ ) yang bersesuaian dengan G adalah matriks yang terdiri dari q baris dan e kolom dengan elemen. ππππππ
1 jika sirkuit ke-i memuat garis ke-j 0 jika sirkuit ke-i tidak memuat garis ke-j
2.3.2. Representasi Graf Berarah dalam Matriks
Cara menyatakan graf berarah dalam matriks sebenarnya tidak jauh berbeda dengan cara menyatakan graf tak berarah dalam suatu matriks. Perbedaannya hanya terletak pada keikutsertaan informasi tentang arah garis yang terdapat dalam graf berarah.
2.3.2.1. Matriks Hubung
Matriks Hubung untuk menyatakan suatu graf berarah banyak dipakai dalam berbagai disiplin ilmu berbeda-beda sehingga nama yang dimiliki berbeda-beda pula. Dalam Teori Otomata, matriks hubung dikenal dengan nama matriks transisi, yang dalam konsep relasi disebut matriks relasi dalam jaringan disebut matrik koneksi, dan lain-lain. Misalkan G adalah graf berarah yang terdiri dari n titik tanpa garis paralel. Matriks Hubung yang sesuai dengan graf G adalah matriks bujur sangkar n x n, A = (ππππππ ) dengan ππππππ
1 jika ada garis vi ke titik vj
0 jika tidak ada garis vi ke titik vj
2.3.2.2. Matriks Sirkuit
Untuk menyatakan graf berarah ke dalam Matriks Sirkuit, perlu diperhatikan arah garis pembentuk sirkuitnya. Misalkan G adalah graf berarah dengan e buah garis dan q buah sirkuit atau Sirkuit Berarah. Sembarang arah orientasi (searah/berlawanan dengan arah jarum jam) diberikan ke tiap-tiap sirkuit. Matriks Sirkuit yang bersesuaian dengan graf G adalah matriks A = (ππππππ ) dengan 1
jika sirkuit ke-i memuat garis ke-j dan arah garis ke-j sama dengan arah orientasi
ππππππ
-1
jika sirkuit ke-i memuat garis ke-j dan arah garis ke-j berlawanan dengan arah orientasi
0
jika sirkuit ke-i tidak memuat garis ke-j
Perbedaan Matriks Sirkuit untuk menyatakan graf berarah dan tidak berarah terletak pada tanda negatif pada elemen matriks, yang menyatakan bahwa garis yang
bersesuaian memiliki arah yang berlawanan dengan arah orientasi yang didefinisikan. Orientasi yang diberlakukan pada setiap sirkuit dapat dibuat sembarang sehingga suatu graf berarah dapat dinyatakan dengan beberapa Matriks Sirkuit yang berbeda 2.4. Algoritma Floyd-Warshall
Algoritma Floyd-Warshall adalah sebuah algoritma analisis graf untuk mencari bobot minimum dari graf berarah. Algoritma Floyd-Warshall adalah matriks hubung graf berarah berlabel, dan keluarannya adalah path terpendek dari semua titik ke titik yang lain (Kamayudi, A. 2009). Dalam usaha untuk mencari path terpendek, Algoritma Warshall memulai iterasi dari titik awalnya kemudian memperpanjang path dengan mengevaluasi titik demi titik hingga mencapai titik tujuan dengan jumlah bobot yang seminimum mungkin. Misalkan ππ0 adalah matriks hubung graf berarah berlebel mula-mula. ππ β adalah matriks hubung
minimal dengan ππππππ β = path terpendek dari titik π£π£ππ ke π£π£ππ .[4]
Algoritma Warshall untuk mencari path terpendek adalah sebagai berikut
1. W = ππ0
2. Untuk k = 1 hingga n, lakukan: Untuk i = 1 hingga n, lakukan Untuk j = 1 hingga n lakukan Jika W[i, j] > W[i, k] + W[k, j], maka Tukar W[i, j] dengan W[i, k] + W[k, j]
3 ππ β = W
Dalam iterasinya untuk mencari path terpendek, Algoritma Warshall membentuk n
matriks sesuai dengan iterasi-k. Hal ini menyebabkan waktu prosesnya lambat, terutama untuk n yang besar. Meskipun waktu prosesnya bukanlah yang tercepat, Algoritma Warshall sering dipergunakan untuk menghitung path terpendek karena kesederhanaannya. Program implementasinya Algoritma Warshall sangat mudah dibuat.
2.5. Algoritma Johnson Algoritma Johnson adalah dapat digunakan untuk graf yang berbobot negatif dan untuk menyelesaikan masalah lintasan terpendek di setiap titik ke semua titik lain. Langkah awal penyelesaian (Noviandi, E. 2012).
Algoritma Johnson adalah mengonstruksi graf yang baru dengan menambahkan graf baru pada graf dan memberi bobot sisi yang keluar dari titik baru tersebut dengan 0. Langkah selanjutnya adalah mencari lintasan terpendek dari titik baru ke semua titik lain. Lintasan Terpendek tersebut digunakan untuk mengubah bobot semua sisi pada graf baru agar bobot semula bernilai positif. Setelah itu dicari lintasan terpendek dari tiap titik ke semua titik lain dengan mengubah hasilnya dengan menggunakan hasil dari perhitungan berupa matriks. Dari matriks ini dapat diketahui panjang lintasan terpendek dari titik ke semua titik lain. Langkah Algoritma Johnson adalah sebagai berikut 1. Mengostruksi graf baru G, dengan cara menambahkan titik baru sehingga Vβ = V + {s} dan E + {(s,v)v di V} 2. Setiap titik v di V 0 β w (s, v) β β w (v, s) 3. Menjalankan Algoritma Bellman-Ford pada graf baru a. jika terdapat bobot negatif maka selesai b. jika tidak terdapat bobot negatif maka hitung d(s, v) , 4. Setiap (u, v) di E
vβV
W(u, v) = w(u, v) + d (s, v) β d(s, v) 5. Setiap v di V, dijalankan Algoritma Djikstra untuk menghitung d(u, v) 6. Dβ = d(u, v) 7. Setiap (u, v) di V ; d(u, v) = d(u, v) + d(sv) β d(s, u) 8. D = d(u, v) Keterangan w(s,v)
= bobot sisi dari s ke v.
d(s,v)
= panjang lintasan terpendek dari s ke v.
w(u,v)
= bobot sisi baru dari u ke v.
d(u,v)
= panjang lintasan terpendek dari u ke v dan yang dihutung adalah bobot sisi baru (w).
d(u,v)
= panjang lintasan terpendek dari u ke v.
Dβ
= matriks hasil perhitungan lintasan terpendek dari tiap-tiap pasangan titik dan bobot sisi yang digunakan adalah w.
D
= matriks hasil akhir dari perhitungan.
Dalam Algoritma Johnson terdapat dua Algoritma untuk penyelesainnya, yaitu Algoritma Bellman-Ford dan Algoritma Djikstra. 2.5.1. Algoritma Bellman-Ford Algoritma Bellman-Ford menghitung jarak terpendek (dari satu sumber) pada sebuah graf berbobot. Maksudnya dari satu sumber ialah bahwa ia menghitung semua jarak terpendek yang berawal dari satu vertex. Algoritma Dijkstra dapat lebih cepat mencari hal yang sama dengan syarat tidak ada (edge) yang berbobot negatif, maka Algoritma Bellman-Ford hanya digunakan jika ada sisi berbobot negatif. 2.5.2. Algoritma Dijkstra Algoritma Dijkstra ditemukan oleh Edsger W. Dijkstra yang merupakan salah satu varian bentuk algoritma populer dalam pemecahan persoalan yang terkait dengan masalah optimasi dan bersifat sederhana. Algoritma ini menyelesaikan masalah untuk mencari lintasan terpendek ( sebuah lintasan yang mempunyai panjang minimum) dari vertex a ke vertex z dalam graf berbobot, bobot tersebut adalah bilangan positif jadi tidak dapat dilalui oleh vertex negatif. Dalam mencari solusi, Algoritma Dijkstra menggunakan prinsip greedy, yaitu mencari solusi optimum pada setiap langkah yang dilalui dengan tujuan untuk mendapatkan solusi optimum pada langkah selanjutnya yang akan mengarah pada solusi terbaik. Algoritma ini mencari panjang lintasan terpendek dari vertex a ke z dalam sebuah graf berbobot. Langkah-langkah dalam menentukan lintasan terpendek pada Algoritma Dijkstra yaitu: 1.
Pada awalnya pilih vertex dengan bobot yang terendah dari vertex yang belum dipilih, diinisialisasikan dengan β0β dan yang sudah terpilih diinisialisasikan dengan β1β.
2.
Bentuk tabel yang terdiri dari vertex, status, bobot. Lengkapi kolom bobot yang diperoleh dari jarak vertex sumber ke semua vertex yang langsung terhubung dengan vertex sumber tersebut.
3.
Jika vertex sumber ditemukan maka tetapkan sebagai vertex terpilih.
4.
Tetapkan vertex terpilih dengan label permanen dan perbaharui vertex yang langsung terhubung.
5.
Tentukan vertex sementara yang terhubung pada vertex yang sudah terpilih sebelumnya dan merupakan bobot terkecil dilihat dari tabel dan tentukan sebagai vertex terpilih berikutnya.
6.
Apakah vertex yang terpilih merupakan vertex tujuan? Jika ya, maka kumpulan vertex terpilih merupakan rangkaian yang menunjukkan lintasan terpendek.
7.
Begitu seterusnya hingga semua vertex terpilih.
2.6. JAVA Java adalah bahasa pemrograman yang bersifat open source yang dikembangkan oleh Sun Microsistems sejak tahun 1991 (Hakim,R. & Ir.Sutarno, M.Si. 2009). Bahasa ini dikembangkan dengan model yang mirip dengan bahasa C++ dan Smalltalk, namun dirancang agar lebih mudah dipakai dan platform independent, yaitu dapat dijalankan di berbagai jenis sistem operasi dan arsitektur komputer. Java sendiri merupakan bahasa pemrograman yang berbasis objek, maksudnya adalah semua aspek yang terdapat pada Java adalah objek, sehingga memudahkan untuk mendesain, membuat dan mengembangkan program Java dengan cepat. Kelebihan ini membuat program Java menjadi mudah untuk digunakan oleh banyak orang. Pada Tahun 1996, Sun Microsistems secara resmi merilis versi awal Java yang kemudian terus berkembang hingga muncul JDK 1.1 (Java Development Kit versi 1.1). Perkembangan terus dilakukan hingga muncul versi baru yang disebut Java
2.
Perubahan utama antara versi sebelumnya adalah adanya Swing yang merupakan teknologi Graphical User Interface (GUI) yang mampu menghasilkan aplikasi desktop yang benar-benar baik. Dalam penelitian ini penulis menggunakan Java versi The Java 2 Platform, Standart Edition (J2SE) yang merupakan Teknologi Java edisi standar, yang digunakan untuk penerapan Teknologi Java pada komputer desktop. Versi ini menyediakan lingkungan pengembangan yang kaya fitur, stabil, aman dan mendukung konektivitas basis data, rancangan antarmuka pemakai, masukan/keluaran, dan pemrograman jaringan.
2.7. UML (Unified Modeling Language)
Unified Modeling Language (UML) tidak mendefinisiskan proses standar tetapi dimaksudkan untuk menjadi berguna dengan proses perkembangan berulang (Dharwiyanti,
S & R.S. Wahyono. 2003). Hal ini dimaksudkan untuk mendukung proses perkembangan dengan Object Oriented. UML menyimpan informasi tentang struktur statis dan perilaku dinamis suatu sistem. Perilaku Dinamis mendefinisikan sejarah objek dari waktu ke waktu dan komunikasi antara objek-objek untuk mencapai tujuan. UML terdiri atas pengelompokan diagram-diagram sistem menurut aspek atau sudut pandang tertentu. Diagram adalah yang menggambarkan permasalahan maupun solusi dari permasalahan suatu model. UML mempunyai 13 diagram, diantaranya Use Case Diagram, Class Diagram, Package Diagram, Object Diagram, Sequence Diagram, Collaboration Diagram, StatiChart Diagram, Activity Diagram, Deployment Diagram, Component Diagram, Composite Structure Diagram, Interaction Overview Diagram, Timing Diagram. Tetapi yang sering digunakan adalah Use Case Diagram, Activity Diagram, Sequence Diagram, dan Class Diagram.
2.7.1. Use Case Diagram (Diagram Pengguna Keadaan)
Use Case Diagram menggambarkan fungsionalitas yang diharapkan dari sebuah sistem. Dalam pembuatan Use Case Diagram, yang ditekankan adalah βapaβ yang diperbuat sistem, dan bukan βbagaimanaβ. Sebuah Use Case mempresentasikan sebuah interaksi antara aktor dengan sistem. Berikut beberapa simbol yang digunakan pada Use Case Diagram di antaranya terdapat pada Tabel 2.1. Tabel 2.1 Simbol Pada Use Case Diagram Simbol
Nama Simbol Aktor
Use Case
Use Case
Asosiasi
Include << include >> Sistem
Sistem
Kegunaan Sebagai subjek yang berinteraksi atau menggunakan sistem Sebagai kegiatan yang dapat dilakukan oleh pengguna pada sistem Sebagai penghubung antara aktor dan Use Case yang dilakukan Sebagai penghubung antara Use Case yang membutuhkan Use Case yang lain Sebagai cakupan Wilayah Sistem
2.7.2. Activity Diagram (Diagram Aktivitas) Activity Diagram menggambarkan berbagai alur aktivitas dalam sistem yang sedang dirancang, bagaimana masing-masing alur berawal, decision yang mungkin terjadi, dan bagaimana mereka berakhir. Sebuah aktivitas dapat direalisasikan oleh satu Use Case atau lebih.
Aktivitas
menggambarkan
proses
yang
berjalan,
sementara
Use
Case
menggambarkan bagaimana aktor menggunakan sistem untuk melakukan aktivitas. Berikut ini beberapa simbol yang digunakan pada Activity diagram dapat dilihat pada Tabel 2.2. Tabel 2.2 Simbol pada Activity Diagram Simbol
Nama Simbol Inisial node
Kegunaan Awal aktivitas
Final Node
Akhir Aktivitas
Action
Sebagai aktivitas dilakukan oleh sistem
Action
Control Flow Decision Exception handler
yang
Sebagai penghubung urutan aktivitas Merupakan aktivitas pengecekan kondisi Menunjukkan kondisi pengecualian apabila suatu action tidak dapat dilakukan
2.7.3. Class Diagram (Diagram Kelas)
Class adalah sebuah spesifikasi yang jika diinstansiasi akan menghasilkan sebuah objek dan merupakan inti dari pengembangan dan desain berorientasi objek. Class menggambarkan keadaan (atribut/property) suatu sistem, sekaligus menawarkan layanan untuk memanipulasi keadaan tersebut (metode/fungsi). Class Digram menggambarkan struktur dan deskripsi class, package, dan objek beserta hubungan satu sama lain seperti containment, pewarisan, asosiasi, dan lain-lain. Berikut ini beberapa simbol yang digunakan pesa Class Diagram. Dapat dilihat pada Tabel 2.3.
Tabel 2.3 Simbol Pada Class Diagram Simbol
Nama Simbol Class
Class Generalization
<<use>>
Usage
Kegunaan Sebagai kelas yang digunakan pada sistem Menunjukkan hubungan inheritance antar kelas Menunjukkan hubungan penggunaan suatu kelas dengan kelas yang lain
2.7.4. Sequence Diagram (Diagram Rangkaian)
Sequence Diagram menggambarkan interaksi antar-objek di dalam dan sekitar sistem (termasuk pengguna, display, dan sebagainya) berupa message yang digambarkan terhadap waktu. Sequence Diagram terdiri atas dimensi vertikal (waktu) dan dimensi horizontal (objek-objek yang terkait). Sequence Diagram biasa digunakan untuk mengambarkan skenario atau rangkaian langkah-langkah yang dilakukan sebagai tanggapan dari sebuah event untuk menghasilkan output tertentu. Berikut ini beberapa simbol yang digunakan pada Sequence Diagram dapat dilihat pada Tabel 2.4. Tabel 2.4 Tabel simbol pada Sequence Diagram Simbol
Nama Simbol Actor
Kegunaan Sebagai subjek yang menggunakan sistem
Life line
Bagian dari sistem yang melakukan aktivitas pemrosesan data
Message
Alur data yang diproses oleh sistem
Lifeline
2.8. Flowchart
Flowchart adalah suatu diagram alur (flow) yang menunjukan (flow) di dalam program atau prosedur sistem secara logika (Suarga, 2012). Pada diagram alur, dapat dilihat secara jelas arus pengendalian algoritma, yakni bagaimana rangkaian pelaksanaan kegiatan program tersebut. Suatu diagram alur akan memberi gambaran dua dimensi berupa simbol-
simbol yang masing-masing simbol tersebut telah ditetapkan lebih dahulu fungsi dan atrinya. Dua di antara beberapa Flowchart yang menggambarkan proses dengan komputer, yaitu : 1.
Sistem Flowchart Diagram Alur Sistem (Sistem Flowchart) merupakan bagan yang menunjukkan arus pekerjaan secara keseluruhan dari sistem. Bagan ini menjelaskan urutan dari prosedurprosedur yang ada di dalam sistem.
2.
Program Flowchart Diagram Alur Program (Program Flowchart) merupakan bagan yang menjelaskan secara rinci langkah-langkah dari proses program. Pada Tebel 2.5 menunjukkan seperangkat simbol diagram alur beserta fungsi dan
manfaat yang digunakan dalam pembuatan langkah algoritma pemrograman. Tabel 2.5. Simbol-Simbol Flowchart No 1
Simbol Flowchart Start
Keterangan Simbol Komponen yang berfungsi untuk mengawali dan mengakhiri suatu proses
2
Data/Hasil
Komponen yang mewakili input dan output
3
Sub Proses
Komponen yang subproses/subprogram
4
Proses
Komponen yang menyatakan setiap hasil dari pengolahan proses.
5
Looping
Komponen yang berfunsi untuk menyatakan perulangan /melakukan berulang-ulang.
6
Decision
Komponen yang berfunsi untuk menyatakan dua kemungkinan yang bernilai True dan False.
7
Connector
Komponen yang berfungsi untuk menghubungkan halaman yang sama/one page connector, ataupun halaman yang berbeda/two page connector.
8
Alur
Komponen yang berfungsi untuk menghubungkan simbol-simbol sebagai arahnya.
menyatakan
