Pertemuan 4 : Teori Graf

11/02/2013 02:47:00 PM Discrete mathematics 0 Comments

Review Pembahasan : Teori graf

Makalah pertama tentang teori graf ditulis pada tahun 1736 oleh seorang matematikawan Swiss yang bernama Leonard Euler. Ia menggunakan teori graf untuk menyelesaikan masalah jembatan Königsberg (sekarang, bernama Kaliningrad).

A.) Definisi Graf

Graf merupakan struktur diskrit yang terdiri himpunan sejumlah berhingga obyek yang disebut simpul (vertices, vertex) dan himpunan sisi (edges) yang menghubungkan simpul-simpul terseut. terdiri dari dari Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut.

B.) Terminologi Graf

Ada beberapa terminologi graf yang perlu diketahui, antara lain : ketetanggaan antara dua simpul, bersisian , derajat suatu simpul, dan lain-lain.

C.) Beberapa Jenis Graf

Beberapa jenis graf tak berarah yang perlu diketahui adalah :
1. Graf sederhana (simple graph) : Graf sederhana merupakan graf tak berarah yang tidak mengandung gelang maupun sisi-ganda.

2. Graf Ganda (multigraph) : Graf ganda merupakan graf tak berarah yang tidak mengandung gelang (loop).

3. Graf semu (Pseudo graph) : Graf semu merupakan graf yang boleh mengandung gelang (loop).

4. Graf berarah (directed graph atau digraph) : Graf berarah merupakan graf yang setiap sisinya mempunyai arah dan tidak mempunyai dua sisi yang berlawanan antara dua buah simpul (tak mempunyai sisi ganda).

5. Graf ganda berarah (directed multigraph) : Graf ganda berarah merupakan graf berarah yang membolehkan adanya sisi ganda pada graf tersebut (boleh mempunyai dua sisi yang berlawanan antara dua buah simpul).

 

D.) Keterhubungan dan Sub Graf

Dua buah simpul v1 dan simpul v2 pada suatu graf dikatakan terhubung jika terdapat lintasan dari v1 ke v2. Jika setiap pasang simpul vi dan vj dalam himpunan V pada suatu graf G terdapat lintasan dari vi ke vj maka graf tersebut dinamakan graf terhubung (connected graph). Jika tidak, maka G dinamakan graf tak-terhubung (disconnected graph).

E.) Matriks Ketetanggaan (adjacency matrix) dan Matriks Bersisian (incidency matrix) dari Suatu Graf

Matriks ketetanggaan untuk graf sederhana merupakan matriks bukur sangkar yang unsur-unsurnya hanya terdiri dari dua bilangan yaitu 0 (nol) dan 1 (satu). Baris dan kolom pada matriks ini, masing-masing merupakan representasi dari setiap simpul pada graf tersebut. Matriks ketetanggaan untuk graf tak sederhana merupakan matriks bukur sangkar yang unsur-unsurnya hanya terdiri dari bilangan 0 (nol), 1 (satu) dan 2 (dua). Baris dan kolom pada matriks ini, masing-masing merupakan representasi dari setiap simpul pada graf tersebut.

F.) Lintasan dan Sirkuit Euler

Lintasan Euler dalam suatu graf merupakan lintasan yang melalui masing-masing sisi didalam graf tersebut tepat satu kali. Jika lintasan tersebut kembali kesimpul awal, sehingga membentuk lintasan tertutup (sirkuit) maka lintasan ini dinamakan sirkuit Euler. Dengan demikian, sirkuit Euler merupakan sirkuit yang melewati masing-masing sisi tepat satu kali. Graf yang memuat sirkuit Euler dinamakan graf Euler (Eulerian graph), sedangkan graf yang memuat lintasan Euler dinamakan graf semi Euler (semi-Eulerian graph).

G.) Lintasan dan Sirkuit Hamilton

Sir Wiliam Hamilton pada tahun 1859 membuat permainan dodecahedron yang ditawarkan pada pabrik mainan di Dublin. Permainan tersebut terdiri dari 12 buah pentagonal dan ada 20 titik sudut (setiap sudut diberi nama ibu kota setiap negara) . Permainan ini membentuk perjalanan keliling dunia yang mengunjungi setiap ibu kota Negara tepat satu kali dan kembali lagi ke kota asal. Ini tak lain adalah mencari sirkuit Hamilton.

H.) Graf Isomorfik dan Homeomorfik

Suatu graf dapat digambarkan dengan berbagai cara. Dua buah graf yang isomorfik adalah graf yang sama, kecuali penamaan simpul dan sisinya saja yang berbeda. Sebagai contoh dua graf diatas merupakan dua graf yang isomorfik. Dua buah graf dikatakan isomorfik jika memenuhi ketiga syarat berikut (Deo, 1989):
1. Mempunyai jumlah simpul yang sama.
2. Mempunyai jumlah sisi yang sama
3. Mempunyai jumlah simpul yang sama berderajat tertentu

I.) Aplikasi Graf

Bebarapa aplikasi dari Graf antara lain ; Lintasan Terpendek (Shortest Path), Algoritma Lintasan Terpendek Dijkstra, Persoalan Perjalanan Pedagang (Travelling Salesperson Problem - TSP), Persoalan Tukang Pos Cina (Chinese Postman Problem).

You can download the slide here :

Graph Teory