http://lms.unhas.ac.id/claroline/backends/download.php?url=L0JBQl9JSS5fQmViZXJhcGFfR3JhZl9LaHVzdXMuZG9jeA%3D%3D&cidReset=true&cidReq=MD_001

BAB II BEBERAPA JENIS GRAF KHUSUSSuatu graf disebut graf khusus karena graf tersebut memiliki ciri-ciri tertentu yang mudah dikenali. Graf lengkap adalah salah satu graf khusus yang paling mudah dikenali dan telah didefinisikan pada Bab I. Pada bab ini akan dibahas beberapa graf khusus seperti graf lintasan, graf siklus, graf bintang, graf roda, dan graf pohon. 2.1 GRAF LINTASAN DAN GRAF SIKLUS Dalam kehidupan sehari-hari orang senang bepergian cenderung berfikir bagaimana meminimumkan biaya perjlanan. Demikian pula dengan biaya-biaya lain seperti biaya hidup, biaya pendidikan dan lain-lain. Untuk masalah perjalanan atau jaringan, baik itu jaringan transportasi, jaringan listrik, ataupun jaringan komputer dan imformasi dapat dicari solusinya dengan memodelkan masalah tersebut ke dalam model graf, kemudian mencari lintasan terpendek pada graf hasil pemodelan tersebut. Beberapa cara mendefinisikan graf lintasan. Ada yang memulai dari pengertian barisan, ada pula yang memulai dari pengertian jalan (walk). Di sini akan disajikan pengertian lintasan dengan menggunakan istilah jalan. Karenaya, sebelum membahas lintasan terlebih dahulu membahas jalan. Definisi 2.1.1. Misalkan G adalah graf dengan himpunan titik V(G)= {v1, v2, ...,vk, ...,vn}, dan himpunan sisi E(G)={ei : ei = vivj untuk suatu i,j}. 1. Jalan W pada graf G dengan panjang k adalah barisan titik dan sisi : dengan ,.2. Jalan disebut tertutup jika .3. Jalan yang setiap sisinya berbeda disebut jalur (trail).4. Jika untuk setiap i,j {0, 1, 2, ..., k}, maka W disebut lintasan. 5. Graf yang hanya terdiri atas satu lintasan disebut graf lintasan. Definisi 2.1.2. Misalkan : adalah lintasan orde k pada graf G. Siklus pada G dengan panjang k dinotasikan adalah subgraf dengan himpunan titik dan himpunan sisi . Graf yang hanya terdiri atas satu siklus disebut graf siklus.

Teorema 2.1.1 Jika graf G memuat jalan u v dengan panjang l, maka G memuat lintasan u v dengan panjang paling besar l.

Bukti. Diantara semua lintasan u v dalam G, diandaikan P : adalah suatu jalan dengan panjang terkecil k. Karenanya, k l. Klaim bahwa P adalah lintasan u v. Karena u v adalah jalan, maka terdapat i, j dengan 1ijk sehingga vi = vj. Akibatnya, jalan memiliki panjang kurang dari k. Hal ini tidak mungkin karena P adalah lintasan. Jadi mestilah k adalah panjang terbesar. Batas editContoh 2.1.4 Misalkan dan Graf adalah graf lintasan berorde 6, lihat Gambar 2.1.2. Graf bagian (a) adalah graf lintasan berorde dan bagian (b) adalah graf siklus dengan panjang 6. v3v4v3v4v2v5v2v5

v6v1v6

P6 :C6 :Gambar 2.1.2 : Graf lintasan dan siklusContoh 2.1.5 Misalkan dan Bentuk graf dapat dilihat pada Gambar 2.1.3. Salah satu jalan pada graf adalah . :

Gambar 2.1.3 Lintasan pada graf adalah , dan siklus pada graf adalah , . Dalam hal ini . Graf dikatakan terhubung (connected) jika untuk setiap dua titik dan pada graf tersebut terdapat suatu lintasan yang memuat dan . Misalkan . Subgraf disebut subgraf terhubung maksimal jika bukan subgraf sejati pada sembarang subgraf terhubung di G. Subgraf disebut komponen dari jika merupakan subgraf terhubung maksimal. Selanjutnya, misalkan adalah graf terhubung dan serta Himpunan disebut himpunan titik pemisah , jika graf tak terhubung. Secara serupa, himpunan disebut himpunanan sisi pemisah dalam jika juga graf tak terhubung.Misalkan dan berturut-turut merupakan himpunan titik pemisah dan himpunan sisi pemisah. Jika dan , maka disebut titik potong (cut vertex) dan disebut jembatan (bridge). Sebagai contoh, pada Gambar 2.1.2 titik adalah titik potong dan sisi adalah jembatan. Pada Gambar 2.1.4. Graf G memiliki himpunan titik potong A={a, b} atau D = {a,b,c} dan himpunan sisi pemisah B ={ad, ac, bc}.

a d

b c G :Gambar 2.1.4. Graf yang memiliki himpunan titik potongPanjang siklus terbesar pada suatu graf dinotasikan dengan , sedangkan panjang siklus terkecil dinotasikan dengan . Graf dengan orde disebut pansiklis (pancynclic) jika memuat semua siklus dengan , dan disebut pansiklis lemah (weakly pancyclic) jika memuat siklus untuk .

G1 :G2 :Gambar 2.1.5 Graf pansiklis lemah dan graf pansiklis .Graf pada Gambar 2.1.5 adalah pansiklis lemah dengan dan adalah pansiklis karena memuat semua siklus untuk .

2.3 GRAF BINTANG DAN GRAF RODA

