Graph Kel 1.pdf

TUGAS TEORI GRAPH Untuk Memenuhi Tugas Mata Kuliah Teori Graph

Dosen Pembimbing : Novita Vindri Harini, M.Pd

Oleh : Nurul Fithrotuz Zaidah

(D04216027)

Tanthowi Jauhari

(D74216077)

Milla Aprilia

(D74216099)

Qomariatul Laili

(D74216107)

Rofiqoh Sa’adah

(D74216109)

Yusiana Rismatika Slawantya

(D74216115)

PROGRAM STUDI PENDIDIKAN MATEMATIKA FAKULTAS TARBIYAH DAN KEGURUAN UIN SUNAN AMPEL SURABAYA 2019

A. Sejarah Teori Graph

Leonhard Euler, seorang matematikawan Swiss diperkirakan sebagai orang yang pertama kali (1736) menulis artikel ilmiah di bidang teori graf. Artikel dengan judul "Seven Bridges of Königsberg" yang ditulisnya membahas permasalahan ada atau tidaknya struktur yang saat ini dikenal sebagai sirkuit Euler

pada

graf

keterhubungan

daratan

kota

Königsberg (sekarang Kaliningrad, Russia) dan pulau kecil di tengah sungai Pregel yang dihubungkan oleh tujuh buah jembatan.

Disiplin ilmu teori graf belum meraih perhatian besar para matematikawan penting dalam sejarah sampai kurang lebih seratus tahun kemudian, masalah pewarnaan peta diperkenalkan oleh Francis Guthrie. Pada tahun 1852, Francis Guthrie menyadari bahwa ia hanya membutuhkan empat warna yang berbeda untuk mewarnai peta wilayah Britania Raya sehingga setiap dua daerah yang bersebelahan selalu memiliki dua warna yang berbeda. Kemudian, ia mengajukan sebuah pertanyaan pada seorang matematikawan Inggris, Augustus De Morgan, mungkinkah hal ini bukan sekadar kebetulan dan setiap peta selalu dapat diwarnai dengan empat warna saja? Pertanyaan ini membangkitkan keingintahuan para matematikawan dan sejak saat itu, teori graf menjadi bahan penelitian yang sangat menarik. Pertanyaan ini tetap menjadi misteri selama setidaknya seratus tahun kemudian dan menjadi topik yang sangat panas diperbincangkan matematikawan-matematikawan besar pada zaman itu. Pada awal abad keduapuluh, para saintis menemukan banyak manfaat dari teori graf di bidang-bidang lain seperti ilmu komputer, kimia teoretik, transportasi, dan lain-lain.

B. Alasan Belajar Teori Graph Pada tahun 1836, Leonhard Euler membuktikan bahwa perjalanan di kota Konigsberg dengan syarat melalui setiap jembatan tepat satu kali, tidak dapat dilaksanakan. Dalam pembuktiannya Euler menyederhanakan situasi jembatan Konigsberg itu menjadi suatu diagram seperti pada gambar 1.

Gambar 1

Berkat pekerjaan Euler yang diilhami melalui persoalan jembatan Konigsberg itu, maka muncullah suatu cabang Matematika yang cukup penting, yang dikenal dengan nama Teori Graph (Graph Theory). Teory Graph sudah banyak berkembang dan memiliki segi terapan di banyak bidang ilmu, misalnya di bidang Fisika, Kimia, Ilmu Komunikasi, Rekayasa listrik, Genetika, dan lainlain. Teori Graph juga erat kaitannya dengan beberapa cabang Matematika, antara lain ; teory Matriks, Analisa Numerik, Teori Kemungkinan, Topologi dan Kombinatorial. Sementara dalam kenyataan, pengetahuan kita tentang Teori Graph masih sangat kurang. Salah satu persoalan dalam Teori Graph adalah menghitung banyaknya Graph yang tidak isomorphik, yang disebut Enumerasi (Enumeration). Khusus untuk graf pohon dapat dilakukan dengan mengaplikasikan Teorema Cayley . Persoalan lain adalah menghitung banyaknya pohon perentang dari graph lengkap Kp dan pohon perentang (spaninning - tree) dari sebarang graph terhubung sederhana. Pohon perentang dari graph lengkap Kp ternyata ada kaitannya dengan pohon berlabel yang tidak isomorphik. Karena itu banyaknya pohon perentang dari suatu graph lengkap Kp dapat dihitung dengan Teorema Cayley, sedang pohon perentang dari graph tehubung sederhana dapat dihitung dengan Teorema Matriks Pohon (Matrix-Tree Theorem).

C. Definisi Graph (Graf) Graf merupakan struktur diskrit yang terdiri himpunan sejumlah berhingga obyek yang disebut simpul (vertices/vertex) dan himpunan sisi (edges) yang menghubungkan simpulsimpul tersebut. Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut.

