MAKALAH TEORI GRAFGRAF BERARAH ATAU DIGRAF

DI SUSUN OLEH:KELOMPOK VIANGGOTA :1. HANJAIRIN( 12 221 022 )2. MAIFTAHUL AHYAR( 12 221 001 )3. SAIFUL JAMIL( 12 221 0 )4. NININGSIH( 11 221 012 )5. ERNA DIAN PRATIWI( 08 221 075 )6. MIFTAHUL INDRA( 10 221 015 )

JURUSAN PENDIDIKAN MATEMATIIKAFAKULTAS PENDIDIKAN MATEMATIKA DAN ILMU PENGETAHUAN ALAMINSTITUT KEGURUAN DAN ILMU PENDIDIKAN ( IKIP ) MATARAM 2015/2016

KATA PENGANTAR

Puji syukur atas kehadirat Allah SWT yang telah memberikan limpahan rahmat serta hidayah-Nya, sehingga penulis dapat menyelesaikan makalah tentang Graf Berarah atau Digraf ini tepat pada waktunya. Makalah ini dibuat guna memenuhi tugas yang telah diberikan oleh dosen mata kuliah Teori Graf.

Makalah yang berjudul Graf Berarah atau Digraf ini diharapkan dapat bermanfaat bagi pembaca pada umumnya termasuk penulis sendiri pada khususnya. Penulis juga ucapkan terimakasih kepada yang telah membantu dalam penyusunan makalah ini sehingga makalah ini dapat terselesaikan dengan tepat waktu.

Penulis juga menyadari bahwa, dalam pembuatan makalah ini terdapat banyak sekali kekurangan, maka dari itu kritik serta saran yang sifatnya membangun penulis terima dengan tulus hati.

Mataram, Juni 2015

Penulis

DAFTAR ISI

HALAMAN SAMPULHal

KATA PENGANTARi

DAFTAR ISIii

BAB I PENDAHULUAN10. Latar Belakang10. Rumusan Masalah20. Tujuan2BAB II PEMBAHASAN30. Pengertian Digraf30. Cara Menentukan Derajat Titik pada Digraf30. Menentukan Digraf isomorfik dan digraf identik40. Bentuk Digraf khusus6BAB III PENUTUP73.1 Simpulan73.2 Saran7DAFTAR PUSTAKA8

BAB IPENDAHULUAN1.1 Latar BelakangTeori graf merupakan salah satu ilmu dalam bidang matematika yang mempelajari himpunan titik yang dihubungkan oleh himpunan sisi atau busur. Suatu graf adalah diagram yang terdiri dari noktah-noktah tidak kosong yang disebut titik (vertex) dan dihubungkan oleh garis yang disebut sisi (edge). Terdapat dua jenis graf menurut orientasi arah pada sisinya yaitu graf yang tidak mempunyai orientasi arah disebut graf tak berarah (undirected graph) dan graf yang mempunyai orientasi arah disebut graf berarah (directed graph / digraph). Teori graf saat ini menjadi topik yang banyak mendapat perhatian, karena model-model yang ada pada teori graf berguna untuk aplikasi yang luas, seperti masalah dalam jaringan komunikasi, transportasi, ilmu komputer, riset operasi, dan lain sebagainya. Suatu graf adalah himpunan benda-benda yang disebut verteks (atau node) yang terhubung oleh edge-edge (atau arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan verteks) yang dihubungkan oleh garis-garis (melambangkan edge).Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan bantuan graf. Jaringan persahabatan pada Friendster bisa direpresentasikan dengan graf: verteks-verteksnya adalah para pemakai Friendster dan ada edge antara A dan B jika dan hanya jika A berteman dengan B. Perkembangan algoritma untuk menangani graf akan berdampak besar bagi ilmu komputer. Sebuah struktur graf bisa dikembangkan dengan memberi bobot pada tiap edge. Graf berbobot dapat digunakan untuk melambangkan banyak konsep berbeda. Sebagai contoh jika suatu graf melambangkan jaringan jalan maka bobotnya bisa berarti panjang jalan maupun batas kecepatan tertinggi pada jalan tertentu. Ekstensi lain pada graf adalah dengan membuat edgenya berarah, yang secara teknis disebut graf berarah atau digraf (directed graph).Salah satu aplikasi dalam teori graf adalah menentukan kota terjauh (maksimal lintasan terpendek) dari suatu kota ke kota lain yang terdiri dari kumpulan kota dalam suatu daerah. Masalah ini ekuivalen dengan menentukan eksentrisitas titik pada graf.