2.4 GRAF POHONTeori graf merupakan salah satu cabang matematika yang memiliki banyak penerapan untuk mencari solusi dari permasalahan diskrit yang terjadi di kehidupan sehari-hari. Untuk mencari solusi tersebut, di dalam graf terdapat banyak konsep. Salah satu konsep di antaranya adalah konsep pohon (tree). Salah satu istilah dalam konsep pohon adalah pohon perentang (spanning tree). Misalkan adalah graf terhubung tak berarah yang bukan pohon, berarti pada graf terdapat beberapa sikel, dapat diubah menjadi suatu pohon dengan cara menghapus sisi-sisi yang membentuk sikel sehingga graf terhubung tidak lagi memuat sikel, graf menjadi sebuah pohon yang disebut pohon perentang. Salah satu jenis graf khusus adalah graf berbobot (weighted graph). Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga atau bobot. Pada graf berbobot terhubung, dikenal istilah pohon perentang minimum (minimum spanning tree). Jika adalah graf berbobot, maka bobot pohon perentang dari didefinisikan sebagai jumlah bobot semua sisi di Di antara semua pohon perentang dari pohon perentang yang berbobot minimum disebut pohon perentang minimum. Hingga saat ini, pemanfaatan pohon perentang minimum dapat diaplikasikan untuk mencari solusi pada permasalahan di dunia nyata. Di antaranya, masalah jaringan komunikasi (network), yakni untuk membangun suatu jaringan komunikasi dengan biaya pemakaian sekecil mungkin.Dalam membentuk sebuah pohon perentang minimum dari suatu graf terhubung berbobot, dikenal dua algoritma yaitu algoritma Prim dan algoritma Kruskal.Definisi 2.9 : Graf Pohon

Misalkan adalah graf terhubung. Jika tidak berarah dan tidak memiliki siklus, maka disebut graf pohon. Atau dengan kata lain graf pohon adalah graf terhubung yang tidak mempunyai siklus.

Gambar 5. Graf pohon dan bukan graf pohon

Contoh graf dan adalah graf pohon diberikan pada Gambar II.5 dimana setiap simpulnya senantiasa punya jalan ke simpul lain. Sedangkan karena terdapat siklus dan graf bjuga bukan graf pohon karena tidak ada jalan dari a ke d dan beberapa simpul lainnya.

Teorema 2.2

Jika adalah graf pohon jika setiap simpulnya memiliki hanya satu jalan ke simpul yang lain.

Bukti

Misalkan adalah graf pohon yang memiliki simpul simpul . adalah pohon maka setiap simpulnya memiliki jalan kepada simpul yang lain dan karena tidak ada siklus maka tidak ada perulangan jalan. Sehingga dapat disimpulkan setiap simpulnya memiliki hanya satu jalan ke simpul yang lain.

Teorema 2.3

Jika adalah graf yang memiliki titik, maka pernyataan-pernyataan berikut adalah eqivalen.

Jika adalah pohon, maka memiliki sisi dan tidak memiliki siklus.

Jika adalah graf terhubung dan memiliki sisi, maka setiap dua titik simpul dari dihubungkan oleh tepat satu lintasan.

tidak memiliki siklus, dan jika pada ditambahkan satu sisi x yang mengaitkan dua titik di G yang tidak bertetangga, maka memiliki satu siklus.

II.2 Pohon Berakar

Berikut ini pembahasan lebih lanjut mengenai graf pohon. Akan didefinisikan beberapa istilah penting pada graf pohon berakar yang nantinya akan digunakan pohon traversal pada bab III.

Definisi 2.10 : DaunDaun adalah semua simpul yang derajatnya satu atau simpul yang berada pada tingkat terendah dari pohon. Seringkali, daun merupakan simpul terjauh dari akar

Dalam teori graf, daun adalah sebuah simpul dengan derajat 1 selain akar (kecuali jika pohonnya hanya memiliki satu sudut; maka akarnya adalah daunnya juga). Setiap graf pohon memiliki setidaknya satu daun.

Definisi 2.11 : Simpul Dalam (Internal Nodes)

Misalkan graf adalah graf pohon, maka simpul dalam adalah semua simpul dari graf pohon yang memiliki daun dan bukan merupakan daun.

Definisi 2.12 : Subpohon (Subtrees)

Misalkan graf adalah graf pohon, ,maka subpohon (Subtrees) adalah suatu bagian dari graf pohon yang dapat dilihat sebagai sebuah pohon lain yang berdiri sendiri.

Pada gambar II.5 di bawah ini adalah sebuah graf pohon. Sesuai dengan definisi 2.10 2.12 maka simpul simpul M, N, O, P, Q, R, S, T, U, V, W, X, Y dan Z adalah daun. Simpul internalnya adalah F, G, H, I, J, K dan L dan graf tersebut dapat dipisah pisah menjadi empat buah subpohon yang berawal dari B, C, D dan E.

Gambar II.5. Graf pohon

Definisi 2.13 : Graf Pohon Berakar

Suatu graf yang merupakan pohon berarah bila arah sisinya diabaikan dan suatu pohon berarah dinamakan pohon berakar (rooted tree) bila ada tepat satu simpul yang berderajat masuk 0, dan semua simpul lain berderajat masuk 1. simpul berderajat masuk 0 dinamakan akar, simpul berderajat keluar 0 dinamakan daun, sedangkan simpul yang berderajat masuk 1 tetapi derajat keluarnya tidak 0 disebut simpul cabang.

Gambar II.6. Graf pohon berarah yang jika arahnya tidak diperhatikan maka simpul yang derajatnya 0 adalah akar

Pada gambar II. 6 di atas simpul a adalah akar, simpul-simpul b, c adalah simpul cabang sedangkan simpul-simpul d, e, f dan g adalah daun.

Simpul d disebut anak (child) dari simpul b bila ada sisi dari b ke d, dalam hal ini simpul b disebut orang tua (parent) dari simpul d. Bila simpul d memiliki anak lagi maka anak dari simpul d merupakan keturunan (descendent) dari simpul a, b, d karena ada lintasan berarah dari simpul-simpul tersebut ke simpul anak dari d. Sebaliknya, simpul-simpul a, b, dan d disebut leluhur (ancestor) dari simpul anak dari d.

Gambar II.7. Graf pohon yang tidak berakar

karena ada suatu siklus dari kembali ke .

Teorema 2.4 : Teorema geometrik pohon

