Makalah Teori Graf [PDF]

Citation preview

MAKALAH KONSEP DASAR TEORI GRAF Untuk Memenuhi Salah Satu Tugas Mata Kuliah Matematika Diskrit



Yang Diampu Oleh : Ayu Wulandari, M.Pd



Disusun Oleh:



1. Ernawati Yuru Beli



(2015800072)



2. Heru Saputra



(20158300106)



3. Debi Paradita



(20158300210)



4. Yunita



(20158300275)



PROGRAM STUDI PENDIDIKAN MATEMATIKA STKIP KUSUMA NEGARA JAKARTA 2018



KATA PENGANTAR Puji dan syukur senantiasa penulis panjatkan kehadirat Allah SWT, shalawat serta salam semoga senantiasa dilimpahkan kepada Nabi Muhammad SAW, juga untuk para keluarga, sahabat dan pengikutnya sampai akhir zaman. Karena atas rahmat-Nya, penulis dapat menyelesaikan penyusunan makalah ini yang berjudul “Konsep Dasar Teori Graf”. Makalah ini disusun untuk memenuhi tugas mata kuliah “Matematika Diskrit”. Penulis mengucapkan terimakasih kepada Ibu Ayu Wulandari, M.Pd. selaku dosen pengampu, teman-teman dan semua pihak yang membantu dalam penyelesaian makalah ini. Penyusunan materi dalam makalah ini disesuaikan dengan referensi yang didapat dari buku maupun internet. Penulis berharap makalah ini dapat menambah pengetahuan pembaca dan memberikan gambaran mengenai materi terkait. Sehingga pembaca dapat menggunakan makalah ini sebagai literatur pendukung dalam pengembangan bidang ilmu selanjutnya yang terkait ataupun langsung mengaplikasikannya kedalam kehidupan sehari-hari. Penulis menyadari bahwa makalah ini masih jauh dari kesempurnaan, oleh karena itu penulis mengharapkan saran dan kritik yang membangun untuk perbaikan makalah ini. Besar harapan penulis agar penulisan makalah ini dapat berguna bagi siapapun yang menjadikan makalah ini sebagai bahan literatur mengenai materi terkait.



Jakarta, Oktober 2018



Penulis



i



DAFTAR ISI



KATA PENGANTAR ...................................................................................



i



DAFTAR ISI ................................................................................................



ii



BAB 1 PENDAHULUAN A. Latar Belakang .................................................................................



1



B. Rumusan Masalah ...........................................................................



2



C. Tujuan Penulisan .............................................................................



2



BAB II PEMBAHASAN A. Definisi Graf ....................................................................................



3



B. Jenis-jenis Graf .................................................................................



4



C. Keterhubungan graf ...........................................................................



7



BAB III PENUTUP A. Kesimpulan ......................................................................................



DAFTAR PUSTAKA



ii



9



BAB I PENDAHULUAN



