Teori Graf Dan Diagram Pohon [PDF]

Citation preview

TEORI GRAF DAN DIAGRAM POHON DOSEN PENGAMPU : FIKA INDAH PERAWANSA, M.Pd



Disusun Oleh:



PUTRI NATASYA LUBIS (0701191101) PUTRI PRATIWI PANE



(0701192048)



MUHAMMAD WAAFI ALDIAN



(0701192059)



RIDHO TRI SOEKMANEGARA



(0701193200)



RIKO ALDINATA



(0701193205)



UNIVERSITAS ISLAM NEGERI SUMATERA UTARA FAKULTAS SAINS DAN TEKNOLOGI ILMU KOMPUTER 2020



KATA PENGANTAR Assalamu’alaikum warahmatullahi wabarakatuh Segala puju bagi Allah SWT yang telah memberikan penulis kemudahan sehingga dapat menyelesaikan makalah ini dengan tepat waktu. Shalawat serta salam semoga terlimpah curahkan kepada baginda tercinta kita yaitu Nabi Muhammad SAW yang kita nanti – natikan syafa’atnya di akhirat nanti. Penulis mengucapkan syukur kepada Allah SWT atas limpahan nikmat sehat – Nya, baik itu berupa sehat fisik maupun akal pikiran, shingga penulis mampu menyelesaikan pembuatan makalah yang berjudul “Teori Graf dan Diagram Pohon”. Adapun tujuan dibuatnya tugas ini untuk memenuhi tugas Matematika Diskrit dan untuk menambah wawasan baik dari penulis maupun pembaca. Penulis juga mengucapkan terimakasih kepada Fika Indah Perawansa, M.Pd selaku dosen pengampu Matematika Diskrit di Universitas Islam Negeri Sumatera Utara. Penulis menyadari bahwa tugas ini masih banyak kekurangan dan kelemahannya, baik dalam isi maupun sistematiknya. Hal ini disebabkan oleh keterbatasan pengetahuan danwawasan penulis. Oleh sebab itu, penulis sangat mengharapkan kritik dan saran untuk menyempurnakan tugas ini. Akhir kata penulis mengharapkan semoga tugas makalah “Teori Graf dan Diagram Pohon” ini dapat memberikan manfaat, khususnya bagi penulis dan umumnya bagi pembaca. Wassalamu’alaikum warahmatullahi wabarakatuh



Medan, 13 Mei 2020



Penulis 1



DAFTAR ISI KATA PENGANTAR...............................................................................................................................1 DAFTAR ISI..................................................................................................................................................2 BAB I : PENDAHULUAN........................................................................................................................3 A. Latar Belakang Masalah..................................................................................................................3 B. Rumusan Masalah............................................................................................................................3 BAB II : PEMBAHASAN.........................................................................................................................4 A.



TEORI GRAF................................................................................................................................4 1.



Teori Graf..................................................................................................................................4



2.



Definisi Graf...............................................................................................................................4



3.



Terminologi Graf.......................................................................................................................6



B.



DIAGRAM POHON....................................................................................................................10 1.



Diagram Pohon........................................................................................................................10



2.



Definisi Pohon..........................................................................................................................10



3.



Definisi Hutan..........................................................................................................................11



4.



Sifat-Sifat Pohon......................................................................................................................11



5.



Pohon Berakar (RootedTree)...................................................................................................13



6.



Pohon Merentang.....................................................................................................................14



7.



Pohon Merentang Minimum...................................................................................................15



BAB III : PENUTUP...............................................................................................................................18 A.



Kesimpulan..................................................................................................................................18



B.



Saran.............................................................................................................................................18



DAFTAR PUSTAKA..............................................................................................................................19



2



BAB I : PENDAHULUAN