Bila adalah pohon berakar (dimana adalah relasi dan adalah akar) maka: Tidak ada siklus dalam

merupakan satu-satunya akar dari .

Gambar II.8. Graf di atas bukanlah pohon berakar

karena mempunyai 2 akar pohon yaitu dan .

Perhatikan pada gambar II.7 dan gambar II.8 bukan graf pohon berakar karena tidak memenuhi teorema 2.4. gambar II.7 bukan graf pohon berakar karena terdapat siklus dari kembali ke dan gambar II.8 juga bukan pohon berakar karena mempunyai 2 akar pohon yaitu dan

Definisi 2.14 : Level

Misalkan graf pohon berakar , memiliki akar , jika semua simpul yang tepat dibawahnya (anak dari ) diberi simbol . Kemudian simpul anak dari simpul semua diberi symbol dan seterusnya hingga maka level graf pohon berakar adalah

Untuk lebih jelasnya perhatikan gambar II. 9 di bawah. Terdapat graf pohon berakar , akar pohonnya adalah a diberi ada di level 0. Kemudian b, f dan g yang merupakan anak dari akar a semua berlevel 1, dan c anak dari b, h, i dan j yang merupakan anak dari g,semua merupakan anak dari simpul berlevel 1 sehingga diberi level 2 dan kemudian simpul dibawah simpul yang berlevel 2 diberi level 4. Jadi graf itu sendiri adalah graf graf pohon berakar berlevel 3.

Gambar II.9. Level graf pohon berakar .

II.3 Beberapa Istilah Lain Sepadan Yang Sering Digunakan

Agar tidak bingung dengan istilah lain yang sama yang sering digunakan terutama dalam struktur basis data, maka akan diberikan juga beberapa istilah yang digunakan lainnya. Antara lain Predecessor : simpul yang berada di atas simpul tertentu Successor : simpul yang dibawah simpul tertentu Ancestor : seluruh simpul yang terletak sebelum simpul tertentu dan terletak sesudah pada jalur yang sama Descendant : seluruh simpul yang terletak sesudah simpul tertentu dan terletak sesudah pada jalur yang sama Parent : predecessor satu level diatas suatu simpul Child : successor satu level dibawah suatu simpul Sibling : simpul-simpul yang memiliki parent yang sama dengan suatu simpul Subtree : bagian dari graf pohon yang berupa suatu simpul beserta descendantnya dan memiliki semua karakteristik dari graf pohon tersebut Size : banyaknya simpul dalam suatu tree Height : banyaknya tingkatan/level dalam suatu tree Root : satu-satunya simpul khusus dalam tree yang tidak mempunyai predecessor Leaf : simpul-simpul dalam tree yang tidak memiliki successor Degree : banyaknya child yang dimiliki suatu simpul

Gambar II.10. Graf pohon berakar

Dari gambar II.10 dan berdasarkan definisi di atas maka : Ancestor : C, A Descendant : C, G Parent : B Child : B, C Sibling : F, G Size : 7 Height : 3 Root : A Leaf : D, E, F, G Degree : 2

BAB III

SISTEMATIKA PENGALAMATAN UNIVERSAL DAN PEMBUATAN GRAF

Dalam struktur data, pohon memegang peranan yang cukup penting. Struktur ini biasanya digunakan terutama untuk menyajikan data yang mengandung hubungan hirarki antara elemen-elemennya. Kita lihat misalnya, data pada record, keluarga dari pohon, ataupun isi dari tabel. Mereka mempunyai hubungan secara hirarki. Pohon atau tree adalah salah satu bentuk graf terhubung yang tidak mengandung sirkuit. Karena merupakan graf terhubung, maka pada pohon selalu terdapat jalan yang menghubungkan setiap dua simpul dalam pohon. Disini akan dibahas mengenai bagaimana cara menggambarkan graf dari suatu ekspresi dan graf pohon berakar pada sistem pengalamatan

III.1 Sistem Pengalamatan Universal

Jika kita akan mengunjungi suatu alamat misalnya di jalan I no 2 RT, RW, Kelurahan, Kecamatan, Kota, Propinsi, Negara maka secara sistematis ini membutuhkan prosedur yang teratur. Demikian juga jika kita ingin mengunjungi sebuah web, komputer pada suatu jaringan, data dan lain lain maka ini juga membutuhkan prosedur yang teratur dan sistematis yang mirip dengan graf pohon. Prosedur untuk mengunjungi semua simpul pada pohon berakar terurut tergantung pada penataan daun daunnya. Pada graf pohon berakar terurut, daun dari simpul internal dalam penggambarannya dibuat dari kiri ke kanan. Urutan penyusunan simpul - simpul dari sebuah pohon berakar teratur adalah (Rosen, 2012):

Cara melabeli semua simpul secara rekursif :1. Labeli akar dengan bilangan bulat 0. Kemudian label k untuk anak dari akarnya (daunnya) dari kiri ke kanan dengan 1, 2, 3,...,k.2. Untuk setiap simpul yang memiliki anak v pada level n diberikan label A (sesuai dengan simpulnya, misalnya), labeli anaknya (daun) dengan kv, yang dibuat dari kiri ke kanan. Sehingga didapatkan A.1, A.2, ..., A. kv.

Gambar III.1. Pelabelan akar, simpul dan daun

Simpul v pada level n (dengan ), diberi label x1, x2, ..., xn, dimana terdapat suatu jalan yang unik dari akar ke v yang melewati simpul ke x1 di level 1, simpul ke x2 di level 2 dan seterusnya. Pelabelan ini disebut sistem pengalamatan universal pohon berakar terurut. Contoh pembuatannya seperti pada gambar III.2 di bawah ini. Simpul akar yaitu 0 yang memiliki anak 1, 2, 3, 4 dan 5. Simpul yang punya anak yaitu simpul 1, 3, dan 5. Pada masing masing simpul yang memiliki anak diberi label orang tua (parent) diikuti 1, 2, ..., n. Dan dengan cara yang sama untuk simpul simpul di bawahnya