A. Latar Belakang Teori graf lahir pada tahun 1736 melalui tulisan Euler yang berisi tentang upaya pemecahan masalah jembatan Konigsberg yang sangat terkenal di Eropa. Kurang lebih seratus tahun setelah lahirnya tulisan Euler tersebut tidak ada perkembangan yang berarti dengan teori graf. Tahun 1847, G.R. Kirchoff (1824-1887) berhasil mengembangkan teori pohon (Theory of trees) yang digunakan dalam persoalan jaringan listrik. Sepuluh tahun kemudian, A.Cayley (1821-1895) juga menggunakan konsep pohon untuk menjelaskan permasalahan kimia yaitu hidrokarbon. Pada masa Kirchoff dan Cayley juga telah lahir dua hal penting dalam graf. Salah satunya berkenaan dengan konjektur empat warna, yang menyatakan bahwa untuk mewarnai sebuah atlas cukup dengan menggunakan empat warna sedemikian sehingga tiap negara yang berbatasan akan memiliki warna yang berbeda. Para ahli teori graf berkeyakinan bahwa orang yang pertama kali mengemukakan masalah empat-warna adalah A.F.Mobius (1790-1868) dalam salah satu kuliahnya di tahun 1840. Sepuluh tahun kemudian, A.Demorgan (1806-1871) kembali membahas masalah ini bersama ahli-ahli matematika lainnya di kota London. Dengan demikian tulisan Demorgan dianggap sebagai referensi pertama berkenaan dengan masalah empat-warna. Masalah empat-warna ini menjadi sangat terkenal setelah Cayle mempublikasikannya tahun 1879 dalam Proceeding of the Royal Geographic Society volume pertama. Hal ini yang penting untuk membicarakan sehubungan dengan perkembangan teori graf adalah apa yang dikemukakan oleh Sir W.R. Hamilton (1805-1865). Pada tahun 1895 dia berhasil menemukan suatu permainan yang kemudian dijualnya ke sebuah pabrik mainan di Dublin. Permainan tersebut dari kayu berbentuk dodecahedron beraturan yakni berupa sebuah polyhedron dengan 12 muka dan 20 pojok. Tiap muka berbentuk sebuah pentagon beraturan dan tiap pojoknya dibentuk oleh tiga sisi berbeda. Tiap pojok dari dodecahedron tersebut dipasangkan dengan sebuah kota terkenal seperti London, New York, Paris, dll. Masalah dalam



1



permaianan ini adalah kita diminta untuk mencari suatu rute melalui sisi-sisi dari dodecahedron sehingga tiap kota dari 20 kota yang ada dapat dilalui tepat satu kali. Walaupun saat ini masalah tersebut dapat dikategorikan mudah, akan tetapi pada saat itu tidak ada seorang pun yang bisa menemukan syarat perlu dan cukup dari eksistensi rute yang dicari. Kurang lebih setengah abad setelah Hamilton, aktivitas dalam bidang teori graf dapat dikatakan relatif kecil. Pada tahun 1920-an kegiatan tersebut muncul kembali yang dipelopori oleh D.Konig. Konig berupaya mengumpulkan hasil-hasil pemikiran para ahli matematika tentang teori graf termasuk hasil pemikirannya sendiri, kemudian dikemasnya dalam bentuk buku yang di terbitkan pada tahun 1936. Buku tersebut dianggap sebagai buku pertama tentang teori graf.



B. Rumusan Masalah Setelah memperhatikan pemaparan diatas, dapat dirumuskan beberapa masalah yang akan dibahas dalam makalah ini, diantaranya : 1. Apa definisi tentang teori graf? 2. Apa saja jenis-jenis teori graf? 3. Apa saja yang terkait dengan graf?



C. Tujuan Penulisan Adapun tujuan penulisan makalah ini ditujukan untuk : 1. Untuk mengetahui definisi tentang teori graf 2. Untuk mengetahui tentang jenis-jenis graf 3. Untuk mengetahui tentang keterkaitan graf



2



BAB II PEMBAHASAN



A. Definisi Graf Secara sistematis, graf didefinisikan sebagi berikut: Suatu graf dapat dipandang sebagai kumpulan titik yang disebut simpul dan segmen garis yang menghubungkan dua simpul yang disebut dengan rusuk. Graf (G) didefinisikan sebagai pasangan himpunan (V, E), di tulis dengan notasi G = (V, E), yang dalam hal ini V adalah himpunan tidak kosong dari simpul-simpul (vertices atau node) dan E adalah himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul. Dari definisi diatas dapat di simpulkan bahwa, graf adalah kumpulan dari simpul dan busur yang secara sistematis dinyatakan sebagai: G = (V, E) Dimana: G = Graf V = Simpul atau vertices atau node atau titik E = Busur atau edges atau arcs atau sisi Dari definisi di atas menyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Jadi, sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpulnya harus ada, minimal satu. Graf yang hanya mempunyai satu buah simpul tanpa sebuah sisi pun dinamakan graf trivial. Simpul pada graf dapat dinomori dengan huruf, seperti a, b, c, ..., v, w, ..., dengan bilangan asli 1, 2, 3, ..., atau gabungan keduanya. Sedangkan sisi yang menghubungkan simpul u dengan simpul v dinyatan dengan pasangan (u, v) atau dinyatakan dengan lambang e1, e2, .... Dengan kata lain, jika e adalah sisi yang menghubungkan simpul u dengan v, maka e dapat ditulis sebagai e = (v, v) Secara geometri graf digambarkan sebagai sekumpulan noktah (simpul) di dalam bidang dwimatra