Gambar di bawah ini sebuah graf yang menyatakan peta jaringan jalan raya yang menghubungkan sejumlah kota di provinsi Jawa Tengah.

Sejarah Graf yang dulunya diambil dari sebuah masalah jembatan Königsberg (tahun 1736)

Graf yang merepresentasikan jembatan Königsberg: 1. Simpul (vertex) : menyatakan daratan 2. Sisi (edge)

: menyatakan jembatan

Notasi Graf Notasi graf dapat dituliskan dengan 𝐺 = (𝑉, 𝐸), dimana: 

𝑉 merupakan himpunan tak kosong dari simpul-simpul (vertices), misalkan 𝑉 = {𝑣1 , 𝑣2 , … 𝑣𝑛 }



𝐸 merupakan himpunan tak kosong dari simpul-simpul (edges), misalkan 𝐸 = {𝑒1 , 𝑒2 , … 𝑒𝑛 }

Contoh : Graf dari masalah jembatan Konigsberg dapat disajikan sebagai berikut.

Misalkan graf tersebut adalah G(V, E) dengan :

𝑉 = { 𝐴, 𝐵, 𝐶, 𝐷 } 𝐸 = { (𝐴, 𝐶), (𝐴, 𝐶), (𝐴, 𝐵), (𝐴, 𝐵), (𝐵, 𝐷), (𝐴, 𝐷), (𝐶, 𝐷)} = {𝑒1 , 𝑒2 , 𝑒3 , 𝑒4 , 𝑒5 , 𝑒6 , 𝑒7 } Pada graf tersebut sisi 𝑒1 = (𝐴, 𝐶) dan sisi 𝑒2 = (𝐴, 𝐶) 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 𝑒3 dan sisi 𝑒4 . Sementara itu, pada graf diatas tidak terdapat gelang (loop), yaitu sisi yang berawal dan berakhir pada simpul yang sama. 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). Contoh : Graf kosong dengan 3 simpul (graf N3)

D. Jenis- jenis Graph Jenis-jenis graf dapat diklasifikasikan berdasarkan beberapa faktor-faktor sebagai berikut1: a. Berdasarkan ada tidaknya loop atau rusuk ganda pada suatu graf, maka graf digolongkan menjadi dua jenis, yaitu: 1. Graf sederhana (simple graph) Graf sederhana yaitu graf yang tidak mengandung loop maupun rusuk ganda. Gambar G1 di bawah ini adalah contoh graf sederhana.

1

Mardiyono: 2009

2. Graf tak-sederhana (unsimple graph) Graf tak-sederhana yaitu graf yang mengandung loop atau rusuk ganda. Gambar Graf G2 di bawah ini adalah contoh graf tidak sederhana yang mengandung rusuk ganda dan Graf G3 adalah contoh graf tidak sederhana yang mengandung loop.

b. Berdasarkan jumlah titik pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis: 1.

Graf berhingga (limited graph) Graf berhingga adalah graf yang jumlah titiknya n berhingga.

2. Graf tak berhingga (unlimited graph) Graf tak behingga adalah graf yang jumlah titiknya n tidak berhingga banyaknya.

c. Berdasarkan orientasi arah pada rusuk, maka secara umum graf dibedakan atas dua jenis: 1. Graf tak berarah (undirect graph) Graf tak berarah adalah graf yang rusuknya tidak mempunyai orientasi arah. Urutan pasangan titik yang terhubung oleh rusuk tidak diperhatikan. Sehingga (𝑣1, 𝑣2) = (𝑣2, 𝑣1) adalah rusuk yang sama. Graf tak berarah sering dipakai pada jaringan saluran telepon karena rusuk pada graf tak berarah menyatakan bahwa saluran telepon dapat beroperasi pada dua arah. Graf G4 di bawah ini merupakan contoh graf tak berarah.

2. Graf berarah (direct graph atau digraph) Graf berarah adalah graf yang setiap rusuknya diberikan orientasi arah. Pada graf berarah (𝑣1, 𝑣2) dan (𝑣2, 𝑣1) menyatakan dua buah rusuk yang berbeda, dalam arti kata bahwa (𝑣1, 𝑣2) ≠ (𝑣2, 𝑣1). Jadi untuk rusuk (𝑣1, 𝑣2) titik 𝑣1 dinamakan titik asal dan titik 𝑣2 dinamakan titik terminal atau titik tujuan. Graf berarah sering dipakai untuk menggambarkan aliran proses, peta lintas kota dan lain sebagainya. Sehingga pada graf berarah gelang atau looping diperbolehkan tetapi rusuk ganda tidak diperbolehkan. Berikut adalah gambar Graf G5 yang merupakan contoh graf berarah:

E. Graph Bagian Sebuah graph g disebut graph bagian atau subgraph dari G jika semua titik dan sisi dari g termuat dalam G, dan tiap sisi dari g memiliki titik-titik ujung yang sama baik dalam g maupun dalam G. Sebagai contoh, graph dalam Gambar 2.3 bagian (b) merupakan sebuah graph bagian dari graph gambar (a). Konsep subgraph dapat dianalogikan dengan konsep

himpunan bagian dalam teori himpunan, maka sebuah subgraph dapat dipandang sebagai bagian dari graph yang lain2.

(a)

(b) Gambar 2.3. Subgraph atau Graph Bagian

Misalkan H seguah graph dengan himpunan titik V(H) dan himpunan sisi E(H). Misalkan pula G sebuah graph dengan himpunan titik V(G) dan himpunan sisi E(G). H dikatakan subgraph dari G jika V(H) ⊂ V(G) dan E (H) ⊂ E(G) atau dapat ditulis H ⊆ G.

Contoh : Perhatikan gambar graph G, grap H1, graph H2, dan graph H3. Graph H2 merupakan graph bagian rentang dari graph G karena H2 ⊂ G dan himpunan titik V(H2) = V(G), sedangkan graph H1 merupakan graph bagian dari graph G (bukan rentang), dan graph H3 merupakan graph bagian dari G yang dibangun oleh V = {a,c,d,f}

G

2

H1

H2

http: //file.upi.edu/Direktori/FPMIPA/JUR._PEND._MATEMATIKA/196303311988031-

NANANG_PRIATNA/Representasi_Graph.pdf (diakses pada tanggal 26 Februari 2019)

H3

F. Aplikasi Graph 1. Lintasan Terpendek Lintasan Terpendek (Shortest Path) merupakan Graf berbobot (weighted graph) dimana untu mencari lintasan yang memiliki total bobot minimum. Contoh aplikasi: •

Menentukan jarak terpendek/waktu tempuh tersingkat/ongkos termurah antara dua buah kota

•

Menentukan waktu tersingkat pengiriman pesan (message) antara dua buah terminal pada jaringan komputer.

Google Map Untuk mencari rute dari Masjid Muayyad Wonocolo menuju Gresik Icon Mall, Google Map menampilkan rute-rute berikut ini.

1. Rute Jalan Kaki

Rute Terpanjang

Rute Sedang

Rute Terpendek

2. Rute Mobil

Rute Terpanjang

Rute Terpendek

3. Rute Motor

Rute Terpanjang

Rute Sedang

Rute Terpendek

Rute di atas dapat berubah sewaktu-waktu. Selain faktor panjang lintasan, Google Map juga memperhatikan berbagai macam faktor yang mempengaruhi pemilihan rute terpendek, seperti macet, hujan, penutupan jalan, penyempitan jalan akibat kegiatan masyarakat, kecelakaan, dan banyak lainnya.

2. Graf Kompatibilitas

Graf – graf kompatibilitas digunakan secara luas dalam memecahkan masalah yang melibatkan pengaturan data dalam urutan tertentu. Dalam graf ini, simpul-simpulnya (titik-titiknya) menunjukkan objek-objek yang akan di atur, dan sisi-sisinya menunjukkan pasangan objek yang kompatibel (sesuai). Aplikasi graf kompatibel yang akan dibahas adalah pengaturan lampu lalu lintas. Perhatikan persimpangan jalan pada Gambar berikut. Beberapa arus lalu lintas pada persimpangan jalan ini adalah kompatibel, yaitu arus ini dapat berjalan pada waktu bersamaan tanpa saling membahayakan.3

Persimpangan Lampu Merah

Dengan Metode Webster

Menentukan Titik/Simpul

Menentukan Sisi

Semua ini dimaksudkan untuk menentukan waktu dari masing-masing lampu, yakni merah, kuning, dan hijau. Penentuan waktu ini dipengaruhi oleh banyak faktor, seperti arus lalu lintas, kecepatan rata2 kendaraan tiap jalur, lebar jalan, lebar rata2 kendaran, jenis kendaraan tiap jalur, dan lain-lain.

DAFTAR PUSTAKA

Kusaeri, Suparto. Matematika Diskrit. Surabaya:UIN Sunan Ampel Press. 2014 http://file.upi.edu/Direktori/FPMIPA/JUR._PEND._MATEMATIKA/19630331198803 1-NANANG_PRIATNA/Representasi_Graph.pdf (diakses pada tanggal 26 Februari 2019. Pukul 15.54) https://id.wikipedia.org/wiki/Teori_graf (diakses pada tanggal 27 Februari 2019. Pukul 23.34) Gary Chartrand, Ortrud R. Oellermann, (1993), Applied and algorithmic Graph Theory, McGRAW-HILL. Reinhard Diestel (2000), Graph Theory: Graduste Texts In Mathematics, Springer. Wataru Mayeda (1972), Graph Theory, WILEY-INTERSCIENCE.