Gambar III.2. Sistem pengalamatan universal

Kita secara total dapat menyusun simpul simpul tersebut dengan menggunakan urutan pelabelan sistem pengalamatan universal. Simpul berlabel kurang dari simpul berlabel jika terdapat i, dengan , , ...., dan , atau jika dan untuk . Dari gambar III.2 di atas dengan pelabelan sistem pengalamatan universal dalam pohon berakar terurut adalah

III.2 Prosedur Pembuatan Graf Pohon Pada Suatu Ekspresi

Kita dapat menyatakan hubungan yang kompleks seperti proposisi majemuk, kombinasi himpunan dan aritmatika dengan menggunakan graf pohon terurut. Misalnya ekpresi matematika dengan operator tambah (+), kurang ( ), perkalian (*), bagi ( / ) dan pangkat ( ). Pada tulisan ini digunakan tanda kurung untuk menunjukkan orde operasi.

Cara membuat graf dari suatu ekspresi yaitu Tahap pembentukan graf dari suatu ekspresi ada beberapa tahap yaitu mengkonstruksi sub sub pohon kemudian menggabungkannya dengan suatu akar, dimana akar tersebut digunakan sebagai simpul.

Jadi dalam pembuatan graf dari suatu ekspresi kita harus pisahkan dahulu maka pohon, subpohon dan akar akarnya. Setelah itu baru tentukan mana parent, anak maupun daunnya. Dari pemisahan ini maka akan tergambar suatu graf pohon.

Contoh Soal

Misalkan bentuk graf pohon terurut pada , buatlah pembuatan graf pohonnya.

Jawab

Pembuatan graf pohon berakar terurut pada dibuat dengan cara :

Pertama : Pisahkan subpohon , dengan anaknya dan 2 kemudian dihubungkan dengan dan subpohon dengan anaknya dan . Dari sini terlihat daun daun dari graf tersebut adalah x, y, 2, x, -4 dan 3. Kemudian dibuat graf seperti gambar III.3

Gambar III.3. Membuat subpohon dan

Kedua: Konstruksi kedua subpohon (karena hanya dua) yaitu dan dijadikan satu dihubungkan dengan +. Sehingga + merupakan akar dari ekspresi jika dinyatakan dengan graf. Dan hasilnya dapat dilihat pada gambar III.4.

Gambar III.4. Gabungkan dengan akar (+) menjadi graf pohon terurut

Latihan1. Buatlah bentuk graf dari urutan simpul berikut

2. Buatlah bentuk graf dari persamaan

BAB IV

ALGORITMA POHON TRAVERSAL DAN NOTASINYA

IV.1. Algoritma Traversal

Kunjungan pada suatu alamat, sebuah web, komputer pada suatu jaringan, data pada suatu tabel dan lain lain maka ini juga membutuhkan prosedur yang teratur dan sistematis yang mirip dengan graf pohon. Prosedur ini dinamakan algoritma traversal yaitu suatu prosedur yang secara sistematik mencari bagaimana mengunjungi setiap simpul pada sebuah graf pohon berakar terurut. Akan diterangkan 3 algoritma yang paling banyak digunakan yaitu Preorder Traversal, Inorder Traversal dan Postorder Traversal.

IV.1.1 Algoritma Preorder Traversal

Definisi 4.1 : Algoritma Preorder (Rosen, 2012)

Misalkan adalah sebuah graf pohon berakar terurut dengan akar . Jika pada graf hanya terdapat , maka dan merupakan preorder traversal dari . Sebaliknya misalkan adalah sub sub pohon di dari kiri ke kanan di . Preorder traversal dimulai dengan mengunjungi . Selanjutnya melewati preorder, kemudian preorder dan seterusnya, sehingga melewati preorder.

Dari definisi yang dikemukan Rosen ini mungkin masih sangat sulit untuk mengerti bagaimana langkah langkah praktisnya. Demikian juga prosedur sederhana preorder traversal adalah akar, kiri kanan (Munir, 2005) atau Kunjungi akar Kunjungi subpohon disebelah kiri akar Kunjungi subpohon disebelah kanan subpohon sebelumnya. Yang langkah langkahnya digambarkan sebagai berikut :

Gambar IV.1. Alur Sederhana Preorder Traversal (akar, kiri, kanan)

Penyederhanaan langkah yang demikian maupun langkah yang dikemukakan Rosen hanya jelas jika hanya ada akar dan simpul simpulnya saja. Sedangkan jika terdapat akar, beberapa orang tua, anak dan daun dalam jumlah banyak dalam suatu graf maka langkah tersebut masih kurang jelas. Contoh berikut akan memperjelas bagaimana alur prosedur preorder dalam mengunjungi setiap simpulnya.

Contoh Soal 4.1Misalkan terdapat graf T pada gambar di bawah ini, bagaimana cara mengunjungi tiap simpulnya secara preorder?

Gambar IV.2. Graf pohon T

JawabAlur aplikasi pada graf pohon di atas secara preorder digambarkan di bawah ini :

Gambar IV.3. Alur Preorder Traversal

Algoritma per-langkahnya Kunjungi akar a Kunjungi subpohon di sebelah kiri dari akar a hingga orang tua, anak dan daun yaitu b,e,j

