Definisi Graf
Graf adalah kumpulan simpul (nodes) yang dihubungkan satu sama lain melalui sisi/busur (edges) (Zakaria, 2006). Suatu Graf G terdiri dari dua himpunan yaitu himpunan V dan himpunan E.
a. Himpunan V yang elemennya disebut simpul atau titik, atau vertex, atau point, atau nodes yang terbatas dan tidak kosong
b. Himpunan E yang merupakan pasangan tak terurut dari simpul, disebut ruas atau rusuk, atau sisi, atau edge, atau line.
Simpul-simpul pada graf dapat merupakan obyek sembarang seperti kota, atom-atom suatu zat, nama anak, jenis buah, komponen alat elektronik dan sebagainya. Sisi graf dapat menunjukkan hubungan (relasi) sembarang seperti rute penerbangan, jalan raya, sambungan telepon, ikatan kimia, dan lain-lain.
Notasi graf: G(V,E) artinya graf G memiliki V simpul dan E sisi. Banyaknya simpul (anggota V) disebut orde Graf G, sedangkan banyaknya sisi (anggota E) disebut derajat/ukuran (size) Graf G.
Contoh: 
Perhatikan gambar tersebut, graf G1, G2 dan G3
G1 adalah graf dengan simpul di V dan himpunan sisi E adalah :
V = {1,2,3,4}
E = {(1,2), (1,3), (2,3), (2,4), (3,4)}
G2 adalah graf dengan himpunan simpul V dan dan himpunan sisi E adalah :
V = {1,2,3,4}
E = {(1,2), (2,3), (1,3), (1,3), (2,4), (3,4), (3,4)}
= {e1,e2,e3,e4,e5,e6,e7}
G3 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3) }
= { e1, e2, e3, e4, e5, e6, e7, e8}
· Pada G2, sisi e3 = (1, 3) dan sisi e4 = (1, 3) dinamakan sisi berganda atau sisi sejajar (multiple edges atau paralel edges), karena kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul 1 dan simpul 3.
· Pada G3, sisi e8 = (3, 3) dinamakan gelung atau self-loop karena ia berawal dan berakhir pada simpul yang sama.
· Pada graf, apabila ada simpul yang tidak ada sisi yang menghubungkannya dengan simpul lain dinamakan simpul terasing.
II.2 Jenis-Jenis Graf
· Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis:
1. Graf sederhana (simple graf).
Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana. Contoh: G (V,E) dengan;
V= {1,2,3,4}
E= {(1,2), (1,3), (2,3), (2,4), (3,4)}
2. Graf tak-sederhana (multigraf / unsimple-graf).
Graf yang mengandung sisi ganda atau gelung (loop) dinamakan graf tak-sederhana (unsimple graf atau multigraf).
Graf ini dibedakan menjadi dua yaitu:
Ø Multigraf (graf ganda) yaitu graf yang memiliki sisi ganda. Sisi ganda adalah sekumpulan sisi yang menghubungkan sepasang simpul yang sama bisa lebih dari dua buah sisi.
Contoh: 
G (V,E) dengan;
G (V,E) dengan;V = {1,2,3,4}
E = { (1,2), (2,3), (1,3), (1,3), (2,4), (3,4), (3,4)}
= {e1,e2,e3,e4,e5,e6,e7}
atau graf G dengan G({1,2,3,4},{e1,e2,e3,e4,e5,e6,e7})
Ø Speudograf (graf semu) yaitu graf yang memiliki sisi loop atau mengandung gelung. Loop adalah sisi yang menghubungkan sebuah simpul dengan dirinya sendiri.
Contoh: G (V,E) dengan;V= {1,2,3,4}
E= { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3) }
= { e1, e2, e3, e4, e5, e6, e7, e8}
Atau graf G dengan G({1,2,3,4},{ e1, e2, e3, e4, e5, e6, e7, e8})
· Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis:
1. Graf tak-berarah (undirected graf)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah.
2. Graf berarah (directed graf atau digraf)
Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah.
Pada Gambar disamping merupakan graf dengan simpul adalah sub-sub program p1, p2, p3, p4, dan p5. Dan edge {pi, pj} menyatakan dua sub program pi dan pj yang menggunakan data yang bersama.
Contoh: Graf berarahPada gambar disamping merupakan graf dengan verteks/simpul adalah gardu transfataumatatau aliran listrik g1, g2, g3, g4, dan g5. Dan edge/sisi (gi, gj) menyatakan aliran listrik mengalir dari gardu gi ke gardu gj.
· Berdasarkan bobotnya (weighted) pada graf dibedakan menjadi dua jenis graf yaitu:
1. Graf tak-berbobot (non-weighted graph)
Suatu graf (baik berarah atau tak-berarah, sederhana atau tak-sederhana) yang sisi/edge-nya tidak memilika label bilangan riil. Dan dianggap berbobot satu.2. Graf berbobot (weighted graph)
Suatu graf (baik berarah atau tak-berarah, sederhana atau tak-sederhana) yang setiap sisinya diberikan label bobot bilangan riil.
 |  | ||