3



Contoh 8.1 Gambar 8.3 memperlihatkan tiga buah graf, G1, G2, dan G3. 1) G1 adalah graf dengan himpunan simpul V dan himpunan sisi E adalah V = { 1, 2, 3, 4 } E = { (1, 2), (1, 3), (2, 3), (2, 4), (3, 4) } 2) G2 adalah graf dengan himpunan simpul V dan himpunan sisi E adalah V = { 1, 2, 3, 4 } E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4) } → himpunan ganda = { e1, e2, e3, e4, e5, e6, e7 } 3) G3 adalaha graf dengan himpunan simpul V dan himpunan sisi E adalah V = { 1, 2, 3, 4 } E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3) } → himpunan ganda = { e1, e2, e3, e4, e5, e6, e7, e8 }



Pada G2, sisi e3 = (1, 3) dan sisi e4 = (1, 3) dinamakan sisi-ganda (multiple edges atau paralel edges) karena kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul 1 dan simpul 3. Pada G3, sisi e8 = (3, 3) dinamakan gelang atau kalang (loop) karena ia berawal dan berakhir pada simpul yang sama.



B. Jenis-jenis Graf Graf dapat dikelompokkan menjadi beberapa kategori (jenis) bergantung pada sudut pandang pengelompokkannya. Pengelompokkan graf dapat dipandang berdasarkan ada tidaknya sisi ganda atau sisi kalang, berdasarkan jumlah simpul, atau berdasarkan orientasi arah pada sisi. Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis, yaitu: 4



1) Graf sederhana (simple graph) Graf tidak mengandung gelang maupun sisi ganda dinamakan graf sederhana. G1 pada gambar 8.3 (a) adalah contoh graf sederhana yang merepresentasikan jaringan komputer. Simpul menyatakan komputer, sedangkan sisi menyatakan saluran telepon untuk berkomunkasi. Saluran telepon dapat beroperasi pada dua arah. Pada graf sederhana, sisi adalah pasangan tak terurut (unordered pairs). Jadi, menulis sisi (u, v) sama saja dengan (v, u). Kita dapat juga mendefinisikan graf sederhana G = (V, E) terdiri dari himpunan tidak kosong simpul-simpul dan E adalah himpunan pasangan tak terurut yang berbeda yang disebut sisi. 2) Graf tak sederhana (unsimple graph) Graf yang mengandung sisi ganda atau gelang dinamakan graf tak sederhana (unsimple graph). Ada dua macam graf tak sederhana, yaitu graf ganda (multigraph) dan graf semu (pseudograph). Graf ganda adalah graf yang mengandung sisi ganda. Sisi ganda yang menghubungkan sepasang simpul bisa lebih dari dua buah. G2 pada gambar 8.3 (b) adalah graf ganda. Sisi ganda dapat diasosiasikan sebagai pasangan tak terurut yang sama. Kita dapat juga mendefinisikan graf ganda G = (V, E) terdiri dari himpunan tidak kosong simpul-simpul dan E adalah himpunan ganda (multiset) yang mengandung sisi ganda. Pada jaringan telekomunikasi, sisi ganda pada G2 dapat diandaikan sebagai saluran telepon tambahan apabila beban komunikasi data antar komputer sangat padat. Perhatikanlah bahwa setiap graf sederhana juga adalah graf ganda, tetapi tidak setiap graf ganda merupakan graf sederhana. Graf semu adalah graf yang mengandung gelang (loop). G3 adalah graf semu (termasuk bila memiliki sisi ganda sekalipun). Sisi gelang pada G3 dapat dianggap sebagai saluran telepon tambahan yang menhubungkan komputer dengan dirinya sendiri (mungkin untuk tujuan diagnostik). Graf semu lebih umum daripada graf ganda, karena sisi pada graf semu dapat terhubung ke dirinya sendiri. Jumlah simpul pada graf kita sebut sebagai kardinalitas graf, dan dinyatakan dengan n = | V |, dan jumlah sisi kita nyatakan dengan m = | E |. Pada contoh di atas, G1 mempunyai n = 4 dan m = 4, sedangkan G2 mempunyai n = 3 dan m = 4.