1.2 Rumusan MasalahAdapun masalah masalah yang dapat dirumuskan adalah sebagai berikut :1. Apakah pengertian digraf ?2. Bagaimana cara menentukan derajat titik pada graf?3. Bagaimana menentukan digraf isomorfik dan digraf indentik?4. Bagaimana bentuk dari digraf khusus?1.3 TujuanAdapun tujuan dari makalah ini adalah sebagai berikut:1. Untuk mengetahui pengertian digraf.2. Untuk mengetahui cara menentukan derajat titik pada graf .3. Untuk mengetahui digraf isomorfik dan digraf identik.4. Untuk mengetahui bentuk dari digraf khusus.

BAB IIPEMBAHASAN2.1 Pengertian DigrafGraf berarah atau digraf D adalah struktur yang terdiri dari himpunan tak kosong dan berhingga, yang unsurnya disebut titik, beserta himpunan pasangan berurutan dari dua titik berbeda yang disebut busur. Kata digraf merupan adopsi dari kependekan kata directed graf. Seperti pada graf, himpunan itik pada digraf D dinotasikan dengan V(D), dan dan himpunan busur dinotasikan dengan A(D). Banyak unsur di V(D), yakni V(D), disebut order dari D dan dinotasikan dengan p(D), sedangkan banyaknya unsur da A(D), yakni A(D), disebut ukuran dari D dan dinotasikan dengan q(D). Jika digraf yang dibicarakan hanya digraf D, maka order dan ukuran dari D masing-masing cukup ditulis p dan q. Digraf dengan ord p dan ukuran q dapat ditulis digraf (p,q).Jika a = (u,v) adalah busur pada digraf D, maka a dikatakan memasangkan u dan v. Lebih lanjut, dikatakan a terkait terkait langsung dari (incident from) u dan terkait langsung ke (incident to ) v. Selain itu dikatakan u terhubung langsung (adjacent to) v sedangkan v terhubung langsung dari (adjacent from) u. Dua titi u dan v pada digraf D dikatakan tidak terhubung langsung jika u tidak terhubung langsung ke v atau u tidak terhubung langsung dari v. Pada digraf D, busur (u,v) akan ditulis uv. Sebagai contoh, misal D digraf dengan himpunan titik V(D) = { u, v, w } dan himpunan busur A(D) = { (u, w) , (u, v) }. Maka D dapat digambarkan sebagai berikut.

D : uvPada contoh digraf D ini, titik u terhubung langsung ke v. Dilain pihak, titi v tidak terhubung langsung ke u.

2.2 Derajat Titik pada DigrafMisalkan v adalah titik pada digraf D. Banyaknya titik yang terhubung langsung ke v disebut derajat masuk (indegree) dari v, dan dinotasikan dengan id(v). Banyaknya titik yang terhubung langsung dari v disebut derajat keluat (outdegree) dari v, dan dinotasikan dengan od(v). Sedangkan derajat itik v pada digraf D, dinotasikan dengan deg(v), didefinisikan dengan

deg (v) = od (v) + id (v)

Perhatikan gambar digraf D berikut.

WUv

D:

Berdasarkan gambar diketahui bahwa od (u) = od (v) = od (w) = 1 id(v) = 2 Dan id(v) = id (w) =1jadi diperoleh : deg (u) = 3, deg (v) = 2 , dan deg (w) = 3

Teorema 5.1Misalkan D digraf berorder p dan berukuran q dengan himpunan titik V(D) = {v1, v2, ... , vn } maka: Bukti :Setiap menhitung derajat keluar suatu titik, maka masing masing busur dihitung satu kali, karena setiap busur terkait langsung dari tepat satu titik. Demikian juga, setiap menghitung derajat masuk suatu titik, maka masing masing busur dihitung satu kali, karena setiap busur terkait langsung ke tepat satu titik.

2.3 Digraf Isomorfik dan Digraf IdentikDigraf D dikatakan isomorfik dengan digraf D2 jika erdapat fungsi yang bersifat bijektif dari V(D1) ke V(D2), yang disebut isomorfisme, sedemikian hingga uv A(D1) jika dan hanya jika (u) (v) A(D2). Jika digraf D1 isomorfik dengan digraf D2, maka dinotasikan dengan G H.Dengan mudah dapat diperiksa bahwa relasi isomorfik dengan merupakan relasi ekivalen pada digraf, yakni a. D D (sifat refleksif),b. D1 D2 jika dan hanya jika D2 D1 (sifat simetris), dan c. D1 D2, D2 D3 maka D1 D3 (sifat transitif).Relasi isomorfik pada digraf akan membagi digraf ke dalam klas klas ekivalen. Dua digraf tidak isomorfik jika menjadi anggota klas ekivalen yang berbea, dan isomorfik jika berada dalam klas ekivalen yang sama.Berdasarkan konsep isomorfisme, maka hanya akan ada stu digraf berorder 1 dan berukuran 0, yang disebut digraf trivial, Digraf tak trivial mempunyai orde p 1. Pada ambar berikut, D1 adalah digraf trivial dan D2 adalah digraf tak trivial.