II.3 Graf Planar
Suatu gambar graf yang digambar dalam suatu bidang dengan edge/sisi satu dengan lainnya tidak saling memotong. Suatu graf dapat digambarkan dalam beberapa macam bentuk.
|
Suatu graf planar dapat juga mempunyai gambar graf yang memuat edge-edge yang saling berpotongan. Akan tetapi grafnya tetap planar. Untuk menunjukkan bahwa suatu graf planar, cukup ditunjukkan representasi planar dari graf tersebut.
Contoh:
Tunjukkan bahwa graf G=({a, b, c, d, e, f, g, h}, E) merupakan graf planar?Dimana hinpunan edge E = {{a,b}, {a,d}, {a,e}, {b,c}, {b,f}, {c,d}, {c,g}, {d,h}{e,f},{e,h},{f,g},{g,h}}.
Graf G dapat dinyatakan dalam bentuk gambar (a) dan gambar (b). Dalam representasi pada Gambar (b) tidak ada edge-edge yang saling berpotongan. Oleh karena itu, graf G merupakan graf planar. Contoh:
Graf lengkap Kn adalah suatu graf sederhana dengan n verteks dan setiap pasang verteks dihubungkan dengan sebuah edge. Derajat pada setiap verteks adalah n-1.Perisalah apakah graf lengkap (complete graph) K1, K2, K3, K4, K5 seperti pada Gambar diatas merupakan graf planar?.
Penyelesaian:
Terlihat pada gambar (a), (b), dan (c) bahwa pada graf lengkap K1, K2, K3 merupakan graf planar karena tidak ada edge-edge yang berpotongan pada ketiga graf tersebut.Sedangkan untuk graf lengkap K4 dapat dirubah menjadi gambar graf untuk K4 seperti berikut ini yang merupakan representasi planarnya.
Untuk graf lengkap K5 bukan merupakan graf planar.
Oleh karena masih ada edge-edge/sisi-sisi yang berpotongan sehingga graf lengkap K5 tidak planar, begitu juga untuk graf lengkap Kn ( dengan n ≥ 5 ) bukan merupakan graf planar.
II.4 Graf Euler dan Graf Hamilton
1. Graf Euler
· Lintasan Euler pada suatu graf G adalah suatu lintasan yang melewati setiap edge pada graf G tepat satu kali.
· Sirkuit Euler pada suatu graf G adalah suatu sirkuit yang melewati setiap edge pada graf G tepat satu kali.
Lintasan Euler melewati setiap edge dari graf tepat satu kali. Bila lintasan Euler tersebut kembali ke verteks asal maka lintasan tertutup tersebut dinamakan sirkuit Euler. Graf yang mempunyai sirkuit Euler disebut graf Euler (Eulerian graf). Sedangkan graf G hanya memiliki lintasan Euler dinamakan graf semi-Euler (semi-Eulerian graf).
Contoh:
Perhatikan gambar di bawah ini. Setiap graf yang berada pada gambar tersebut merupakan graf semi Euler, yaitu hanya terdapat lintasan Euler.
Untuk graf pada gambar (a), salah satu lintasan Eulernya adalah: c-a-b-c-e-b-d-e. Dan graf ini tidak memiliki sirkuit Euler.
Untuk graf pada gambar (b), salah satu lintasan Eulernya adalah: c-a-b-c-e-b-d-e-f-d. Dan graf ini juga tidak memiliki sirkuit Euler.
Contoh:
Perhatikan gambar di bawah ini. Setiap graf yang berada pada gambar tersebut merupakan graf Euler, yaitu terdapat sirkuit Euler.
Untuk graf pada gambar (a), salah satu sirkuit Eulernya adalah: a-b-c-d-e-c-a.
Sedangkan untuk graf pada Gambar (b), salah satu lintasan Eulernya adalah: a-b-c-e-b-d-e-f-d-c-a.
Syarat cukup dan perlu keberadaan lintasan Euler maupun sirkuit Euler dalam suatu graf ternyata sangat sederhana. Euler menemukan syarat tersebut untuk memecahkan masalah jembatan Konigsberg (1736) yang dinyatakan dalam teorema yaitu:
v Teorema 1.1. Jika suatu graf tak berarah terhubung G terdapat sirkuit Euler maka setiap verteks di dalam graf G tersebut berderajat genap.
v Teorema 1.2. Jika setiap verteks di dalam suatu graf tak berarah terhubung G berderajat genap maka pada graf G terdapat sirkuit Euler.
v Teorema 1.3. Untuk suatu graf tak berarah terhubung G merupakan graf semi Euler (terdapat lintasan Euler) jika dan hanya jika di dalam graf G tersebut terdapat tepat dua verteks berderajat ganjil.
v Teorema 1.4. Graf berarah terhubung G memiliki sirkuit Euler jika dan hanya jika G terhubung dan setiap verteks memiliki derajat-masuk dan derajat-keluar sama. G memiliki lintasan Euler jika dan hanya jika G terhubung dan setiap verteks memiliki derajat masuk dan derajat-keluar sama kecuali dua verteks, yang pertama memiliki derajat keluar satu lebih besar derajat-masuknya, dan yang kedua memiliki derajat masuk satu lebih besar dari derajat-keluarnya.
2. Graf Hamilton
· Lintasan Hamilton pada suatu graf G adalah suatu lintasan yang melewati setiap verteks graf G tepat satu kali.
· Sirkuit Hamilton pada suatu graf G adalah suatu sirkuit yang melewati setiap edge pada graf G tepat satu kali.
Apabila dalam lintasan Hamilton verteks awal sama dengan verteks akhir, lintasan tersebut menjadi tertutup dan dinamakan sikuit Hamilton. Graf yang memiliki sirkuit Hamilton dinamakan graf Hamilton, sedangkan graf yang hanya memiliki lintasan Hamilton disebut graf semi-Hamilton.
Contoh:
Gambar (a), adalah graf yang memiliki lintasan Hemilton (misal: 3-2-1-4)
Gambar (b), adalah graf yang memiliki sirkuit Hemilton (misal: 1-2-3-4-1)
Gambar (c), adalah graf yang tida memiliki lintasan dan sirkuit Hemilton.
v Teorema 2.1. Jika graf G merupakan graf sederhana dengan n buah verteks, n ≥ 3, sedemikian sehingga derajat tiap verteks paling sedikit n/2 maka graf merupakan graf Hamilton.
v Teorema 2.2. Jika graf G merupakan graf sederhana dengan n buah verteks, n ≥ 3, sedemikian sehingga jumlah derajat tiap pasang verteks u dan v di G paling sedikit n atau d(u) +d(v) ≥ n maka graf merupakan graf Hamilton.
v Teorema 2.3. Jika graf G adalah graf lengkap maka G merupakan graf Hamilton.
v Teorema 2.4. Jika graf G merupakan graf lengkap dengan n buah verteks, n ≥ 3, maka terdapat (n - 1)/2 buah sirkuit Hamilton.
v Teorema 2.5. Jika graf G merupakan graf lengkap dengan n buah verteks, n ≥ 3 dan n ganjil, maka terdapat (n - 1)/2 buah sirkuit Hamilton yang saling lepas (tidak ada edge yang beririsan).
Jika graf G merupakan graf lengkap dengan n buah verteks, n ≥ 3 dan n genap, maka terdapat (n - 2)/2 buah sirkuit Hamilton yang saling lepas.
Contoh:
Persoalan pengaturan tempat duduk: Sembilan anggota sebuah klub bertemu tiap hari untuk makan siang pada sebuah meja bundar. Mereka memutuskan duduk sedemikian sehingga setiap anggota mempunyai tetangga duduk berbeda pada setiap makan siang. Berapa hari pengaturan tersebut dapat dilaksanakan?.
Penyelesaian:
Persoalan di atas dapat direpresentasikan oleh sebuah graf dengan sembilan buah verteks sedemikian sehingga setiap verteks menyatakan anggota klub, dan edge yang menghubungkan dua buah verteks menyatakan kedua verteks tersebut bertetangga dalam tempat duduk.Sirkuit Hamilton: 1, 2, 3, 4, 5, G, 7, 8, 9, 1 edge dengan garis tebal, menyatakan salah satu cara pengaturan tempat duduk.
Sirkuit Hamilton: 1, 5, 9, 4, 8, 3, 7, 2, 6, 1 edge dengan garis tipis, menyatakan salah satu cara lain pengaturan tempat duduk.
Kalau kita lihat sirkuit Hamilton garis tebal dan garis tipis tidak beririsan edge dengan sirkuit Hamilton yang bergaris tipis, atau kedua sirkuit tersebut saling asing.
Jumlah pengaturan tempat duduk yang berbeda ada (9-1)/2 = 4. Sehingga dalam klub tersebut dapat bertemu dalam 4 hari dengan selalu berganti tetangga duduk.
BAB III
P E N U T U P
III.1 Kesimpulan
Berdasarkan pembahasan yang telah dilakukan, maka kesimpulan yang dapat diambil mengenai graf, jenis-jenis graf, graf planar dan graf Euler dan Hamilton adalah sebagai berikut:
- Graf adalah kumpulan simpul atau verteks yang dihubungkan dengan garis atau busur atau ruas atau edge.
- Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut.
- Graf terdiri dari beberapa jenis antara lain; graf sederhana, graf tak-sederhana, graf berarah, graf tak-berarah, graf berbobot, graf tak-berbobot dan lain-lain.
- Graf planar adalah suatu graf yang digambar dalam suatu bidang dengan sisi satu dengan lainnya tidak saling berpotongan.
- Graf Euler dan Hamilton ialah suatu sirkuit yang melewati setiap sisi pada graf G tepat satu kali dan kembali lagi ke simpul awal.
III.2 Saran
Materi pada makalah ini mengenai graf masih dapat dikembangkan, misalnya pada graf berhingga maupun tak berhingga, lintasan terpendek graf, pewarnaan pada graf dan lain sebagainya, hal ini dikarenakan tuntutan pembahasan materi yang telah diberikan oleh dosen pengasuh sebagai pemberi tugas. Untuk itu bagi semu pihak yang ingin mengembangkannya sangat dianjurkan agar tingkat kepahaman terhadap teori graf lebih baik lagi.
DAFTAR PUSTAKA
Liu, C.L. 1985. Dasar-Dasar Matematika Diskret. Terjemahan oleh Bambang Sumantri. Ed.2. 1995. Jakarta: Gramedia Pustaka Utama
http://www.yahoo.com
Tidak ada komentar:
Posting Komentar
Kritik dan saran sobat sangat erc harapkan demi penyempurnaan blog ini. Selamat menikmatinya dan silahkan BERKOMENTAR SOBAT.