5



Sisi pada graf dapat mempunyai orientasi arah. Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis, yaitu: 1) Graf tak berarah (undirected graph) Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak berarah. Pada graf tak berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Jadi, (u, v) = (v, u) adalah sisi yang sama. Tiga buah graf pada gambar 8.3 adalah graf tak berarah. Pada jaringan telepon, sisi pada graf berarah menyatakan bahwa saluran telepon dapat beroperasi pada dua arah. 2) Graf berarah (directed graph atau digraph) Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Kita lebih suka menyebut sisi berarah dengan sebutan busur (arc). Pada graf berarah, (u, v) dan (v, u) menyatakan dua buah busur yang berbeda, dengan kata lain (u, v) ≠ (v, u). Untuk busur (u, v), simpul u dinamakan simpul asal (initial vertex) dan simpul v dinamakan simpul terminal (terminal vertex). G4 pada gambar 8.4 (a) adalah contog graf berarah. Pada G4 dapat dibayangkan sebagai saluran telepon tidak dapat beroperasi pada dua arah. Saluran hanya beroperasi pada arah yang ditunjukkan oleh anak panah. Jadi, sebagai contoh, saluran (1, 2) tidak sama dengan saluran telepon (2, 1). Graf berarah sering dipakai untuk menggambarkan aliran proses, peta lalu lintas suatu kota (jalan searah atau dua arah) dan sebagainya. Pada graf berarah, gelang diperbolehkan, tetapi sisi ganda tidak.



Definisi graf dapat diperluas sehingga mencakup graf ganda berarah (directed multigraph). Pada graf ganda berarah, gelang dan sisi ganda



6



diperbolehkan ada. G5 pada gambar 8.4 (b) adalah contoh graf-ganda berarah. Tabel 8.1 meringkas perluasan definisi graf Jenis



Sisi



Sisi ganda



Sisi gelang



dibolehkan?



dibolehkan?



Graf sederhana



Tak-berarah



Tidak



Tidak



Graf ganda



Tak-berarah



Ya



Tidak



Graf semu



Tak-berarah



Ya



Ya



Graf berarah



Berarah



Tidak



Ya



Graf-ganda berarah



Berarah



Ya



Ya



Didalam buku ini, kita menyebut graf untuk jenis graf apa saja, baik sisinya tak berarah maupun berarah, baik mengandung gelang maupun sisi ganda, baik graf sederhana maupun tak sederhana



C. Keterhubungan Menurut Chartrand & Zang, sebuah graf G dikatakan terhubung jika setiap dua simpul graf G terhubung. Dengan kata lain, graf G dikatakan terhubung jika ada suatu lintasan antara sembarang dua simpul. Graf dapat digunakan sebagai model dari suatu sistem, salah satunya yaitu model sistem rute perjalanan. Gambar 2.2 digunakan sebagai ilustrasi untuk membedakan graf berdasarkan rusuk yang dilalui dan simpul yang dituju dan disinggahi.



7



