GRAF

Posted on Maret 25, 2010 | Tinggalkan Komentar

Graf
1. Sejarah Graf
Graf dipakai pertama kali oleh seorang matematikawan Swis pada tahun 1763 untuk memecahkan teka-teki jembatan Konigsberg. Di kota Konigsberg –Jerman Timur– terdapat sungai Pregal yang dibelah dua oleh Pulau Kneipof. Daratan yang dipisahkan oleh sungai tersebut dihubungkan oleh tujuh buah jembatan. Teka-tekinya adalah : apakah mungkin melalui ketujuh jembatan tersebut dan kembali ke tempat semula dengan masing-masing jembatan dilalui tepa satu kali ?
Sebelum Euler memodelkan masalah ini ke dalam graf dan mengemukakan solusinya, kebanyakan orang sepakat bahwa tidak mungkin kembali ke tempat semula namun mereka tidak mampu menjelaskan mengapa. Euler memodelkan daratan dengan titik yang disebut sebagai simpul dan jembatan yang menghubungkannya sebagai garis yang disebut sebagai sisi.
Jawaban Euler adalah : orang tidak mungkin melalui ketujuh jembatan tersebut masing-masing satu kali dan kembali lagi ke tempat semula jika jumlah sisi dari masing-masing simpul tidak seluruhnya genap. Atau dengan kata lain, jika masing-masing simpul memiliki jumlah sisi genap maka dengan melalui masing-masing sisi satu kali kita dapat kembali ke tempat semula. Dari gambar di atas tampak bahwa simpul-simpul dari graf pemodelan jembatan Konigsberg memiliki sisi berjumlah ganjil, jadi orang tidak mungkin kembali ke tempat semula.
2 Definisi Graf
Graf adalah struktur diskrit yang terdiri dari simpul dan sisi dimana sisi-sisi menghubungkan simpul yang ada . Graf juga didefinisikan sebagai pasangan himpunan (V,E) yang dalam hal ini :
V = himpunan tidak kosong dari simpul-simpul (vertex atau node) = {v₁,v₂,…v_n} dan
E = himpunan sisi-sisi (edges atau arcs) yang menguhubungkan sepasang simpul = {e₁,e₂,…e_n}
Atau dapat ditulis singkat notasi
G = (V,E) .
Simpul pada graf dinomori dengan huruf atau bilangan asli atau gabungan keduanya. Sedangkan sisi yang menghubungkan simpul vi dengan simpul vj dinyatakan dengan pasangan (vi,vj) atau dengan lambang e_i dimana i = himpunan bilangan asli = {1,2,3,…} .
Secara geometri graf direpresentasikan sebagai himpunan titik yang dihubungkan dengan himpunan garis dalam ruang dua dimensi.

3 Jenis-jenis Graf
Berdasarkan jenis sisinya graf digolongkan menjadi dua jenis :

1. Graf sederhana yaitu graf yang tidak memiliki sisi ganda maupun sisi loop.

2.   Graf tidak sederhana yaitu graf yang memiliki sisi ganda atau sisi loop. Graf tidak sederhana dibedakan menjadi dua :
a)     Graf ganda yaitu graf yang memiliki sisi ganda. Sisi ganda adalah sekumpulan sisi yang menghubungkan sepasang simpul yang sama. Dengan kata lain, bila sepasang simpul dihubungkan oleh lebih dari satu sisi, maka sisi-sisi itu disebut sisi ganda.
b) Graf semu yaitu graf yang memiliki sisi loop. Loop adalah sisi yang menghubungkan sebuah simpul dengan dirinya sendiri.
Berdasarkan jumlah simpul yang dimilikinya, graf juga digolongkan menjadi dua jenis:
1.      Graf berhingga (limited graph)
Graf berhingga adalah graf yang jumlah simpulnya berhingga.

1. Graf tak berhingga (unlimited graph)

Graf tak berhingga adalah graf yang jumlah simpulnya tak berhingga. Secara geometris graf tak berhingga digambarkan dengan sisi-sisi yang hanya memiliki satu simpul untuk setiap simpul luarnya. Sekilas nampak seperti graf yang belum selesai digambar.
Penggolongan lain dilakukan berdasarkan orientasi arah dari sisi-sisi graf. Ada dua jenis graf dalam penggolongan ini :
1. Graf tak berarah, yaitu graf yang sisi-sisinya tidak memiliki arah.
2. Graf Berarah, yaitu graf yang sisi-sisinya memiliki orientasi arah.
Pada graf jenis ini, sisi yang menghubungkan simpul 3 ke simpul 1 tidak sama dengan sisi yang menghubungkan simpul 1 ke simpul 3 karena orientasi arahnya berbeda.
4. Contoh Terapan Graf

1. Rangkaian listrik.

1. Isomer senyawa kimia karbon

metana (CH₄)                      etana (C₂H₆)              propana (C₃H₈)

1. graf dapat digunakan berbagai objek diskrit, terutama graf sering digunakan untuk memodelkan berbagai persoalan untuk memudahkan penyelesaiannya. Misalnya seseorang ingin menggambarkan diagram hubungan relasi kerja seorang pimpinan dengan staf-stafnya, maka sang pimpinan dapat dijadikan suatu objek diskrit (simpul/vertex), demikian juga staf-stafnya, dan akan terdapat sisi-sisi (edges) yang menghubungkan satu dan lainnya untuk menggambarkan hubungan (relationship) antara objek-objek (simpul) tadi.

Graf digunakan dalam kehidupan sehari-hari terutama untuk mendeskripsikan model persoalan dan menggambarkannya secara konkret dan jelas. Selain itu graf juga dipergunakan untuk mempermudah menyelesaikan berbagai macam persoalan-persoalan yang sulit diselesaikan dengan perhitungan dan pertimbangan biasa. Hal ini disebabkan sifat-sifat dan teori-teori yang telah dipelajari pada graf.