Karena subpohon sudah habis maka cari subpohon dibawahnya , disini harus melewati level yang paling atas (dekat dengan akar) jadi kunjungi k. Kunjungi daun daun k dari kiri ke kanan yaitu n, o dan p Karena sudah habis maka kunjungi daun berikutnya yaitu f. Kunjungi akar a kemudian kunjungi daun kedua (karena pada simpul c tidak ada simpul level di bawahnya maka kunjungi c. Kunjungi subpohon , kemudian menuju daun paling kiri yaitu d, g, l. Ulangi cara mengunjungi seperti subpohon sebelumnya sehingga didapatkan m, h dan i.Sehingga urutan simpul yang dilewatinya a,b,e,j,k,n,o,p,f,c,d,g,l,m,h dan i.

Pemecahan prosedur ini perlangkahnya dapat dilihat pada gambar di bawah ini

Gambar IV.4. Algoritma Preorder Traversal

IV.1.2. Algoritma Ineorder Traversal

Definisi 4.2 : Algoritma Inorder (Rosen, 2012)

Misalkan adalah sebuah graf pohon berakar terurut dengan akar . Jika pada graf hanya terdapat , maka dan merupakan inorder traversal dari . Sebaliknya misalkan adalah subpohon di dari kiri ke kanan di . Inorder traversal dimulai dengan mengunjungi . Selanjutnya kunjungi inorder, kemudian inorder dan seterusnya, sehingga mengunjungi inorder.

Dari definisi yang dikemukan Rosen ini mungkin masih sangat sulit untuk mengerti bagaimana langkah langkah praktisnya. Demikian juga prosedur sederhana inorder traversal adalah kiri, akar, kanan (Munir, 2005) atau Kunjungi subpohon paling kiri dari akar. Kunjungi akar Kunjungi subpohon kanannya.Langkah langkahnya digambarkan sebagai berikut :

Gambar IV.5. Alur Sederhana Inorder Traversal (kiri, akar, kanan)

Penyederhanaan langkah yang demikian maupun langkah yang dikemukakan Rosen hanya jelas jika hanya ada akar dan simpul simpulnya saja. Sedangkan jika terdapat akar, beberapa orang tua, anak dan daun dalam jumlah banyak dalam suatu graf maka langkah tersebut masih kurang jelas. Perlu ditekannkan bahwa prosedur inorder selalu mengutamakan daun kemudian orang tua dari daun tersebut. Contoh berikut akan memperjelas bagaimana alur prosedur inorder dalam mengunjungi setiap simpulnya.

Contoh Soal 4.2Misalkan terdapat graf T pada gambar IV.2, bagaimana cara mengunjungi tiap simpulnya secara inorder?

JawabAlur aplikasi pada graf pohon di atas secara inorder digambarkan di bawah ini :

Gambar IV.6. Alur Inorder Traversal

Algoritma per-langkahnya Kunjungi daun dari subpohon paling kiri dari akar a yaitu j. Naik pada level di atasnya atau orangtua dari j yaitu e Kunjungi daun paling kiri dari subpohon level dibawahnya yaitu n. Naik pada level di atasnya atau orangtua dari n yaitu k Kunjungi daun daun k yang lain yaitu o dan p. Karena sudah habis maka naik level diatasnya pada subpohon yang sama (), jadi kunjungi b. Kunjungi daun b yaitu f. Kunjungi akar a Kunjungi daun a setelah subpohon yaitu c. Kunjungi daun paling kiri dari subpohon berikutnya yaitu l. Naik pada simpul level di atasnya yaitu g Kunjungi daun g yaitu m. Naik pada simpul level di atasnya yaitu d Kunjungi daun d yaitu h dan i.Sehingga urutan simpul yang dilewatinya j,e,n,k,o,p,b,f,a,c,l,g,m,d,h dan i.

Pemecahan prosedur ini perlangkahnya dapat dilihat pada gambar di bawah ini

Gambar IV.7. Algoritma Inorder Traversal

IV.1.3. Algoritma Postorder Traversal

Definisi 4.3 : Algoritma Postorder (Rosen, 2012)

Misalkan adalah sebuah graf pohon berakar terurut dengan akar . Jika pada graf hanya terdapat , maka dan merupakan postorder traversal dari . Sebaliknya misalkan adalah subpohon di dari kiri ke kanan di . Postorder traversal dimulai dengan melewati daun paling kiri di , kemudian postorder dan seterusnya hingga dan berakhir melewati preorder .

Dari definisi yang dikemukan Rosen ini mungkin masih sangat sulit untuk mengerti bagaimana langkah langkah praktisnya. Demikian juga prosedur sederhana postorder traversal adalah kiri, akar, kanan (Munir, 2005) atau Lewati daun paling kiri dari subpohon paling kiri, selalu mencari daun hingga habis mendekati subpohon kanannya Lewati daun daun subpohon selanjutnya disebelah kanannya Kunjungi akar

Langkah langkahnya digambarkan sebagai berikut :

Gambar IV.8. Alur Sederhana Postorder Traversal (kiri, kanan, akar)

Penyederhanaan langkah yang demikian maupun langkah yang dikemukakan Rosen hanya jelas jika hanya ada akar dan simpul simpulnya saja. Sedangkan jika terdapat akar, beberapa orang tua, anak dan daun dalam jumlah banyak dalam suatu graf maka langkah tersebut masih kurang jelas. Perlu ditekannkan bahwa prosedur postorder selalu mengutamakan daun. Contoh berikut akan memperjelas bagaimana alur prosedur inorder dalam mengunjungi setiap simpulnya.

Contoh Soal 4.3Misalkan terdapat graf T pada gambar IV.2, bagaimana cara mengunjungi tiap simpulnya secara postorder?

JawabAlur aplikasi pada graf pohon di atas secara postorder digambarkan di bawah ini :

Gambar IV.9. Alur Postorder Traversal

Gambar IV.10. Algoritma Postorder Traversal

Algoritma per-langkahnya Kunjungi daun paling kiri dari subpohon dari akar a yaitu j. Kunjungi daun subpohon sebelah kanan j yaitu n,o,p. Naik pada simpul level di atasnya (akar dari subpohon ) yaitu kunjungi k. Naik ke level subpohon di atas k yaitu e. Kunjungi daun f. Naik pada simpul level di atasnya (akar dari subpohon ) yaitu b. Kunjungi daun a yaitu c. Kunjungi daun paling kiri pada subpohon sebelah kanan () dari akar a yaitu l,m. Naik ke level subpohon di atasnya yaitu g. Naik ke daun dari subpohon d yaitu h dan i. Naik ke level subpohon di atasnya yaitu d. Naik ke akar yaitu a.Sehingga urutan simpul yang dilewatinya j,n,o,p,k,e,f,b,c,l,m,g,h,i,d dan a.

IV.2 Notasi Prefix, Infix danPostfix

Kita dapat menyatakan hubungan yang kompleks seperti proposisi majemuk, kombinasi himpunan dan aritmatika dengan menggunakan graf pohon berakar terurut. Misalnya ekpresi matematika dengan operator tambah (+), kurang ( ), perkalian (*), bagi ( / ) dan pangkat ( ). Tanda kurung untuk menunjukkan orde operasi. Bagaimana menuliskan urut urutan ekspresi pada graf pohon berakar terurut inilah yang akan dibahas pada bab ini yaitu notasi prefix, infix dan postfix.

Agar lebih mudah prosedur membuat notasi ini dimulai dengan membuat graf pohon terurut pada ekspresi yang akan dibuatkan notasi. Kemudian urut urutkan sesuai dengan prosedur yang diinginkan. Dari urutan itulah maka notasi dapat dibuat.

IV.2.1 Notasi Prefix

Definisi 4.4 : Notasi PrefixNotasi Prefix adalah notasi mengunjungi tiap simpul pada graf pohon berurut secara preorder.

Dari notasi ini mensyaratkan pengetahuan tentang preorder traversal, agar lebih jelasnya lihat contoh di bawah ini

Contoh Soal 4.4

Bagaimana notasi prefix ekspresi berikut ?

JawabPada notasi prefix maka mengikuti alur preorder seperti prosedur yang sudah dijelaskan sebelumnya yaitu akar, kiri, kanan. Dari gambar 12 maka alur ekspresi prefixnya:1. Kunjungi akarnya + 2. Kunjungi subpohon sebelah kiri hingga ke daun yang lurus dengan akar + + x y3. Kunjungi daun daun berikutnya + + x y 24. Kunjungi subpohon sebelah kanannya dengan cara yang sama sehingga didapatkan + + x y 2 / x 4 3

Contoh Soal 4.5

Bagaimana perhitungan secara preorder + * 2 3 5 / 2 3 4?

Solusi :

Alur perhitungan + * 2 3 5 / 2 3 4 adalah prefix digambarkan dari atas ke bawah berikut :

Gambar IV.11. Cara operasi notasi traversal

Kerjakan subpohon sebelah kanan akar ( / ) yaitu 2 3 atau Kerjakan subpohon tersebut dengan akar ( / ) yaitu / 8 4 atau Kerjakan subpohon sebelah kiri akar ( / ) yaitu * 2 3 atau 6 5 atau Kerjakan subpohon kiri dengan kanan yaitu + 1 2 atau

IV.2.2 Notasi Infix

Definisi 4.5 : Notasi Infix

Notasi infix adalah notasi mengunjungi tiap simpul pada graf pohon berurut secara inorder

Dari notasi ini mensyaratkan pengetahuan tentang inorder traversal, agar lebih jelasnya lihat contoh di bawah ini

Contoh Soal 4.6

Bagaimana notasi infix ekspresi ?

JawabPada notasi infix maka mengikuti alur inorder seperti prosedur yang sudah dijelaskan sebelumnya yaitu kiri, akar, kanan. Maka didapatkan alur pengerjaan infixnya:1. Kunjungi variabel daun subpohon paling kiri x2. Naik ke simpul level diatasnya (orangtua) sehingga x +3. Kunjungi daun simpul tersebut tersebut sehingga didapat x + y4. Dengan cara yang sama kunjungi simpul selanjutnya sehingga didapat x + y 25. Kunjungi akar sehingga didapat x + y 2 +6. Kunjungi daun subpohon sebelah kanannya sehingga didapat x + y 2 + x 7. Ulangi cara mengunjungi subpohon pertama x + y 2 + x 4 / 3

IV.3 Notasi Postfix

Definisi 4.6Notasi Postfix adalah notasi mengunjungi tiap simpul pada graf pohon berurut secara postorder

Ekpresi penulisan postfix dinamakan juga reverse polish notation. Agar lebih jelasnya lihat contoh di bawah ini

Contoh Soal 4.7

Bagaimana bentuk postfix ekspresi berikut

JawabPada notasi postfix maka mengikuti alur postorder seperti prosedur yang sudah dijelaskan sebelumnya yaitu kiri, kanan, akar. Dari gambar 12 maka didapatkan alur pengerjaan postfixnya:1. Kunjungi variabel daun daun subpohon paling kiri x y2. Kunjungi orangtua (parent) dari daun tersebut sehingga didapat x y + 3. Kunjungi daun dan kemudian orangtuanya (parent) sehingga didapat x y + 24. Kunjungi daun daun subpohon sebelah kanannya sehingga didapat x y + 2x 4 5. Kunjungi orangtua (parent) dari daun tersebut sehingga didapat x y + 2x 4 3 /6. Kunjungi Akar sehingga didapat x y + 2x 4 3 / +

Contoh Soal 4.8

Bagaimana bentuk postfix ekspresi logika berikut

Jawab

Buat graf pohon dari seperti gambar di bawah ini

Gambar IV.12. graf pohon untuk

Sehingga notasi postfixnya untuk adalah1. Kunjungi variabel daun daun subpohon paling kiri p q2. Kunjungi operator penghubung variabel tersebut sehingga didapat p q 3.

Kunjungi operator penghubung level di atasnya sehingga didapat p q 4.

Kunjungi daun daun subpohon sebelah kanannya sehingga didapat pqp q5.

Kunjungi operator penghubung level di atasnya sehingga didapat pqp q 6.

Kunjungi Akar sehingga didapat pqp q

Latihan 1Bagaimana urutan kunjungan pada simpul simpul graf berikut

Latihan 21. Buatlah notasi pada ekspresi berikut

2. Buatlah notasi pada ekspresi berikut

Definisi JarakJarak antara dua titik u,v pada suatu graf G ditulis d(u,v) dengan d(u,v)= 0 jika u=v; dan d(u,v)= k, jika uv dimana k adalah panjang lintasan terpendek yang menghubungkan titik u dan titik v. Jika tidak ada lintasan yang menghubungkan titik u, v, maka d(u,v)= .

Contoh. Perhatikan graf berikut.

14u32

41

76

5

1298

v1110

13

Untuk menghitung jarak dari titik u ke titik v, terlebih dahulu ditentukan lintasan terpendek dari titik u ke titik v tersebut.Lintasan dari titik u ke titik v adalah:P1: u, 1, 3, 2, 4, 14, 6, 7, v ;P2: u, 1, 2, 4, 6, 7, v;P3: u, 1, 5, 2, 4, 6, 9, 13, 10, 12, 11, 8, 7, v ;P4: u, 1, 5, 4, 6, 9, 10,11, v ; dan seterusnya.Lintasan terpendek adalah P2 dengan panjang 6. Jadi jarak dari titik u ke titik v adalah 6 atau d(u,v)= 6.

Subgraf dari graf lengkap yang mempunyai karakteristik tertentu biasanya lebih mudah dikenali dan pada umumnya telah mempunyai nama. Pembahasan tentang subgraf-subgraf tersebut disajikan pada subbab ini yakni meliputi konsep graf lengkap, jalan, lintasan, siklus, graf pohon, graf bintang, graf roda, dan graf bipartit dan multipartit.

1. Graf LintasanDefenisi 6Graf lintasan dengan n 1 titik adalah graf yang titik-titiknya dapat diurutkan dalam suatu barisan u1,u2,...,un sedemikian sehingga E (P)={ui,ui+1: i = 1,...,n-1}. Graf lintasan dengan n titik di notasikan dengan Pn.

...v1v2v3v4v5vnGambar 2.5Contoh graf lintasan diberikan pada gambar 2.5.

2. Graf SiklusDefinisi 7Jika Pn := v1,v2,...,vn adalah suatu graf lintasan berorde n dan n 3, maka graf Cn := Pn + {v1,v2} disebut siklus berorde n. Panjang Pn adalah n-1, yaitu banyaknya sisi pada Pn dan panjang siklus Cn adalah n. Graf siklus untuk n titik dinotasikan dengan Cn . Contoh graf siklus diberikan pada gambar 2.6.

v3Gambar 2.6...v1v2v4v5vn

Panjang suatu lintasan adalah banyaknya sisi yang ada pada lintasan tersebut. Pada suatu graf yang memuat siklus tentulah ada yang mempunyai panjang terbesar dan ada yang terkecil. Panjang siklus terkecil disebut girt dan dinyatakan dengan g(G) dan panjang siklus terbesar disebut Keliling (circumference) pada graf G dinyatakan dengan c(G). G:Gambar 2.6a

Graf pada gambar 2.6a mempunyai g(G)=3 dan c(G)=8Pada suatu graf terhubung setiap dua titik simpulnya dihubungkan oleh paling sedikit dua lintasan. Karena itu lintsan-lintasan tersebut ada yang pendek dan ada yang panjang. Panjang lintasan terpendek yang menghubungkan dua titik menunjukkan jarak kedua titik tersebut dan dinyatakan oleh d(u,v). Lebih jelasnya diberikan definisi berikut.

3. Graf Pohon Konsep tentang pohon muncul secara eksplisit dalam karya Gustav Kirchof (1824-1887), yang menggunakan gagasan teori graf dalam menentukan arus listrik untuk rangkaian (sirkuit) listrik. Kemudian, Arthur Caylay (1821-1895), James J. Sylvester (1806-1897), George Polya (1887-1985) , dan beberapa orang lainnya menggunakan pohon untuk mencacah banyaknya molekul kimia. Pohon adalah salah satu jenis graf yang menarik untuk dikaji karena mempunyai struktur yang berbeda-beda. Gambar pada Contoh 1, berturut-turut adalah Lintasan dan Siklus dengan 5 titik. Sedangkan Contoh 2 adalah graf pohon dengan 6 titik P6.

Contoh1. Graf lintasan P4 dan siklus C4.

P4C4Contoh 2. Pohon P8.

Misalkan Tn adalah pohon dengan n titik. Titik-titik mberderajat satu pada Tn disebut daun dan titik-titik yang berderajat lebih dari satu disebut ruas. Pohon berakar adalah pohon yang mempunyai satu titik tertentu sebagai akar. Pohon berakar dengan n titik dan akar yang diberi label s dinotasikan dengan Tn(s). Pohon berakar Tn(s) disebut pohon berakar bercabang-k (k-ary tree) jika Tn(s) berderajat maksimum k+1.

Teorema 1.Misalkan G adalah suatu graf dengan p titik. Tunjukkan bahwa ketiga pernyataan berikut adalah ekivalen. a) G adalah pohon;b) G terhubung dan mempunyai p -1sisi (ukuran);c) G berukuran p-1 dan tidak memeuat siklus.