A. Latar Belakang Masalah Teori graf adalah bagian dari matematika diskrit yang banyak digunkan sebagai alat bantu untuk menggambarkan atau manyatakan suatu persoalan agar lebih mudah dimengerit dan diselesaikan. Banyak persoalan akan lebih jelas untuk diterangkan bila dapat dipresentasikan dalam bentuk graf. Dasar teori graf berawal pada abad ke-18 yang bermula dari masalah jembatan Königsberg. Warga kota Königsberg ingin melewati 7 jembatan pada sungai Pregel di kota Königsberg tepat satu kali dan kembali lagi ke tempat awal. Masalah ini telah dibuktikan tidak mungkin oleh Euler. Dalam pembuktian tersebut Euler menggunakan teori Graf. Salah satu topik dari teori Graf adalah tentang pohon. Konsep pohon merupakan konsep yang paling penting karena konsep ini mampu mendukung penerapan Graf dalam berbagai ilmu. Pohon adalah graf terhubung yang asiklik (tidak memuat sikel). Sebuah pohon selalu terdiri dari n simpul dan n – 1 jalur pohon yang merupakan subgraph dari suatu graf terhubung G, yang memuat seluruh simpul dari G disebut pohon rentang.



B. Rumusan Masalah 1. Teori Graf 2. Definisi Graf 3. Terminologi Graf 4. Diagram Pohon 5. Definisi Pohon 6. Definisi Hutan 7. Sifat – Sifat Pohon 8. Pohon Berakar 9. Pohon Merentang 10.Pohon Merentang Minimum



3



BAB II : PEMBAHASAN A. TEORI GRAF 1. Teori Graf Teori graf merupakan pokok bahasan yang banyak penerapannya pada masa kini. Pemakaian teori graf telah banyak dirasakan dalam berbagai ilmu, antara lain : optimisasi jaringan, ekonomi, psikologi, genetika, riset operasi (OR), dan lain-lain. Makalah pertamatentang teori graf ditulis pada tahun 1736 oleh seorang matematikawan Swiss yangbernama Leonard Euler. Masalah yang dikemukakan Euler : Dapatkah melewati setiap jembatan tepat sekali dan kembali lagi ke tempat semula? Berikut adalah sketsa yang merepresentasikan ilustrasi jembatan Königsberg yang pada gambar diatas. Himpunan titik yaitu {A, B, C, D}merepresentasikan sebagai daratan, dan garis yang menghubungkan titik-titik tersebut adalah sebagai jembatan



Jawaban pertanyaan Euler adalah tidak mungkin. Agar bisa melalui setiap jembatan tepat sekali dan kembali lagi ke tempat semula maka jumlah jembatan yang menghubungkan setiap daratan harus genap.



2. 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 Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut.Notasi sebuah graf adalah G = (V,E), dimana : 



V merupakan himpunan tak kosong dari simpul-simpul (vertices) 4



misalkanV = {v1,v2, ... ,vn} 



E merupakan himpunan sisi – sisi yang menghubungkan sepasang simpul, misalkan E={e1,e2, …,en}



Contoh : Graf dari masalah jembatan Königsberg dapat disajikan sebagai berikut :



Misalkan graf tersebut adalah G(V,E) dengan V= {A,B,C,D} E= { (A,C) (A,C), (A,B), (A,B), (B,D), (A,D), (C,D) } = {e1,e2,e3,e4,e5,e6,e7}



Pada graf tersebut sisi e1 = (A,C) dan sisi e2 = (A,C) dinamakan Sisi-ganda (multiple edges atau paralel edges) karena kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul A dan simpul C. Begitu pun dengan sisi e3 dan sisi e4.Sementaraitu, pada graf diatas, tidak terdapat gelang (loop), yaitu sisi yang berawal dan berakhirpada simpul yang sama.



5



Dari definisi graf, himpunan sisi (E) memungkinkan berupa himpunan kosong.Jika graf tersebut mempunyai himpunan sisi yang merupakan himpunan kosong maka graf tersebut dinamakan graf kosong (null graph atau empty graph). 3. Terminologi Graf Ada beberapa terminologi graf yang perlu diketahui, antara lain : ketetanggaan antara dua simpul, bersisian , derajat suatu simpul, dan lain-lain. Berikut ini adalahbeberapa terminoogi yang penting, yaitu : 1. Bertetangga (Adjacent) Dua buah simpul dikatakan Bertetangga jika kedua simpul tersebut terhubung langsung oleh suatu sisi. Contoh : Perhatikan graf berikut