D1 : D2 :

Selain itu, berasarkan isomorfisma, maka hanya ada satu digraf (2,0), digraf (2,1), dan digraf (2,2). Terdapat empat digraf (3,3) sebagaimana nampak pada gambar berikut

Dua digraf D1 dan D2 disebut identik, dinotasikan dengan D1 = D2, jika V(D1) = V(D2) dan A(D1) = A(D2). Dengan kata lain, digraf D identik dengan D2 jika keduanya memuat himpunan busur yang sama. Jika D1 = D2, maka jelaslah D1 D2. Di lain pihak, jika D1 D2, maka belum tentu D1 = D2. Perhatikan digraf berikut, D1 D2 tetapi D1 D2.

2.4 Digraf KhususSuatu digraf D disebut digraf simetris jika uv busur di D, maka vu juga busur di D. Dngan kata lain, D adalah digraf simetris jika uv A(D), maka vu A(D). Digraf D disebut digraf asimetris atau graf berorientasi jika vu A(D). Jadi graf berorientai D dapat diperoleh dari graf G dengan cara memberikan arah pada masing masing sisi di G. Jadi, mengubah sisi pada graf G menjadi busur sama halnya dengan mengubah G menjadi graf berorientasi D. D ini disebut juga orientasi dari G. Pada contoh berikut, D1 simetris, D2 asimetris, dan D3 tidak keduanya.

Digraf D disebut digraf komplit jika untuk sembarang dua titik berbeda u dan v di D, maka paling sedikit satu dari busur uv dan busur vu terapat di D. Dengan kata lain, D adalah digraf komplit jika untuk sebarang u, v V(D), dengan u v, maka uv A(D) atau vu A(D). Digraf D disebut digraf simetris komplit jika untuk sembarang dua titik berbeda u dan v di D, maka busur uv dan busur vu terdapat di D. Digraf asimetris komplit disebut turnamen. Digraf simetris komplit dengan order n, dinotasikan dengan Kn. Digraf Kn mempunyai ukuran n(n-1) dan od(v) = id(v) = n- 1, untuk sebarang v V(Kn). Busur uv dan vu pada digraf Kn selanjutnya akan digambar satu busur dengan dua arah. Perhatika dua gambar digraf K4 berikut.

Digraf D disebut digraf beraturan derajat r atau beraturan r jika od (v) = id(v) = r untuk sebarang v V(D). Digraf Kn adalah digraf beraturan (n-1). Pada contohberikut ini, D1 adalah beraturan -1 dan D2 adalah digraf beraturan -2. Selain itu, digraf D2 adalah turnamen.D1 : D2 :

BAB IIIPENUTUP1.1 KesimpulanDari beberapa uraian materi di atas, dapat disimpulkan bahwa graf berarah atau digraf adalah struktur yang terdiri dari himpunan tak kosong dan berhingga, yang unsurnya disebut titik, beserta himpunan pasangan berurutan dari dua titik berbeda yang disebut busur.Derajat titik pada digraf terdiri dari derajt titik masuk dan derajat titik keluar. Digraf isomorfik dan digraf identik yaitu dikatakan isomorfik jika terdapat fungsi yang bersifat bijektif dan sebaliknya dikatakan identik jika kedua digraf memuat himpunan titik yang sama dan memuat himpunan busur yang sama.1.2 Saran Saran Adapun saran saran dari penulis, yaitu ilmu matematika itu luas dan menarik. Walaupun kebanyakan orang berfikir bahwa ilmu matematika tidak ada penerapan dalam kehidupan sehari hari. Namun, anggapan tersebut kurang tepat karena ilmu matematika sebenarnya sangat dekat dengan keseharian kita, seperti materi digraf dan materi matematika lainnya. Oleh karena itu, sebagai mahasiswa pendidikan matematika atau seseorang yang menyukai ilmu matematika, jangan henti hentinya untuk tetap mengkaji ilmu matematika lebih dalam lagi dan diterapkan dalam kahidupan sehari hari.

DAFTAR PUSTAKA

Munir, rinaldi., Matematika Diskrit,2012, Bandung: Informatika.

Kelompok VI TEORI GRAFPage 8