Bukti. Terdapat tiga tahap dalam pembuktian.

Tahap 1. Diketahui a) akan dibuktikan b).Misalkan G adalah pohondengan p titik. Menurut definisi G adalah terhubung. Misalkan P1 adalah lintasan terpanjang dengan r titik, r < p. Maka banyaknya sisi pada P1 adalah r-1 dan mempunyai dua titik ujung (daun), sebut t1 dan t2. Karena P1 adalah lintasan terpanjang, maka titik lain dari G tidak akan terkait dengan t1 atau t2. Berarti titik-titik lain dari G terkait pada ruas dalam P1. Dalam hal ini penambahan satu titik pada ruas P1 akan menambah 1 sisi. Karena banyaknya titik yang bertambah adalah p-r, maka banyaknya sisi yang bertambah pada P1 juga adalah p-r. Akibatnya, banyaknya sisi pada G sebanyak r-1+p-r = p-1.

Tahap 2. Diketahui b) akan dibuktikan c). Misalkan G terhubung dan mempunyai p -1sisi. Akan dibuktikan dengan cara kontradiksi. Misalkan G mempunyai siklus, perdefinisi G mempunyai p sisi. Kontradiksi dengan yang diketahui bahwa G berukuran p-1. Jadi mestilah tidak mempunyai siklus.

