Graf Euler dan Hamilton
Graf Euler
Lintasan dan Sirkuit Euler
• Lintasan Euler ialah lintasan yang melalui masing-masing sisi di dalam graf tepat satu kali
.
• Sirkuit Euler ialah sirkuit yang melewati masing-masing sisi tepat satu kali..
• Graf yang mempunyai sirkuit Euler disebut graf Euler (Eulerian graph). Graf yang mempunyai lintasan Euler dinamakan juga graf semi-Euler (semi-Eulerian graph).
(a) dan (b) grafsemi-Euler, (c) dan (d) graf Euler , (e) dan (f) bukan graf semi-Euler atau graf Euler
Lintasan Euler pada graf (a) : 3, 1, 2, 3, 4, 1
Lintasan Euler pada graf (b) : 1, 2, 4, 6, 2, 3, 6, 5, 1, 3
Sirkuit Euler pada graf (c) : 1, 2, 3, 4, 7, 3, 5, 7, 6, 5, 2, 6, 1
Sirkuit Euler pada graf (d) : a, c, f, e, c, b, d, e, a, d, f, b, a
Graf (e) dan (f) tidak mempunyai lintasan maupun sirkuit Euler
Teorema-teorema
• TEOREMA 6.2. Graf tidak berarah memiliki lintasan Euler jika
dan hanya jika terhubung dan memiliki dua buah simpul
berderajat ganjil atau tidak ada simpul berderajat ganjil sama
sekali.
• TEOREMA 6.3. Graf tidak berarah G adalah graf Euler
(memiliki sirkuit Euler) jika dan hanya jika setiap simpul
berderajat genap.
• (Catatlah bahwa graf yang memiliki sirkuit Euler pasti
mempunyai lintasan Euler, tetapi tidak sebaliknya)
• TEOREMA 6.4. Graf berarah G memiliki sirkuit Euler jika dan
hanya jika G terhubung dan setiap simpul memiliki derajat-
masuk dan derajat-keluar sama. G memiliki lintasan Euler jika
dan hanya jika G terhubung dan setiap simpul memiliki
derajat-masuk dan derajat-keluar sama kecuali dua simpul,
yang pertamamemiliki derajat-keluar satu lebih besar derajat-
masuk, dan yang kedua memiliki derajat-masuk satu lebih
besar dari derajat-keluar.
Graf Hamilton
Lintasan dan Sirkuit Hamilton
• Lintasan Hamilton ialah lintasan yang melalui
tiap simpul di dalam graf tepat satu kali.
• Sirkuit Hamilton ialah sirkuit yang melalui tiap
simpul di dalam graf tepat satu kali, kecuali
simpul asal (sekaligus simpul akhir) yang dilalui
dua kali.
• Graf yang memiliki sirkuit Hamilton dinamakan
graf Hamilton, sedangkan graf yang hanya
memiliki lintasan Hamilton disebut graf semi-
Hamilton.
Teorema
• TEOREMA 6.5. Syarat cukup (jadi bukan syarat perlu)
supaya graf sederhana G dengan n (³ 3) buah simpul
adalah graf Hamilton ialah bila derajat tiap simpul paling
sedikit n/2 (yaitu, d(v) ³ n/2 untuk setiap simpul v di G).
• TEOREMA 6.6. Setiap graf lengkap adalah graf
Hamilton.
• TEOREMA 6.7. Di dalam graf lengkap G dengan n buah
simpul (n ³ 3), terdapat (n - 1)!/2 buah sirkuit Hamilton.
• TEOREMA 6.8. Di dalam graf lengkap G dengan n buah
simpul (n ³ 3 dan n ganjil), terdapat (n - 1)/2 buah sirkuit
Hamilton yang saling lepas (tidak ada sisi yang
beririsan). Jika n genap dan n ³ 4, maka di dalam G
terdapat (n - 2)/2 buah sirkuit Hamilton yang saling
lepas.
Graf Isomorfik dan Homeomorfik
Perhatikan dua graf berikut ini :
Dua buah graf diatas, terdiri dari empat buah simpul dimana setiap simpul adalah berderajat tiga. Walaupun secara geometri kedua tersebut berbeda tetapi pada prinsipnya
kedua graf tersebut adalah sama.
Definisi / study kasus :
Dua buah graf G1 dan G2 dikatakan isomorfik jika terdapat korespondensi satu-satu antara simpul-simpul pada kedua graf tersebut dan antara sisi-sisi keduanya sehingga jika sisi e bersisian dengan simpul u dan v pada G1 maka sisi e’ pada G2 juga bersisian dengan simpul u’ dan v’.
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
Tetapi cara menunjukan dua graf yang isomorfik dapat diperhatikan pada contoh beriku ini.
Contoh :
Diketahui 2 buah graf berarah :
Pohon Biner
Tree bisa didefinisikan sebagai suatu kumpulan elemen salah satu elemennya disebut dengan akar (root), dan sisa elemen lainnya (yang disebut simpul) terpecah menjadi sejumlah himpunan yang paling tidak berhubungan satu sama lain, yang disebut dengan subpohon (subtree), atau disebut juga cabang. Jika kita melihat pada subpohon, maka subpohon inipun juga mempunyai akar dan sub-subpohonnya masing-masing.
Dalam kehidupan sehari-hari, tree dapat dilihat dari pohon silsilah keluarga. Tingkat yang tertinggi disebut juga sebagai root.
Untuk lebih jelasnya lihat gambar 6.1 merupakan
contoh dari sebuah tree.
Gambar 6.1 Contoh Tree dengan 15 simpul
Jika kita memperhatikan gambar ditas, sebenarnya yang disebut dengan simpul (node atau vertex) adalah elemen pohon yang berisi informasi / data dan petunjuk percabangan. Pada pohon diatas memiliki 15 simpul yang berisi informasi berupa huruf A, B, C, D sampai O lengkap dengan percabangannya. Akar / Root dari pohon diatas berisi huruf A.
Tingkat (level) suatu simpul ditentukan dengan pertama kali menentukan akar sebagai bertingkat 1. jika suatu simpul dinyatakan sebagai tingkat N, maka simpul-simpul yang merupakan anaknya dikatakan berada dalam tingkat N+1. pada pohon diatas merupakan tree dengan 5 level.
Selain tingkat, dikenal juga istilah derajad (degree) dari suatu simpul. Derajad suatu simpul dinyatakan sebagai banyaknya anak atau turunan dari simpul tersebut.
Contoh, dari gambar 6.1 simpul A mempunyai derajad 2, simpul B mempunyai derajad 2, simpul C berderajad 3. simpul-simpul F, H, I, J, K, L, N, O yang semuanya berderajad nol, disebut dengan daun (leaf).
Gambar 6.2 Simpul-simpul yang disebut daun
Tinggi (Height) atau Kedalaman (Depth) dari suatu pohon adalah tingkat maksimum dari suatu pohon dikurangi dengan satu. Dengan demikian pohon diatas mempunyai tinggi atau kedalaman sama dengan 4.
Hutan (Forest) adalah kumpulan sejumlah pohon yang tidak saling berhubungan. Dari gambar diatas jika kita menghapus simpul A maka akan terbentuk sebuah hutan.
Pohon Biner (Binary Tree)
Pohon biner bisa didefinisikan sebagai suatu kumpulan simpul yang mungkin kosong atau mempunyai akar dan dua subpohon yang saling terpisah yang disebut dengan subpohon kiri dan sub pohon kanan. Subpohon disebut juga sebagai cabang. Karakteristik dari pohon biner ialah bahwa setiap simpul paling banyak hanya mempunyai dua buah anak. Dengan kata lain derajat tertinggi dari sebuah pohon biner adalah dua.
Pengertian daun, root, level, tinggi dan derajad yang berlaku pada pohon juga berlaku pada binary tree. Penyajian binary tree pada komputer di gunakan double link list.
Deklarasi Pohon
Setiap simpul pada pohon biner selalu berisi dua buah pointer yang menunjuk ke cabang kiri dan cabang kanan dengan melihat hal tersebut maka struktur double link list sangat cocok untuk di terapkan di dalam tree ini. Gambar
Membuat Pohon Biner
Untuk membuat pohon biner, terdapat aturan dalam penempatan simpulnya. Berikut ini merupakan algoritma penempatan sebuah simpul dalam pohon biner :
“Simpul yang berisi informasi yang nilainya lebih besar dari simpul diatasnya akan ditempatkan sebagai cabang kanan dan jika lebih kecil akan ditempatkan di cabang kiri.”
Sebagai contoh jika kita akan membentuk pohon biner dari untai ‘HKACBLJ’ maka pohon biner yang dihasilkan adalah sebagai berikut :
Gambar 6.4 Pohon Biner Untai ‘HKACBLJ’
Proses untuk memperoleh pohon biner diatas adalah sebagai berikut : Karakter pertama ‘H’ ditempatkan sebagai Akar. Karakter ‘K’ karena lebih besar dari ‘H’ diletakkan dicabang kanan. Karakter ‘A’ karena lebih kecil dari ‘H’ akan menempati cabang kiri dari ‘H’. kemudian, karena karakter ‘C’ lebih kecil dari ‘H’ dan lebih besar dari ‘A’ maka ia di letakkan sebagai cabang kanan dari ‘A’. demikian seterusnya sampai semua masukkan di proses.
Untuk mengalokasikan simpul baru seperti diatas biasanya digunakan fungsi rekursif, untuk itu ada baiknya jika kita membuat fungsi baru agar proses rekursif untuk simpul dapat berlangsung sukses.
Kunjungan Pada Pohon Biner
Sebuah pohon biner memiliki operasi traversal yaitu suatu kunjungan pada suatu simpul tepat satu kali. Dengan melakukan kunjungan lengkap kita akan memperoleh urutan informasi secara linier yang tersinpan di dalam pohon biner.
Terdapat tiga jenis kunjungan pada pohon biner, yaitu :
1. PREORDER
Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :
- Cetak isi simpul yang dikunjungi.
- Kunjungi cabang kiri.
- Kunjungi cabang kanan.
Dari gambar 6.4 jika kita melakukan traversal secara PREORDER pada pohon biner tersebut maka akan menghasilkan untai : ‘HACBKJL’.
2. INORDER
Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :
- Kunjungi cabang kiri.
- Cetak isi simpul yang dikunjungi.
- Kunjungi cabang kanan.
Dari gambar 6.4 jika kita melakukan traversal secara INORDER pada pohon biner tersebut maka akan menghasilkan untai : ‘ABCHJKL’.
3. POSTORDER
Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :
- Kunjungi cabang kiri.
- Kunjungi cabang kanan.
- Cetak isi simpul yang dikunjungi.
Dari gambar 6.4 jika kita melakukan travarsal secara POSTORDER pada pohon biner tersebut maka akan menghasilkan untai : ‘BCAJLKH’.
Tidak ada komentar:
Posting Komentar