Berikut akan dijelaskan keterhubungan graf yaitu simpul (vertex), jalan (walk), jejak (trail), lintasan (path), siklus (cycle) atau sirkuit (circuit). 1) Simpul (Vertex) Setiap rusuk yang menghubungkan dua simpul yang disebut simpul-simpul ujung dari rusuk tersebut. Pada gambar 2.2, contoh simpul (vertex) adalah V = { 𝑣1, 𝑣4, 𝑣5, 𝑣6, 𝑣2, 𝑣3 }. 2) Jalan (Walk) Misalkan graf G dengan rusuk 𝑉 = {𝑣1 ,𝑣2, 𝑣3, … , 𝑣𝑘 } dan simpul 𝐸 = { 𝑒1, 𝑒2, 𝑒3, … , 𝑒𝑘 }, yang membentuk barisan berhingga 𝑊 = { 𝑣1, 𝑒1, 𝑣2, 𝑒2, 𝑣3, 𝑒3, … , 𝑣𝑘, 𝑒𝑘}. Maka, definisi jalan (walk) adalah suatu barisan yang suku-sukunya berupa simpul dan rusuk yang diurutkan secara bergantian sedemikian hingga rusuk ujung 𝑒𝑖 adalah simpul 𝑣𝑖−1 dan . Pada gambar 2.2, contoh suatu jalan (walk) adalah barisan berhingga 𝑊 = {𝑣1, 𝑒2, 𝑣5, 𝑒3, 𝑣4, 𝑒5, 𝑣6, 𝑒6, 𝑣5}. 3) Jejak (Trail) Jejak (Trail) adalah walk tanpa rusuk berulang. Pada gambar 2.2, contoh jejak adalah 𝑊 = {𝑣1, 𝑒2, 𝑣5, 𝑒3, 𝑣4, 𝑒4, 𝑣2, 𝑒9, 𝑣6, 𝑒6, 𝑣5, 𝑒7, 𝑣3}. 4) Lintasan (Path) Lintasan (Path) adalah jejak tanpa simpul berulang. Contoh pada gambar 2.2 ditunjukkan oleh 𝑊 = {𝑣1, 𝑒1, 𝑣4, 𝑒3, 𝑣5, 𝑒6, 𝑣6, 𝑒9, 𝑣2, 𝑒8, 𝑣3}. 5) Siklus (cycle) atau sirkuit (circuit) Siklus (cycle) atau sirkuit (circuit) adalah jalan tertutup (closed walk) dengan rusuk tidak berulang atau dengan kata lain sirkuit adalah jejak (trail) yang tertutup. Contoh sirkuit pada gambar 2.2 adalah 𝑊 = {𝑣1, 𝑒2, 𝑣5, 𝑒6, 𝑣6, 𝑒9, 𝑣2, 𝑒8, 𝑣3, 𝑒7, 𝑣5, 𝑒3, 𝑣4, 𝑒1, 𝑣1}



8



BAB III PENUTUP



A. Kesimpulan Suatu graf dapat dipandang sebagai kumpulan titik yang disebut simpul dan segmen garis yang menghubungkan dua simpul yang disebut dengan rusuk. Graf G yang dilambangkan dengan 𝐺 = (𝑉,𝐸) terdiri atas dua himpunan 𝑉 dan 𝐸 yang saling asing. 𝑉 bukan himpunan kosong dengan unsur-unsurnya disebut simpul, sedangkan unsur himpunan 𝐸 disebut rusuk. Setiap rusuk menghubungkan dua simpul yang disebut simpul-simpul ujung dari rusuk tersebut. Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis, yaitu: graf sederhana (simple graph) dan graf tak sederhana (unsimple graph). Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis, yaitu: graf tak berarah (undirected graph) dan graf berarah (directed graph atau digraph). Sebuah graf G dikatakan terhubung jika setiap dua simpul graf G terhubung. Keterhubungan graf yaitu simpul (vertex), jalan (walk), jejak (trail), lintasan (path), siklus (cycle) atau sirkuit (circuit).



9



DAFTAR PUSTAKA



Rinaldi Munir. 2010. Matematika Diskit. Bandung: Informatika Bandung



10