Tahap 3. Diketahui c) akan dibuktikan a).Misalkan G berukuran p-1 dan tidak memeuat siklus. Tinggal menunjukkan bahwa G adalah graf terhubung. Andaikan G tak terhubung, berarti G terdiri dari beberapa komponen dimana setiap komponen tidak memiliki siklus (merupakan pohon). Misalkan terdiri dari k komponen, sebut T1, T2, ...., Tk dengan titik masing-masing p1, p2, p3, ..., pk dan sisi berturut-turut p1-1, p2-1, p3-1, ..., pk-1. Jadi banyaknya sisi pada G adalah p1-1+p2-1+...+pk-1=p1+p2+...+pk-k atau sama dengan p-k. Hal ini kontradiksi dengan yang diketahui bahwa G berukuran p-1. Jadi mestilah G terhubung. Dengan demikian G adalah graf terhubung tanpa siklus. Jadi G adalah graf pohon.

Soal 1. Gambar semua pohon dengan 5 titik.Jawab. Berikut ini adalah beberapa bentuk pohon yang terdiri dari 5 titik.

Soal 2. Gambar semua pohon dengan 7 titik dan berderajat maksimum lebih dari 4.Jawab. Pohon yang terdiri dari 7 titik mempunyai derajat paling besar 6. Jadi graf pohon dengan 7 titik dan berderajat maksimum lebih dari 4 adalah graf pohon yang terdiri dari 7 titik dengan derajat tertinggi 5 dan 6.