Pada graf diatas : simpul P bertetangga dengan simpul Q dan S, tetapisimpul P tidak bertetangga dengan simpul R. 2. Bersisian (Incidency) Suatu sisi e dikatakan bersisian dengan simpul v1 dan simpul v2 jika e menghubungkankedua simpul tersebut, dengan kata lain e = (v1,v2). Contoh : Perhatikan graf dari masalah jembatan Königsberg berikut ini



6



maka e1 bersisian dengan simpul A dan simpul C, tetapi sisi tersebut tidak berisian dengan simpul B. 3. Simpul Terpencil (Isolated Vertex) Jika suatu simpul tidak mempunyai sisi yang bersisian dengannya maka simpul tersebut dinamakan simpul terpencil. Contoh : Perhatikan graf berikut



Simpul T dan simpul U merupakan simpul terpencil. 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 maupunsisi-ganda. Contoh :



7



1. Graf sederhana



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



Dengan demikian, graf sederhana pun merupakan graf ganda (multi graph)



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



8



Beberapa jenis graf berarah yang perlu diketahui adalah : 1. 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 sisiganda) Contoh : Graf berarah :



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



9



B. DIAGRAM POHON 1. Diagram Pohon Di antara sekian banyak konsep dalam teori graf, konsep pohon (tree) merupakan salah satu konsep yang paling penting, karena terapannya yang luas dalam berbagai bidang ilmu. Banyak terapan, baik dalam bidang ilmu computer maupun di luar bidang ilmu komputer, yang telah mengkaji pohon secara intensif sebagai objek matematika. Dalam kehidupan sehari-hari, orang telah lama menggunakan pohon untuk menggambarkan hirarkhi. Misalnya, pohon silsilah keluarga, struktur organisasi, organisasi pertandingan, dan lain-lain. Para ahli bahasa menggunakan pohon untuk menguraikan kalimat, yang disebut pohon pasing (parse tree) Pohon sudah lama digunakan sejak tahun 1857, ketika matematikawan inggris Arthur Cayley menggunakan pohon untuk menghitung jumlah senyawa kimia. Bab ini membahas pohon dari sudut pandang teori graf. Pohon sebagai struktur data rekursif merupakan bagian dari perkuliahan Struktur Data.



2. Definisi Pohon Pohon T adalah graf tak berarah terhubung yang tidak mengandung sirkuit. Pohon biasa juga disebut secara khusus yaitu pohon bebas (free tree), hal ini untuk membedakan pohon dengan pohon berakar (rooted tree). Dari definisi tersebut diketahui ada 2 syarat dari pohon yaitu: 1) Graf terhubung 2) Tidak mengandung sirkuit. Syarat ini harus dipenuhi kedua-duanya. Contoh:



G1



G2



G3



G4 10



G3 bukan pohon karena mengandung sirkuit, misalnya sirkuit a-d-f-a. G4 bukan pohon karena bukan graf terhubung(titik silang jalur (a,f) dan jalur (b,e) bukan menyatakan simpul). Kita ketahui bahwa definisi pohon mengacu pada graf, maka sebuah pohon mungkin saja hanya mengandung sebuah simpul tanpa sebuah jalur pun (ingat kembali graftrivial) Selanjutnya, kumpulan pohon disebut hutan.



3. Definisi Hutan Hutan (forest) adalah:  Kumpulan pohon yang saling lepas, atau  Graf tidak terhubung yang tidak mengandung sirkuit. Setiap komponen di dalam graf terhubung tersebut adalah pohon.



4. Sifat-Sifat Pohon  Teorema: Misalkan G = (V, E) adalah graf tak-berarah sederhana dan jumlah simpulnya n. Maka, semua pernyataan di bawah ini adalah ekivalen: 1) G adalah pohon. 2) Setiap pasang simpul di dalam G terhubung dengan lintasan tunggal. 3) G terhubung dan memiliki m = n – 1 buah sisi.



11



4) G tidak mengandung sirkuit dan memiliki m = n – 1 buah sisi. 5) G tidak mengandung sirkuit dan penambahan satu sisi pada graf akan membuathanya satu sirkuit. 6) G terhubung dan semua sisinya adalah jembatan.



Contoh: Tentukan mana diantara graf – graf dibawah ini yang merupakan pohon atau hutan!



a. Pohon, karena graf tersebut terhubung dan tidak memiliki sirkuit; b. Pohon, karena graf tersebut terhubung dan tidak memiliki sirkuit; 12



