free download materi teori graf

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.

1. Verteks

Verteks (simpul atau titik) yang disimbolkan dengan V adalah  himpunan simpul yang terbatas dan tidak kosong. Dalam gambar a.1 , v₁, v₂, v₃, … , v₆ adalah simpul-simpul penyusun graf. Jumlah simpul pada graf dapat dinyatakan dengan n = |V|.

2. Edge

edge (sisi, busur atau rusuk) yang disimbolkan dengan E adalah himpunan rusuk yang menghubungkan sepasang simpul. Dalam gambar a.1, pada gambar b), v₁ dan v₂ dihubungkan oleh e₁ dan e₂. Dalam hal ini, e₁ dan e₂  adalah rusuk. Jumlah rusuk dam graf dinyatakan dengan m = |E|.

3. 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(v₁), d(v₂) = 2. Dalam teori graf loop dihitung 2 kali sehingga pada gambar c), d(v₁)= 4 dan d(v₂), d(v₃) = 2.

4. Size

Size (ukuran) dari suatu graf adalah banyaknya simpul yang dimiliki.

c.       Keterhubungan

1. Walk

Misalkan G suatu Graf dengan V_i dan V_j adalah 2 titik dalam G. Walk (jalan) dari V_i ke V_j adalah barisan simpul dan rusuk yang berhubungan secara bergantian, diawali dari simpul V_i  dan diakhiri simpul V_j. Simpul V_i dan V_j adalah simpul awal dan simpul akhir. Sedangkan simpul-simpul yang berada diantara V_i dan V_j adalah simpul-simpul internal.

2. Trail

Trail (jejak) adalah jalan dengan rusuk-rusuk yang berbeda atau tanpa rusuk berulang.

3. Path

Path (lintasan) adalah jalan dengan simpul dan rusuk yang berbeda atau jejak dengan simpul yang berbeda.

4. 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.

5. Cycle

Cycle adalah sebuah jejak tertutup dengan simpul awal dan semua simpul internalnya berbeda.

Contoh :

Salah satu walk dari v­₁ ke v₃ = {v₁,e₁,v₂,e₇,v₆,e₁₀,v₁,e₅,v₅,e₄,v_4,e_4,v_5,e_10,v_6,e_8,v₃}

Salah satu trail dari v­₁ ke v₄ ={v₁,e₁,v₂,e₇,v₆,e₁₀,v₁,e₅,v₅,e₄,v₄}

Salah satu path dari v­₁ ke v₄ ={ v₁,e₁,v₂,e₇,v₆,e₈,v₃,e₃,v₄}

Salah satu sirkuit dari v­₁ ke v₄ = {v₁,e₁,v₂,e₇,v₆,e₉,v₄,e₃,v₃,e₈,v₆,e₆,v₁}

Salah satu sirkuit dari v­₁ ke v₄ = {v₁,e₁,v₂,e₇,v₆,e₉,v₄,e₃,v₃,e₈,v₆,e₆,v₁}

Salah satu cycle = {v₁,e₁,v₂,e₇,v₆,e₁₀,v₁}

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, (v_i,v_j) = (v_j,v_i) 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, (v_i,v_j) dan (v_j,v_i) menyatakan dua buah busur yang berbeda, dengan kata lain (v_i,v_j) ≠ (v_j,v_i). Untuk busur (v_i,v_j) 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.