i. Graf Bintang dan Graf RodaSalah satu jenis graf yang termasuk graf pohon yang paling sederhana selain lintasan adalah bintang. Bintang Sn dapat didefinisikan sebagai pohon yang mempunyai satu titik berderajat n-1 dan yang lainnya berderajat satu. Sedangkan roda adalah graf yang diperoleh dari siklus Ck dengan menambahkan satu titik, sebut x dan menambahkan k sisi dari titik x ke semua titik di Ck. Roda dengan k titik dinotasikan dengan Wk-1. Graf pada Contoh 3 berikut adalah graf bintang dan roda.

Contoh 3.

S6W5

Graf G bipartit jika V(G) dapat dipartisi kedalam dua subhimpunan tak kosong V1 dan V2, sedemikian sehingga untuk setiap sisi e=uvE(G), berlaku u V1 dan vV2 atau v V1 dan u V2 . Graf G dikatakan graf bipartit lengkap, jika E(G)={uv: uV1, vV2 dan dinotasikan Kn,m. Berikut ini adalah graf lengkap dengan 5 titik dan graf bipartit lengkap K3,5. K5K3,5

Teorema 3Graf nontrivial G adalah bipartit jika hanya jika G tidak memuat siklus dengan panjang ganjilBukti. Misalkan G tidak memuat siklus dengan panjang ganjil. Asumsikan G terhubung. Misalkan u adalah sebarang titik di G, dan U adalah himpunan yang memuat titik-titik dengan panjang genap dari u. Misalkan pula W adalah himpunan yang memuat titik dengan panjang ganjil dari u. Dengan demikian {U, W} adalah koleksi partisi dari V(G). Anggaplah bahwa u di U, berarti d(u,u)=0.

U 1 2 5 4 6 3 7 U: u 2 4 6

W : 1 3 5 7 Kita klaim bahwa setiap sisi dari G mengaitkan suatu titik di U dan suatu titik di W. Andaikan itu tidak benar. Berarti terdapat satu sisi di G yang mengaitkan dua titik di U atau dua titik di W, sebut itu ux E(G) dengan w,x W. Karena d(u,w) dan d(u,x) duanya ganjil, maka dapat ditulis d(u,w)=2s+1 dan d(u,x)= 2r+1 untuk suatu bilangan asli s, r. Labeli titik-titik dari u ke w dan dari u ke x sebagai berikut.U=v0, v1, ..., v2s+1=w dan u=x0, x1, ....., x2r+1=x. Dua lintasan tersebut tambah sisi wx memebentuk siklus C, dengan C : u, v1, ......, v2s+1=w, x= x2r+1 , ......, x1, x0=u.Siklus C mempunyai panjang 2s+1 + 2r+1 tambah satu sisi wx. Dengan kata lain panjang C adalah (2s+1)+(2r+1)+1= 2(s+r+1)+1. Nilai 2(s+r+1)+1 adalah ganjil. Jadi G memiliki siklus dengan panjang ganjil. Hal ini kontradiksi dengan G tidak memuat siklus ganjil. Jadi, tidak benar bahwa terdapat sisi di G yang mengaitkan dua titik pada partisi yang sama. Dengan kata lain, setiap sisi dari G mengaitkan suatu titik di partisi yang satu dan suatu titik di partisi yang satunya. Menurut definisi G adalah bipartit. Misalkan G nontrivial dan bipartit. Akan ditunjukkan G tidak memuat siklus ganjil. Partisi himpunan V(G) ke dalam dua subhimpunan sebut U dan W sedemikian sehingga setiap sisi di G mengaitkan suatu titik di U dan suatu titik di W. Misalkan e1=u1w1, e2=u2w2, e3=u3w3, dan e4=u4w4. Jika titik tersebut berbeda semua maka G tidak memuat siklus. Jika masih ada sisi lain misal e di G maka e=uiwj, 1,j=1,2,3,4, dan ij, sebut i=2 dan j=3. Dalam hal ini, terdapat lintasan P3: w2, u2, w3, u3 dengan panjang 3. Jika lintasan ini terletak pada suatu siklus C, maka C=E(P3)+{u3,w2} dengan panjang 4. Situasi lain akan selalu serupa. Karenanya dapat disimpulkan bahwa G tidak memuat siklus ganjil.

U: u 1 u2 u3 u4

W : w1 w2 w3 w4