c. Bukan pohon (dan bukan hutan), karena mengandung sirkuit v3, v4, v5; d. Hutan, karena merupakan kumpulan pohon.



5. Pohon Berakar (RootedTree) Pohon berakar adalah sebuah pohon dimana ada satu simpulnya yang dikhususkan dari simpulnya dan simpul tersebut disebut dengan akar (root), dan jalur-jalurnya digambarkan menjauh dari akar. Derajat masuk simpul akar adalah 0 (nol). Derajat masuk simpul-simpul lainnya adalah 1. Daun (= simpul terminal) adalah simpul yang mempunyai derajat keluar 0 (nol). Cabang (= simpul dalam) adalah simpul yang mempunyai derajat keluar bukan 0 (nol). Setiap simpul pada pohon berkar dapat dicapai dari akar dengan sebuah lintasan tunggal. Lintasan dalam pohon berakar selalu berasal dari akar (dari atas ke bawah).



Istilah – Istilah dalam Pohon Berakar  Anak: simpul y dikatakan anak dari simpul x jika terdapat jalur dari x ke y.  Orangtua: simpul x dikatakan orangtua dari simpul y jika terdapat jalur dari x ke y.  Lintasan: lintasan sederhana tunggal(simpul-jalur-simpul) dari simpul u ke simpul v sedemikian sehingga simpul u adalah leluhur atau orangtua dari simpul v. lintasan mempunyai panjang yaitu banyaknya jalur yang dilalui dalam lintasan.  Leluhur: simpul u adalah leluhur dari simpul v jika terdapat lintasan dari simpul u ke simpul v.  Keturunan: simpul v adalah keturunan dari simpul u jika terdapat lintasan dari simpul u ke simpul v.  Saudara kandung: simpul-simpul yang mempunyai orangtua yang sama.  Derajat: derajat simpul u adalah banyaknya anak dari simpul v. Derajat pohon berakar adalah derajat maksimum dari simpul-simpulnya. Derajat sebuah simpul pada graf berbeda dengan derajat simpul pada pohon.  Daun: simpul yang berderajat nol atau simpul yang tidak memiliki anak.  Cabang (simpul dalam): simpul u disebut cabang jika simpul itu mempunyai anak.



13



 Aras (level): aras dari simpul u adalah panjang lintasan dari akar ke simpul v. Aras dari akar adalah nol (0)  Tinggi (kedalaman): aras (level) maksimum dari sebuah pohon berakar. Contoh: Tentukan daun dan titik cabang pohon pada gambar di bawah ini.



- Titik v4, v5, v6, v7, v8 derajatnya = 1, jadi titik – titik tersebut merupakan Daun. - Titik v1, v2, v3 derajatnya masing – masing >1, maka titik – titik tersebut merupakan titik cabang.



6. Pohon Merentang Pohon merentang dari graf terhubung adalah subgraf merentang yang berupa pohon. Atau dapat diartikan pula dengan subgraf terhubung yang mengandung semua simpul pada graf dan tidak mengandung sirkuit. Jadi, himpunan simpul pada pohon merentang dari graf G sama dengan himpunan simpul pada graf G. Pohon merentang diperoleh dengan memutus sirkuit di dalam graf. Caranya: Pilih sebuah sirkuit, putus sirkuit tersebut dengan menghapus salah satu jalurnya, periksa apakah masih mengandung sirkuit atau tidak. Bila masih mengandung sirkuit maka ulangi langkah tersebut kembali sampai semua sirkuit pada graf terhubung G tidak ada lagi. Pohon yang diperoleh pasti pohon merentang karena kita hanya menghapus jalur, dan tidak menghapus simpul. Contoh:



14



Setiap graf terhubung mempunyai paling sedikit satu buah pohon merentang. Graf tak-terhubung dengan komponen mempunyai k buah pohon merentang disebut hutan merentang (spanning forest).



Mengenal Aplikasi Pohon Merentang Teori mengenai pohon merentang ini mempunyai beberapa aplikasi, diantaranya yaitu: 1. Jumlah ruas jalan seminimum mungkin yang menghubungkan semua kota sehingga setiap kota tetap terhubung satu sama lain. Hal ini diperlukan misalnya untuk meminimumkan biaya pembuatan jalan. 2. Perutean (routing) pesan pada jaringan komputer. Hal ini diperlukan misalnya untuk meminimumkan panjang kabel komputer yang dibutuhkan. Contoh:



