Makalah matematika Diskrit Tentang Graf
MAKALAH
MATEMATIKA DISKRIT
Disusun oleh :
1. Arif saepudin
2. Faishal imamudin
3. Fauzan mutaqin
4. Faizal agus p.
5. Feby pebryana f
6. Dede fahmi
7. Sholihin prasetyo
8. Ilham septian
SEKOLAH TINGGI MANAJEMEN INFORMATIKA DAN KOMPUTER
S U M E D A N G
2017
KATA PENGANTAR
Puji syukur kami panjatkan kehadirat Allah SWT, yang telah berkenan
memberi petunjuk dan kekuatan kepada kami sehingga makalah, “Graf
Bidang, Graf Planar, Graf Dual” ini dapat diselesaikan. Makalah ini
merupakan salah satu tugas dari mata kuliah Matematika Diskrit di STMIK
Sumedang.
Dalam kesempatan ini kami menyampaikan rasa terima kasih dan penghargaan yang setinggi-tingginya kepada Ibu Annisa Aina Nurwaida, S.Kom dan semua pihak yang telah memberikan bantuan, dorongan, bimbingan dan arahan kepada penyusun.
Dalam makalah ini kami menyadari masih jauh dari kesempurnaan, untuk itu segala saran dan kritik guna perbaikan dan kesempurnaan sangat kami nantikan. Semoga makalah ini dapat bermanfaat khususnya bagi penyusun dan para pembaca pada umumnya.
Sumedang, November 2017
Penyusun,
DAFTAR ISI
KATA PENGANTAR .......................................................................... ii
DAFTAR ISI ......................................................................................... iii
BAB I PENDAHULUAN
1.1 Latar Belakang......................................................................... 1
1.2 Rumusan Masalah.................................................................... 2
1.3 Tujuan...................................................................................... 2
BAB II PEMBAHASAN
2.1 Graf ......................................................................................... 3
2.2 Graf Bidang Dan Planar........................................................... 3
2.2.1 Formula Euler ...................................................................... 3
2.3 Graf Dual ................................................................................ 3
BAB III PENUTUP
3.1 Kesimpulan.............................................................................. 17
DAFTAR PUSTAKA ........................................................................... 18
BAB I
PENDAHULUAN
1.1
Latar Belakang
Teori graf merupakan salah satu kajian matematika yang memiliki banyakterapannya diberbagai bidang sampai saat ini.Dalam kehidupan sehari-hari, grafdigunakan untuk menggambarkan berbagai macam struktur yang ada.Tujuannyaadalah sebagai visualisasi objek-objek agar lebih mudah dimengerti. Beberapacontoh aplikasi graf yang sering dijumpai dalam kehidupan sehari-hari antara lainadalah struktur organisasi, bagan alir, peta rangkaian listrik, dan lain-lain.
Salah satu kelas graf yang mempunyai aplikasi pada bidang informatika adalahgraf ohon. Graf pohon memegang peranan penting bagi programmer untukmenggambarkan hasil karyanya. Bagi seorang user, setiap kali berhadapan denganmonitor untuk menjalankan program aplikasi selalu akan menelusuri bagian–bagian dari graf pohon sebelum sampai pada program aplikasi yang dimaksud.Konsep dimensi partisi dan pewarnaan adalah dua konsep yang mendasarilahirnya bilangan kromatik lokasi.Konsep dimensi partisi diperkenalkan olehChartrand dkk, pada tahun 1998. Konsep ini merupakan bentuk lain dari konsepdimensi metrik yang sebelumnya sudah diperkenalkan oleh Slater (1975) danMelter dkk. (1976).
1.2 Rumusan Masalah
Definisi Graf bidang, planar, dan Dual.
1.3 Tujuan
- Diharapkan pebaca dapat mengetahui dan memahami tentang definisi graf bidang, panar dan dual
- Untuk menelesaikan tugas matematika diskrit
- Pembaca paham akan graf bidang,planar dan dual.
BAB II
PEMBAHASAN
2.1 Graf
Graf merupakan suatu diagram yang memuat informasi tertentu jika diinterpretasikan secara tepat. Dalam kehidupan sehari-hari graf digunakan untuk mengambarkan berbagai macam struktur yang ada.Graf adalah himpunan simpul yang dihubungkan dengan garis-garis (ruas).Setiap ruas diasosiasikan dengan tepat dua simpul. Secara matematis, Graf G didefinisikan sebagai pasangan himpunan (V,E) yang dalam hal ini :
V = himpunan tidak kosong dadi simpul-simpul (vertices atau node): {v1,v2,v3,…,vn}.
E = himpunan sisi (edges atau arcs) yang mehubungkan sepasang simpul: {e1,e2,e3,…,en}.
Atau dapat ditulis singkat dengan notasi G=(V,E). jadi sebuah graf dimungkinkan tidak mempunyai sisi satu buahpun, tapi simpulnya harus ada, minimal satu. Graf yang hanya mempunyai satu buah simpul tanpa sebuah sisipun dinamakan graf trivial.
Setiap garis pada graf berubungan dengan satu atau dua titik.Titik-titik tersebut dinamakan titik ujung. Garis yang hanya berhubungan dengan satu titik ujung disebut Loop. Dua garis berbeda yang menghubungkan titik yang sama disebut Garis parallel. Perlu diketahui bahwa panjang garis, kelengkungan garis,, dan letak titik tidak berpengaruh dalam suatu graf.
2.2 Graf Bidang Dan Planar
Graf Bidang adalah graf yang digambarkan pada bidang datar (di kertas, papan tulis, dll) sedemikian rupa sehingga setiap pasang sisi bertemu hanya pada simpul akhirnya (jika mereka bertemu sama sekali).
Graf Planar adalah graf yang isomorfik dengan graf bidang, yaitu dapat digambar kembali sebagai graf bidang.
Contoh Graf Planar
Gambar 5.1: Lima graf planar
Pada gambar di atas semua merupakan Graf Planar, tetapi G1 dan G2 Tidak
graf bidang, karena G1 dapat di gambarkan kembali menjadi G2 dan G3
sedangkan G4 dapat di gambarkan kembali menjadi G5.
Tidak semua graf adalah Planar.Untuk melihat ini, perlu dibicarakan tentang teorema utama dalam matematika.
2.2.1 Formula Euler
Sebuah graf bidang G membagibidang menjadi beberapa wilayah yang masing - masing disebut ”muka”(face) G. Lebih tepatnya, jika x adalah titik pada bidang yang tidak diG, yaitu bukan simpul dari G atau titik di beberapa sisiG, maka didefinisikan muka Gmengandungx yang merupakan himpunan semua titik pada bidang yang dapat dihubungkan dari x menjadi garis (lurus atau melengkung) yang tidak menyeberang sisi G atau melalui simpul dari G.
Contoh, untuk titik x di graph G1 dari Gambar 5.9, muka yang mengandung x ditampilkan sebagai wilayah bertitik. Dalam contoh ini jelas muka G1 mengandung titik y adalah muka yang sama seperti yang mengandung x. Hal ini dibatasi oleh siklus
v_2 v_4 v_3 v_6 v_5 v_4 . Muka G1 mengandung titik z tidak dibatasi oleh siklus apapun. Hal ini disebut muka eksterior G1
Gambar 5.9: Sebuah graf bidang dengan empat muka
2.3
Graf Dual
Graf dual adalah graf yang terbentuk dengan cara penggambaran di titik luar dari graf yang asli.Misalkan kita mempunyai sebuah graf planar G yang direfresentasikan sebagai graf bidang.Kita dapat membuat suatu graf G* yang secara geometri merupakan dual dari graf planar tersebut.
Misalkan G graf bidang. didefinisikan Dual dari G dengan graf G* dibangun sebagai berikut.Untuk masing-masing f muka pada G terdapat simpul yang sesuai f* dari G* dan setiap sisi e pada G ada sisi e* yang sesuai di G* seperti jika sisi e terdapat di perbatasan dari dua muka f dan g kemudian e*gabungan sisidengan simpul yang sesuai f* dan g* di G*. (Jika e adalah sisi jembatan maka diperlakukan seolah-olah terjadi dua kali pada batas muka f di mana itu terletak dan kemudian sisi e* yang sesuai adalah kejadian loop dengan f* titik di G*).
Sebuah graf mempunyai dual hanya jika graf tersebut planar. Pertanyaanya, apakah dual dari sebuah graf adalah unik?dengan kata lain, apakah dual-dual dari sebuah graf planar isomorfik? Jawabannya adalah bahwa sebuah graf planar G mempunyai dual yang unik hanya jika representasi bidangnya unik. Sebagai contoh, pada gambar 8.54, pada kedua graf adalah sama (isomorfik), tetapi mempunyai representatisi bidang yang berbeda. Akibatnya, dual dari kedua graf yang isomorfik tersebut tidak isomorfik.
BAB III
PENUTUPAN
Dari penjelasan di atas, dapat disimpulkan bahwa teori graf memang sangat berguna dalam kehidupan seharihari, dan khususnya dapat diimplementasikan dalam jaringan internet dan merupakan dasar teori yang sangat penting dalam jaringan internet, baik ditinjau dari prinsip dasar kerja jaringan internet, optimasi kerja jaringan internet, maupun dalam mengatasi masalah-masalah dalam jaringan internet. Maka dari itu, teori graf dan teori-teori lainnya, khususnya teori-teori yang termasuk di dalam bidang Matematika Diskrit sangat penting untuk mengembangkan ilmu pengetahuan, agar selanjutnya dapat membantu kehidupan masyarakat.
DAFTAR PUSTAKA
Komentar
Posting Komentar