Teori graf adalah salah satu mata kuliah jurusan matematika, matakuliah ini biasanya di ambil semester 3.
bagi temen-temen yang belum mempunyai materi tentang teori graf dapat di download di link berikut ini.
kilk disni
"rangga pradeka"
TEORI GRAF DAN APLIKASINYA
a. Definisi
Secara informal, suatu graf adalah himpunan benda-benda yang disebut verteks (atau node) yang terhubung oleh sisi (atau edge atau arc). Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graf adalah dengan menuyatakan objek dinyatakan sebagai noktah, bulatan, atau titik, sedangkan hubungan antara objek dinyatakan dengan garis.
Secara formal, Graf G didefinisikan sebagai pasangan himpunan (V, E), yang dalam hal ini:
- V = himpunan tidak-kosong dari simpul-simpul (vertices atau node) = { v1 , v2 , ... , vn }
- E = himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul = {e1 , e2 , ... , en}
atau dapat ditulis singkat notasi G = (V, E).
Definisi diatas menyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Jadi, sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpulnya harus ada, minimal satu. Graf yang hanya mempunyai satu buah simpul tanpa sebuah sisi pun dinamakan graf trivial. Sedangkan garis yang hanya berhubungan dengan satu simpul disebut loop.
b. Komponen-komponen graf
Ada beberapa terminologi dari teori graf yang digunakan untuk menjelaskan apa yang dilihat ketika melihat suatu graf. Graf dapat dilihat dari komponen-komponen penyusunnya.
- Verteks
Verteks (simpul atau titik) yang disimbolkan dengan V adalah himpunan simpul yang terbatas dan tidak kosong. Dalam gambar a.1 , v1, v2, v3, … , v6 adalah simpul-simpul penyusun graf. Jumlah simpul pada graf dapat dinyatakan dengan n = |V|.
- Edge
edge (sisi, busur atau rusuk) yang disimbolkan dengan E adalah himpunan rusuk yang menghubungkan sepasang simpul. Dalam gambar a.1, pada gambar b), v1 dan v2 dihubungkan oleh e1 dan e2. Dalam hal ini, e1 dan e2 adalah rusuk. Jumlah rusuk dam graf dinyatakan dengan m = |E|.
- Degree
Degree (derajat) suatu simpul yang disimbolkan dengan d(v) adalah jumlah rusuk yang berada pada simpul tersebut. Dalam gambar a.1, pada gambar b), d(v1), d(v2) = 2. Dalam teori graf loop dihitung 2 kali sehingga pada gambar c), d(v1)= 4 dan d(v2), d(v3) = 2.
- Size
Size (ukuran) dari suatu graf adalah banyaknya simpul yang dimiliki.
c. Keterhubungan
- Walk
Misalkan G suatu Graf dengan Vi dan Vj adalah 2 titik dalam G. Walk (jalan) dari Vi ke Vj adalah barisan simpul dan rusuk yang berhubungan secara bergantian, diawali dari simpul Vi dan diakhiri simpul Vj. Simpul Vi dan Vj adalah simpul awal dan simpul akhir. Sedangkan simpul-simpul yang berada diantara Vi dan Vj adalah simpul-simpul internal.
- Trail
Trail (jejak) adalah jalan dengan rusuk-rusuk yang berbeda atau tanpa rusuk berulang.
- Path
Path (lintasan) adalah jalan dengan simpul dan rusuk yang berbeda atau jejak dengan simpul yang berbeda.
- Sirkuit
Sirkuit adalah Jejak tertutup. Jejak tertutup adalah jejak dengan simpul awal dan simpul akhir sama.
a. Sirkuit Euler
Sirkuit Euler adalah sirkuit dimana setiap simpul dalam G yang muncul paling sedikit sekali dan setiap rusuk dalam G muncul tepat satu kali.
b. Sirkuit Hamilton
Sirkuit Hamilton adalah sirkuit dimana setiap simpul dalam G yang dilalui tepat satu kali dan setiap garis dalam G tidak harus dilalui.
- Cycle
Cycle adalah sebuah jejak tertutup dengan simpul awal dan semua simpul internalnya berbeda.
Contoh :
Salah satu walk dari v1 ke v3 = {v1,e1,v2,e7,v6,e10,v1,e5,v5,e4,v4,e4,v5,e10,v6,e8,v3}
Salah satu trail dari v1 ke v4 ={v1,e1,v2,e7,v6,e10,v1,e5,v5,e4,v4}
Salah satu path dari v1 ke v4 ={ v1,e1,v2,e7,v6,e8,v3,e3,v4}
Salah satu sirkuit dari v1 ke v4 = {v1,e1,v2,e7,v6,e9,v4,e3,v3,e8,v6,e6,v1}
Salah satu sirkuit dari v1 ke v4 = {v1,e1,v2,e7,v6,e9,v4,e3,v3,e8,v6,e6,v1}
Salah satu cycle = {v1,e1,v2,e7,v6,e10,v1}
d. Jenis-Jenis Graf
Pengelompokan graf dapat dipandang berdasarkan ada tidaknya sisi ganda atau sisi kalang, berdasarkan jumlah simpul, atau berdasarkan orientasi arah pada sisi.
1. Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:
a. Graf sederhana (simple graph).
Graf yang tidak mengandung loop maupun rusuk paralel.
b. Graf tak-sederhana (unsimple-graph).
Graf yang mengandung loop atau rusuk paralel Ada dua macam graf tak-sederhana, yaitu
1). Graf Ganda (multigraph)
Graf ganda adalah graf yang mengandung rusuk paralel
2). Graf Semu (pseudograph).
Graf semu adalah graf yang mengandung loop.
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.
3. Berdasarkan orientasi arah pada rusuk, 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. Pada graf tak-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan.
Jadi, (vi,vj) = (vj,vi) adalah sisi yang sama.
c. Graf berarah (directed graph atau digraph)
Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Pada graf berarah, (vi,vj) dan (vj,vi) menyatakan dua buah busur yang berbeda, dengan kata lain (vi,vj) ≠ (vj,vi). Untuk busur (vi,vj) simpul vj dinamakan simpul asal (initial vertex) dan simpul vk dinamakan simpul terminal (terminal vertex).
e. Permasalahan Optimasi
1. Penyelesaian Masalah Optimasi
Secara umum, penyelesaian masalah pencarian jalur terpendek dapat dilakukan dengan menggunakan dua metode, yaitu metode konvensional dan metode heuristik. Metode konvensional diterapkan dengan perhitungan matematis biasa, sedangkan metode heuristik diterapkan dengan perhitungan kecerdasan buatan.
1. Metode Konvensional
Metode konvensional adalah metode yang menggunakan perhitungan matematis biasa. . Ada beberapa metode konvensional yang biasa digunakan untuk melakukan pencarian jalur terpendek, diantaranya: algoritma Djikstraa, algoritma Floyd-Warshall, dan algoritma Bellman-Ford
2. Metode Heuristik
Metode Heuristik adalah sub bidang dari kecerdasan buatan yang digunakan untuk melakukan pencarian dan optimasi. Ada beberapa algoritma pada metode heuristik yang biasa digunakan dalam permasalahan optimasi, diantaranya algoritma genetika, algoritma semut, logika fuzzy, jaringan syaraf tiruan, pencarian tabu, simulated annealing, dan lain-lain.
2. Permasalahan Jalur Terpendek (Shortest Path Problem)
Jalur terpendek adalah suatu jaringan pengarahan perjalanan dimana sesorang pengarah jalan ingin menentukan jalur terpendek antara dua kota, berdasarkan beberapa jalur alternatif yang tersedia, dimana titik tujuan hanya satu.
Gambar e.2 Graf ABCDEFG
Pada gambar diatas, misalkan kita dari kota A ingin menuju Kota G. Untuk menuju kota G, dapat dipilih beberapa jalur yang tersedia :
A → B → C → D → E → G
A → B → C → D → F → G
A → B → C → D → G
A → B → C → F → G
A → B → D → E → G
A → B → D → F → G
A → B → D → G
A → B → E → G
A → C → D → E → G
A → C → D → F → G
A → C → D → G
A → C → F → G
Berdasarkan data diatas, dapat dihitung jalur terpendek dengan mencari jarak antara jalur-jalur tersebut. Apabila jarak antar jalur belum diketahui, jarak dapat dihitung berdasarkan koordinat kota-kota tersebut, kemudian menghitung jalur terpendek yang dapat dilalui.