7. Pohon Merentang Minimum Sebuah graf berbobot yang terhubung mungkin saja mempunyai lebih dari 1 pohon merentang. Adakalanya kita memerlukan pemecahan masalah yaitu bagaimana memperoleh pohon merentang yang berbobot minimum. Pohon merentang yang berbobot minimum dinamakan pohon merentang minimum (minimum spanning tree). 15



Terdapat dua buah algoritma yang dapat digunakan untuk memperoleh pohon merentang minimum dari sebuah graf berbobot yang terhubung G. Algoritma tersebut yaitu: 1. Algoritma 2. Algoritma Kruskal Contoh: Berikut ini gambar sebuah graf berbobot terhubung. Akan ditemukan pohon merentang minimumnya dengan menggunakan algoritma Prim dan algoritma Kruskal.



1. Algoritma Prim Misalkan T adalah pohon merentang yang jalur-jalurnya diambil dari graf G. Algoritma Prim membentuk pohon merentang minimum langkah per langkah. Pada setiap langkah kita mengambil jalur dari graf G yang mempunyai bobot minimum dan bersisian dengan simpul-simpul di dalam T tetapi tidak membentuk sirkuit di dalam T. Algoritma Prim: Langkah 1 : Pilih jalur yang berbobot minimum, masukkan ke dalam T. Langkah 2 : Pilih jalur (u, v) yang mempunyai bobot minimum dan bersisian dengan simpul di T, tetapi (u, v) tidak membentuk sirkuit di T. Masukkan (u, v) ke dalam T. Langkah 3 : Ulangi langkah 2 sebanyak n – 2 kali atau dengan kata lain sampai T telah memuat semua simpul pada Graf. Jumlah langkah seluruhnya di dalam algoritma Prim adalah (1 + (n – 2)) = (n – 1), dengan n banyak simpul.



16



2. Algoritma Kruskal Algoritma Kruskal sedikit lebih sederhana dibandingkan dengan algoritma Prim dalam pemeriksaan jalurjalur yang akan dipilih. Hal ini karena pada algoritma Prim, setiap langkah per langkah jalur yang dipilih selain harus yang berbobot terkecil harus pula selalu terhubung dengan pohon yang sudah terbentuk sebeumnya. Sedangkan pada algoritma Kruskal ini, pertimbangan memilih jalur hanya bobotnya yang harus terkecil. Algoritma Kruskal: Langkah 0 : (Persiapan) Jalur-jalur pada graf diurutkan dari bobot yang terkecil hingga terbesar. Langkah 1 : T masih kosong. Langkah 2 : Pilih jalur (u, v) dengan bobot minimum yang tidak membentuk sirkuit di T. Tambahkan (u, v) ke dalam T. Langkah 3 : Ulangi langkah 2 sebanyak n – 1 kali



17



BAB III : PENUTUP A. Kesimpulan Teori Graf merupakan pokok bahasan yang sudah tua usianya namun memiliki banyak terapan sampai saat ini. Graf digunakan untuk mempresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graf adalah dengan menyatakan objek dinyatakan sebagai noktah, bulatan, atau titik. Sedangkan hubungan antara objek dinyatakan dengan garis. Salah satu topik dari teori Graf adalah tentang pohon. Konsep pohon merupakan konsep yang paling penting karena konsep ini mampu mendukung penerapan Graf dalam berbagai ilmu. Pohon adalah graf terhubung yang asiklik (tidak memuat sikel). Sebuah pohon selalu terdiri dari n simpul dan n – 1 jalur pohon yang merupakan subgraph dari suatu graf terhubung G, yang memuat seluruh simpul dari G disebut pohon rentang.



B. Saran Semoga pembaca maupun pemakalah dapat memahami dan menerapkan materi diatas dan memjadi lebih baik lagi.



18



DAFTAR PUSTAKA Andhany Ella. Matematika Diskrit.(Medan : Universitas Islam Negeri Sumatera Utara, 2018) https://www.academia.edu/32450816/Teori_Graf.pdf



19