A. Definisi Graf
Secara sederhana graf didefinisikan sebagai kumpulan titik yang dihubungkan oleh garis. Secara matematis, graf adalah pasangan himpunan (V,E) dimana V adalah himpunan tak kosong yang memiliki elemen disebut simpul (vertices) dan E adalah kumpulan dari dua elemen subsets V yang disebut busur (edges).
Graf G = (V, E) yang dalam hal ini adalah:
V = Himpunan tidak kosong dari simpul – simpul (vertices)
= {v1, v2, ... , vn}
E = Himpunan sisi (edges) yang menghubungkan sepasang simpul
= {e1, e2, ... , en}
B. Jenis - jenis Graf
Graf dapat dibedakan dalam beberapa jenis, sebagai berikut:
1.Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis:
a.Graf sederhana (simple graph).
Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana.
b.Graf tak-sederhana (unsimple-graph).
Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph).
2. Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:
a. Graf berhingga (limited graph)
Graf berhingga adalah graf yang jumlah simpulnya, n, berhingga.
b. Graf tak-berhingga (unlimited graph)
Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graf tak-berhingga.
3. Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis:
a. Graf tak-berarah (undirected graph)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. Tiga buah graf pada b. Graf berarah (directed graph atau digraph)
Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah.
C. Graf Sederhana Khusus
1. Graf Sederhana (Simple Graph)
Graf sederhana adalah graf yang tidak mempunyai rusuk ganda dan atau, gelang. Pada graf sederhana, rusuk adalah pasangan tak terurut (unordered pairs) (Harju:2012). Jadi rusuk (u, v) sama dengan (v, u). Menurut Munir (2005) graf sederhana juga dapat didefinisikan sebagai G = (V, E), terdiri dari V, himpunan tidak kosong simpul-simpul dan E, himpunan pasangan tak terurut yang berbeda yang disebut rusuk. Berikut adalah contoh graf sederhana.
Menurut Siang (2002) beberapa graf sederhana khusus yang sering digunakan adalah sebagai berikut.
a. Graf Lengkap (Complete Graph)
Graf lengkap adalah graf sederhana yang setiap dua simpulnya bertetangga. Graf lengkap dengan n buah simpul dilambangkan dengan Kn. Setiap simpul pada Kn berderajat n – 1. Banyaknya rusuk pada graf lengkap yang terdiri dari n buah simpul adalah n(n – 1)/2.
b. Graf Lingkaran
Graf lingkaran adalah graf sederhana yang setiap simpulnya berderajat dua. Graf lingkaran dengan n simpul dilambangkan dengan Cn.
c. Graf Teratur (Regular Graph)
Graf teratur adalah graf yang setiap simpulnya mempunyai derajat yang sama. Apabila derajat setiap simpul adalah r, maka graf tersebut disebut sebagai graf teratur derajat r.
d. Graf Bipartit (Bipartite Graph)
Graf G yang himpunan simpulnya dapat dikelompokkan menjadi dua himpunan bagian V1 dan V2, sedemikian sehingga setiap rusuk di dalam G menghubungkan sebuah simpul di V1 ke sebuah simpul di V2 disebut graf bipartit dan dinyatakan sebagai G (V1, V2).
D. Representasi Graf
1. Matriks Ketetanggaan (adjacency matrix)
Matrik ketegangan adalah refresetasi graf yang paling umum. Misalkan G= (V,E) adalah graf dengan n simpul, n ≥ 1. Matriks ketetanggaan adalah G adalah matriks yang berukuran n x n. bila matriks tersebut di namakan A = [aij], maka aij = {1, jika simpul i dan j bertetangga, sebaliknya aij = 0 jika simpul i dan j tidak bertetangga. Karena matriks ketetanggaan hanya berisi 0 dan 1, maka matriks tersebut dinamakan juga matriks nol-satu (zero-one). Selain angka 0 dan 1, element matrik dapat juga dinyatakan dengan nilai false (menyatakan 0) dan true menyantakan 1). Matriks ketetanggaan di dasarkan pada pngurutan nomor simpul.
2. Matriks Bersisian (incidency matrix)
Bila matriks ketetanggaan menyatakan ketetanggaan simpul-simpul di dalam graf, maka matriks bersisian menyatakan kebersisian simpul dengan sisi. Misalnya G=(V,E) adalah graf dengan n simpul m buah sisi. Matriks bersisian G adalah matriks dwimatra yang berukuran n × m. baris menunjukkan label simpul, sedangkan kolom menunjukkan label sisinya. Bila matriks tersebut di namakan A = [aij], maka aij = 1, jika simpul i bersisian dengan sisi j maka aij = 0, jika simpul i tidak bersisian dengan sisi
E. Chinese Postman Problem
Chinese postman problem menjelaskan bagaimana memecahkan postman problem untuk tiap graf G, yang mana sisinya tidak memiliki arah tertentu.
Ada dua kasus yang harus ditangani secara terpisah.
1. Graf genap
2. Graf ganjil
Secara sederhana graf didefinisikan sebagai kumpulan titik yang dihubungkan oleh garis. Secara matematis, graf adalah pasangan himpunan (V,E) dimana V adalah himpunan tak kosong yang memiliki elemen disebut simpul (vertices) dan E adalah kumpulan dari dua elemen subsets V yang disebut busur (edges).
Graf G = (V, E) yang dalam hal ini adalah:
V = Himpunan tidak kosong dari simpul – simpul (vertices)
= {v1, v2, ... , vn}
E = Himpunan sisi (edges) yang menghubungkan sepasang simpul
= {e1, e2, ... , en}
B. Jenis - jenis Graf
Graf dapat dibedakan dalam beberapa jenis, sebagai berikut:
1.Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis:
a.Graf sederhana (simple graph).
Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana.
b.Graf tak-sederhana (unsimple-graph).
Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph).
2. Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:
a. Graf berhingga (limited graph)
Graf berhingga adalah graf yang jumlah simpulnya, n, berhingga.
b. Graf tak-berhingga (unlimited graph)
Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graf tak-berhingga.
3. Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis:
a. Graf tak-berarah (undirected graph)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. Tiga buah graf pada b. Graf berarah (directed graph atau digraph)
Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah.
C. Graf Sederhana Khusus
1. Graf Sederhana (Simple Graph)
Graf sederhana adalah graf yang tidak mempunyai rusuk ganda dan atau, gelang. Pada graf sederhana, rusuk adalah pasangan tak terurut (unordered pairs) (Harju:2012). Jadi rusuk (u, v) sama dengan (v, u). Menurut Munir (2005) graf sederhana juga dapat didefinisikan sebagai G = (V, E), terdiri dari V, himpunan tidak kosong simpul-simpul dan E, himpunan pasangan tak terurut yang berbeda yang disebut rusuk. Berikut adalah contoh graf sederhana.
Menurut Siang (2002) beberapa graf sederhana khusus yang sering digunakan adalah sebagai berikut.
a. Graf Lengkap (Complete Graph)
Graf lengkap adalah graf sederhana yang setiap dua simpulnya bertetangga. Graf lengkap dengan n buah simpul dilambangkan dengan Kn. Setiap simpul pada Kn berderajat n – 1. Banyaknya rusuk pada graf lengkap yang terdiri dari n buah simpul adalah n(n – 1)/2.
b. Graf Lingkaran
Graf lingkaran adalah graf sederhana yang setiap simpulnya berderajat dua. Graf lingkaran dengan n simpul dilambangkan dengan Cn.
c. Graf Teratur (Regular Graph)
Graf teratur adalah graf yang setiap simpulnya mempunyai derajat yang sama. Apabila derajat setiap simpul adalah r, maka graf tersebut disebut sebagai graf teratur derajat r.
d. Graf Bipartit (Bipartite Graph)
Graf G yang himpunan simpulnya dapat dikelompokkan menjadi dua himpunan bagian V1 dan V2, sedemikian sehingga setiap rusuk di dalam G menghubungkan sebuah simpul di V1 ke sebuah simpul di V2 disebut graf bipartit dan dinyatakan sebagai G (V1, V2).
D. Representasi Graf
1. Matriks Ketetanggaan (adjacency matrix)
Matrik ketegangan adalah refresetasi graf yang paling umum. Misalkan G= (V,E) adalah graf dengan n simpul, n ≥ 1. Matriks ketetanggaan adalah G adalah matriks yang berukuran n x n. bila matriks tersebut di namakan A = [aij], maka aij = {1, jika simpul i dan j bertetangga, sebaliknya aij = 0 jika simpul i dan j tidak bertetangga. Karena matriks ketetanggaan hanya berisi 0 dan 1, maka matriks tersebut dinamakan juga matriks nol-satu (zero-one). Selain angka 0 dan 1, element matrik dapat juga dinyatakan dengan nilai false (menyatakan 0) dan true menyantakan 1). Matriks ketetanggaan di dasarkan pada pngurutan nomor simpul.
2. Matriks Bersisian (incidency matrix)
Bila matriks ketetanggaan menyatakan ketetanggaan simpul-simpul di dalam graf, maka matriks bersisian menyatakan kebersisian simpul dengan sisi. Misalnya G=(V,E) adalah graf dengan n simpul m buah sisi. Matriks bersisian G adalah matriks dwimatra yang berukuran n × m. baris menunjukkan label simpul, sedangkan kolom menunjukkan label sisinya. Bila matriks tersebut di namakan A = [aij], maka aij = 1, jika simpul i bersisian dengan sisi j maka aij = 0, jika simpul i tidak bersisian dengan sisi
E. Chinese Postman Problem
Chinese postman problem menjelaskan bagaimana memecahkan postman problem untuk tiap graf G, yang mana sisinya tidak memiliki arah tertentu.
Ada dua kasus yang harus ditangani secara terpisah.
1. Graf genap
2. Graf ganjil
1. Graf Genap
Bagaimana caranya kita dapat menemukan jalur euler untuk graf G yang di mulai dari simpul a? ikuti sisi yang bersinggungan degan a dan teruskan sampai bertemu kembali dengan simpul a. pada simpul yang dilewati kurva tersebut, ambil simpul yang belum mati(masih meliki sisi yang belum di lewati) lakukan penelusuran dari simpul tersebut terhadap sisi yang belum dilewati sampai bertemu dengan sisi awalnya, ulangi sampai semua simpul mati. Maka akan terbentuk kurva-kurva tertutup C1, C2, C3, …,CN. Kemudian sambungkan tiap-tiap kurva yang diperoleh sehingga membentuk suatu kurva yang kontinu C dan melewati semua sisi-sisi pada graf G. maka di dapatlah jalur R dimana R = C yang melewati semua sisi pada graf G tepat sekali sehingga merupakan jalur euler yang merupakan solusi optimal.
Sebagai contoh, pada graf pada gambar 3 kita akan mulai pada simpul a, kemudian lanjutkan ke simpul b , c, f, i, h, g, d, a. masih terdapat simpul yang belum mati pada kurva abcfihgda,yaitu simpul b, e, f, h, d. kita akan memulai kembali pada simpul d (dipilih secara acak, tidak perlu menggunakan algoritma khusus), sampai katakanlah terbentuk kurva debd dan masih ada simpul yang belum mati yaitu e, f, h. kita akan memulai lagi pada e sehingga membentuk kurva efhe. Maka didapat tiga buah kurva
tertutup
C1 = abcfihgda
C2 = debd
C3 = efhe
Untuk menyambungkan ketiga kurva ini, harus dicari simpul yang sama pada tiap-tiap kurva. Jika ketiga kurva diatas disambung maka akan terdapat beberapa kemungkinan kurva baru
• abdebcfhefihgda
• abcfhefihgdebda
• abcfhebdefihgda
• dll tidak perlu bingung semua kurva tersebut sama-sama
optimal karena merupakan jalur euler.
Bagaimana caranya kita dapat menemukan jalur euler untuk graf G yang di mulai dari simpul a? ikuti sisi yang bersinggungan degan a dan teruskan sampai bertemu kembali dengan simpul a. pada simpul yang dilewati kurva tersebut, ambil simpul yang belum mati(masih meliki sisi yang belum di lewati) lakukan penelusuran dari simpul tersebut terhadap sisi yang belum dilewati sampai bertemu dengan sisi awalnya, ulangi sampai semua simpul mati. Maka akan terbentuk kurva-kurva tertutup C1, C2, C3, …,CN. Kemudian sambungkan tiap-tiap kurva yang diperoleh sehingga membentuk suatu kurva yang kontinu C dan melewati semua sisi-sisi pada graf G. maka di dapatlah jalur R dimana R = C yang melewati semua sisi pada graf G tepat sekali sehingga merupakan jalur euler yang merupakan solusi optimal.
Sebagai contoh, pada graf pada gambar 3 kita akan mulai pada simpul a, kemudian lanjutkan ke simpul b , c, f, i, h, g, d, a. masih terdapat simpul yang belum mati pada kurva abcfihgda,yaitu simpul b, e, f, h, d. kita akan memulai kembali pada simpul d (dipilih secara acak, tidak perlu menggunakan algoritma khusus), sampai katakanlah terbentuk kurva debd dan masih ada simpul yang belum mati yaitu e, f, h. kita akan memulai lagi pada e sehingga membentuk kurva efhe. Maka didapat tiga buah kurva
tertutup
C1 = abcfihgda
C2 = debd
C3 = efhe
Untuk menyambungkan ketiga kurva ini, harus dicari simpul yang sama pada tiap-tiap kurva. Jika ketiga kurva diatas disambung maka akan terdapat beberapa kemungkinan kurva baru
• abdebcfhefihgda
• abcfhefihgdebda
• abcfhebdefihgda
• dll tidak perlu bingung semua kurva tersebut sama-sama
optimal karena merupakan jalur euler.
2. Graf Ganjil
Graf G bukanlah graf genap, karena jumlah sisi yang masuk pada suatu simpul harus sama sengan jumlah sisi yang keluar dari simpul tersebut, akibatnya jika ada sisi yang meiliki simpul ganjil maka simpul ini harus melewati setidaknya satu sisi yang sama dua kali. Jika terdapat sejumlah ganjil sisi simpul yang ganjil maka akan terdapat sejumlah ganjil pula sisi yang harus diulangi. Begitu juga jika terdapat sejumlah genap simpul yang ganjil maka akan terdapat sejumlah genap simpul yang harus di ulangi(nol juga bilangan genap).
Graf G bukanlah graf genap, karena jumlah sisi yang masuk pada suatu simpul harus sama sengan jumlah sisi yang keluar dari simpul tersebut, akibatnya jika ada sisi yang meiliki simpul ganjil maka simpul ini harus melewati setidaknya satu sisi yang sama dua kali. Jika terdapat sejumlah ganjil sisi simpul yang ganjil maka akan terdapat sejumlah ganjil pula sisi yang harus diulangi. Begitu juga jika terdapat sejumlah genap simpul yang ganjil maka akan terdapat sejumlah genap simpul yang harus di ulangi(nol juga bilangan genap).
Jika kita menelusuri sisi berulang yang keluar dari simpul ganjil maka perjalanan sisi yang berulang ini akn berakhir di sisi yang ganjil yang lain. Jadi awal dan akhir jalur sisi-sisi yang di ulang adalah simpul-simpul yang ganjil. Tentu saja dalam perjalanannya dapat melewati sejumlah simpul-simpul yang genap sebagai perantara. Pertanyaannya adalah mana simpul ganjil yang akan dihubungkan oleh jalur sisi-sisi yang diulangi, dan bagaimana konfigurasi dari sisi-sisi pembentuk jalur tersebut. Dengan menggunakan metoda branch and bound, kita dapat meenukan jalur terpendek untuk menghubungkan simpul-simpul yang ganjil, simpul simpul yang tidak ganil dapat diperlakukan seperti halnya graf genap.
F. Pewarnaan Graf
Mewarnai sebuah graph berarti memberi warna pada setiap titik graph, sedemikian hingga titik yang berdekatan mendapat warna berbeda. Menanyakan banyak minimum gerbong kereta yang diperlukan pada contoh 1 adalah sama seperti menanyakan banyak minimum warna yang diperlukan untuk mewarnai graph. Bila suatu sikel memiliki titik yang banyaknya ganjil maka harus digunakan tiga warna.
G. Graf Isomorfik
Dua buah graf yang sama tetapi secara geometri berbeda disebut graf yang saling isomorfik. Dua buah graf G1 dan G2 dikatakan isomorfik jika terdapat korespondesi satu - satu antara simpul - simpul keduanya dan antara sisi - sisi keduanya sedemikian sehingga jika sisi e bersisian dengan simpul u dan v di G1, maka sisi e yang berkorespon di G2 juga harus bersisian dengan simpul u dan v di G2.
Dengan kata lain misalkan sisi e bersisian dengan simpul u dan v di G1, maka sisi e yang berkorespondensi di G2 harus bersisian dengan simpul u dan v di G2.
Dua buah graf yang isomorfik adalah graf yang sama kecuali penamaan simpul dan sisinya saja yang berbeda.
H. Graf Planar (Planar Graph) dan Graf Bidang (Plane Graph)
Graf yang dapat digambarkan pada bidang datar dengan sisi-sisi tidak saling memotong disebut sebagai graf planar, jika tidak ia disebut graf tak-planar.
Rumus Euler:
n – e + f = 2
Keterangan:
f = jumlah wilayah
e = jumlah sisi
n = jumlah simpul
I. Teorema Kuratowski
Teorema kuratowski adalah teorema untuk menentukan keplanaran suatu graf. Sesuai dengan konsep graf planar yaitu: “Graf G bersifat planar jika dan hanya jika ia tidak mengandung subgraf yang sama dengan salah satu graf kuratowski atau homomorfis dengan salah satunya”
Teorema graf kuratowski memiliki sifat, yaitu:
1. Kedua graf kuratowski adalah graf teratur.
2. Kedua graf kuratowski adalah graf non-planar.
3. Penghapusan sisi atau simpul dari graf kuratowski menyebabkan menjadi graf planar.
F. Pewarnaan Graf
Mewarnai sebuah graph berarti memberi warna pada setiap titik graph, sedemikian hingga titik yang berdekatan mendapat warna berbeda. Menanyakan banyak minimum gerbong kereta yang diperlukan pada contoh 1 adalah sama seperti menanyakan banyak minimum warna yang diperlukan untuk mewarnai graph. Bila suatu sikel memiliki titik yang banyaknya ganjil maka harus digunakan tiga warna.
G. Graf Isomorfik
Dua buah graf yang sama tetapi secara geometri berbeda disebut graf yang saling isomorfik. Dua buah graf G1 dan G2 dikatakan isomorfik jika terdapat korespondesi satu - satu antara simpul - simpul keduanya dan antara sisi - sisi keduanya sedemikian sehingga jika sisi e bersisian dengan simpul u dan v di G1, maka sisi e yang berkorespon di G2 juga harus bersisian dengan simpul u dan v di G2.
Dengan kata lain misalkan sisi e bersisian dengan simpul u dan v di G1, maka sisi e yang berkorespondensi di G2 harus bersisian dengan simpul u dan v di G2.
Dua buah graf yang isomorfik adalah graf yang sama kecuali penamaan simpul dan sisinya saja yang berbeda.
H. Graf Planar (Planar Graph) dan Graf Bidang (Plane Graph)
Graf yang dapat digambarkan pada bidang datar dengan sisi-sisi tidak saling memotong disebut sebagai graf planar, jika tidak ia disebut graf tak-planar.
Rumus Euler:
n – e + f = 2
Keterangan:
f = jumlah wilayah
e = jumlah sisi
n = jumlah simpul
I. Teorema Kuratowski
Teorema kuratowski adalah teorema untuk menentukan keplanaran suatu graf. Sesuai dengan konsep graf planar yaitu: “Graf G bersifat planar jika dan hanya jika ia tidak mengandung subgraf yang sama dengan salah satu graf kuratowski atau homomorfis dengan salah satunya”
Teorema graf kuratowski memiliki sifat, yaitu:
1. Kedua graf kuratowski adalah graf teratur.
2. Kedua graf kuratowski adalah graf non-planar.
3. Penghapusan sisi atau simpul dari graf kuratowski menyebabkan menjadi graf planar.
J. Dual Graf
Dual graf dapat dikatakan apabila sebuah graf planar G yang direpresentasikan dalam graf bidang mempunyai graf G yang secara geometris merupakan dual dari graf planar G.
0 Comments:
Posting Komentar