DIGRAF EKSENTRIK DARI GRAF KOMPLIT BIPARTIT DAN DIGRAF KOMPLIT MULTIPARTIT

JUDUL

DIGRAF EKSENTRIK DARI GRAF KOMPLIT BIPARTIT DAN DIGRAF KOMPLIT MULTIPARTIT

skripsi disajikan sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains Program Studi Matematika oleh Abdiyati Ilmiyana 4150407018

JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS NEGERI SEMARANG 2011

PERNYATAAN

Saya menyatakan bahwa skripsi ini bebas plagiat, dan apabila di kemudian hari terbukti terdapat plagiat dalam skripsi ini, maka saya bersedia menerima sanksi sesuai ketentuan peraturan perundang-undangan.

Semarang, 11 Agustus 2011

Abdiyati Ilmiyana NIM. 4150407018

ii

PENGESAHAN Skripsi yang berjudul Digraf Eksentrik dari Graf Komplit Bipartit dan Digraf Komplit Multipartit disusun oleh Abdiyati Ilmiyana 4150407018 telah dipertahankan di hadapan sidang Panitia Ujian Skripsi FMIPA Unnes pada tanggal 19 Agustus 2011

Panitia: Ketua

Sekretaris

Dr. Kasmadi Imam S., M.S. 195111151979031001

Drs. Edy Soedjoko, M.Pd 195604191987031001

Ketua Penguji

Isnaini Rosyida, S.Si., M.Si 197302191998022001

Anggota Penguji/ Pembimbing Utama

Anggota Penguji/ Pembimbing Pendamping

Dr. Mulyono, M.Si 197009021997021001

Drs. Amin Suyitno, M.Pd 195206041976121001

iii

MOTTO HIDUP v (‫ﻣﻦ اراد اﻟﺪَﻧﯿﺎ ﻓﻌﻠﯿﮫ ﺑﺎﻟﻌﻠﻢ وﻣﻦ اراداﻻﺧﺮة ﻓﻌﻠﯿﮫ ﺑﺎﻟﻌﻠﻢ وﻣﻦ ارادھﻤﺎ ﻓﻌﻠﯿﮫ ﺑﺎﻟﻌﻠﻢ )ﻣﺘﻔﻖ ﻋﻠﯿﮫ‬ Barang siapa berharap akan kesuksesan dunia maka wajib baginya dengan ilmu, barang siapa berharap akan kesuksesan akhirat maka wajib baginya dengan ilmu, dan barang siapa berharap akan kesuksesan keduaya maka wajib baginya dengan ilmu pula (HR. Bukhori Muslim). v ‫ﻣﻦ ﺟﺪَّ وﺟﺪ‬ Siapa yang bersungguh-sungguh pasti akan berhasil (H.R Bukhori Muslim) v ‫إنّ ﻣﻊ اﻟﻌﺴﺮ ﯾﺴﺮا‬ Sesungguhnya bersama kesulitan ada kemudahan (QS. Al Insyiroh : 6). v ‫واﻟﺬﯾﻦ اﻣﻨﻮا وﻋﻤﻠﻮا اﻟﺼﺎﻟﺤﺎت ﻟﻨﻜﻔﺮنّ ﻋﻨﮭﻢ ﺳﯿّﺌﺎﺗﮭﻢ وﻟﻨﺠﺰﯾﻨّﮭﻢ اﺣﺴﻦ اﻟﺬي ﻛﺎﻧﻮا ﯾﻌﻤﻠﻮن‬ Dan orang-orang yang beriman dan beramal sholih benar-benar akan dihapuskan dosa-dosa mereka dan benar-benar akan kami beri balasan yang lebih baik dari apa yang mereka lakukan (QS. Al Ankabut : 7).

iv

PRAKATA

Segala puji bagi Allah SWT yang telah memberikan limpahan rahmat dan hidayah-Nya, sehingga penulis memperoleh kekuatan untuk menyelesaikan skripsi ini. Dalam kesempatan ini penulis menghaturkan terima kasih yang tak terhingga kepada: 1. Prof. Dr. H. Sudijono Sastroatmodjo, M.Si., Rektor Universitas Negeri Semarang yang telah memberikan fasilitas-fasilitas kepada penulis. 2. Dr. Kasmadi Imam S., M.S, Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Semarang. 3. Drs. Edy Soedjoko, M.Pd, Ketua Jurusan Matematika Universitas Negeri Semarang. 4. Dr. Mulyono, S.Si., M.Si, Dosen Pembimbing I dan Drs. Amin Suyitno, M.Pd, Dosen Pembimbing II yang senantiasa mengarahkan dan membimbing penulis dalam menyusun skripsi ini dengan penuh kesabaran dan keikhlasan. 5. Ibu Isnaini Rosyida,S.Si., M.Si, Dosen penguji yang membimbing penulis dalam menyempurnakan skripsi ini dengan penuh ketelitian. 6. Bapak dan Ibu dosen Jurusan Matematika yang telah memberikan bekal ilmu dan pengetahuan selama kuliah. 7. Ibu Miskiyah sekeluarga yang senantiasa sabar dan ikhlas mencurahkan kasih sayang, mendoakan, menasihati, membimbing dan menyemangati penulis serta ayahku Bapak Shodiqun tercinta yang selalu menyayangi dan mendoakanku di sana. 8. Kakak2 dan adik2ku, Mbak Hj. Hikmah, I.Lc yang menjadi inspiratorku, terimakasih untuk kasih sayang, doa serta dukungan yang diberikan. Mas Abid, mbak Etvi, mas Edzik, adik2ku Kamilatun Nisa dan Akmala Ashlihatina yang menjadi semangatku.

v

9. Abah Kyai Al Mamnuhin Kholid, Ibu Nyai Istighfaroh, S.Pd, Ibu Nyai Al Mau’natul Hafidloh, S.Pdi A.H, Ustadz-Ustadzah Ponpes. Al Asror Patemon Gunung Pati, Ustadz-Ustadzah di Madrasah Salafiyah Simbang Kulon, RA, TPQ, serta Madrasah Diniyah Al Burhan. Terimakasih atas mutiara ilmu, nasihat, kasih sayang, dan doa yang diberikan. 10. Pencinta kalam Tuhan, semoga Allah berkenan memasukkan kita ke dalam surga indahNya. Amin 11. Teman2 santriwan santriwati Ponpes Al Asror, Specially for 10 bersaudara angkatan 2007{mbak tanti, mbak im, yu end, Yu Towi, mbak Qibti, mbak Isty, mbak Pipit, mbak Kiki, Kang Yasin dan Kang Febri} maafkan salah ilmi ya? He… Klo ngumpul kompak bgt, nyenengke. Makasih buat doa dan semangatnya. Buat 10 Sister’s di Pekalongan yang selalu kurindu, buat temanteman matematika 2007 khusushon buat riva, marya, ayu cinta, azka, mb wini makasih atas dukungan, doa, dan semangatnya selama kuliah. 12. Segenap pihak yang membantu terselesaikannya skripsi ini dan studi penulis. Semoga Allah SWT berkenan membalas bantuan yang diberikan dengan balasan yang lebih baik dan berlipat ganda. Penulis berharap skripsi ini dapat bermanfaat bagi para pembaca.

Semarang, 10 Agustus 2011

Penulis

vi

ABSTRAK Ilmiyana, Abdiyati. 2011. Digraf Eksentrik dari Graf Komplit Bipartit dan Digraf Komplit Multipartit. Skripsi. Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Negeri Semarang. Pembimbing I: Dr. Mulyono, S.Si, M.Si dan Pembimbing II: Drs. Amin Suyitno, M.Pd. Kata kunci: Eksentrisitas, Titik eksentrik, Digraf Eksentrik Dewasa ini teori graf telah memantapkan diri sebagai alat matematika yang sangat penting dan berguna dalam berbagai aplikasi kehidupan. 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. Eksentrisitas e(u) dari u dalam G adalah jarak maksimal dari u ke setiap v di G, atau dapat ditulis , | . Titik disebut titik eksentrik jika jarak dari ke sama dengan . Digraf Eksentrik dari graf G yang dinotasikan dengan ED(G) didefinisikan sebagai digraf yang mempunyai himpunan titik yang sama dengan himpunan titik di G, dengan arc dari titik v ke u pada ED(G) jika dan hanya jika u adalah titik eksentrik dari v. Sedangkan Eksentrisitas e(u) dari u dalam Digraf D adalah jarak maksimal dari u ke setiap v di D, atau dapat ditulis , | . Titik disebut titik eksentrik jika jarak dari ke sama dengan . Digraf Eksentrik dari digraf D yang dinotasikan dengan ED(D) didefinisikan sebagai digraf yang mempunyai himpunan titik yang sama dengan himpunan titik di D, dengan arc dari titik v ke u pada ED(D) jika dan hanya jika u adalah titik eksentrik dari v. Permasalahan yang dikaji dalam skripsi adalah (1) bagaimana langkah-langkah mengkonstruksi digraf eksentrik dari graf dan digraf (2) bagaimana bentuk digraf eksentrik dari graf komplit bipartit, dan (3) bagaimana bentuk digraf eksentrik dari digraf komplit multipartit. Penelitian ini merupakan penelitian studi pustaka yang dilakukan dalam tiga tahap, yaitu (1) mempelajari dan mengkaji tentang eksentrisitas titik, digraf eksentrik dari graf dan digraf (2) menentukan langkah-langkah untuk mengkonstruksi digraf eksentrik dari graf komplit bipartit dan digraf eksentrik dari digraf komplit multipartit dengan menggunakan referensi yang ada serta bagaimana membuktikan teorema yang mendukung keberadaannya, dan (3) menggunakan kajian tentang digraf eksentrik untuk menemukan bagaimana bentuk digraf eksentrik dari graf komplit bipartit dan digraf eksentrik dari digraf komplit multipartit. Untuk menentukan langkah-langkah mengkonstruksi digraf eksentrik dari graf dan digraf digunakan definisi eksentrisitas, titik eksentrik dan digraf eksentrik. Kemudian dengan menggunakan langkah-langkah tersebut mulai mencari bentuk digraf eksentrik dari dari graf komplit bipartit dan digraf komplit multipartit. Berdasarkan hasil pembahasan diperoleh bahwa (1) langkah-langkah mengkonstruksi digraf eksentrik dari graf dan digraf adalah menentukan jarak vii

setiap titik di graf G ke titik yang lain di graf G atau menentukan jarak setiap titik di digraf D ke titik yang lain di digraf D, kemudian mencari eksentrisitas dan titik eksentriknya dan terakhir menggambar digraf eksentriknya (2) bentuk digraf eksentrik dari graf komplit bipartit dinotasikan , 2 adalah , dengan gabungan dari digraf komplit dengan m titik dan n titik yang sisinya berarah bolak-balik atau diperoleh bentuk umum dengan , , 2, dan (3) digraf eksentrik iterasi kedua pada digraf komplit multipartit , , , adalah digraf komplit multipartit , , , itu sendiri. Berdasarkan hasil penelitian tersebut penulis menyarankan kepada peneliti lain untuk mengkaji bentuk digraf eksentrik iterasi pertama dari digraf komplit multipartit dan digraf eksentrik dari graf atau digraf yang lain.

viii

DAFTAR ISI HALAMAN JUDUL .....................................................................................

i

PERNYATAAN ...........................................................................................

ii

HALAMAN PENGESAHAN ......................................................................

iii

MOTTO DAN PERSEMBAHAN ...............................................................

iv

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

v

ABSTRAK .................................................................................................... vii DAFTAR ISI ................................................................................................. viii DAFTAR SIMBOL ......................................................................................

x

DAFTAR GAMBAR ....................................................................................

xi

DAFTAR TABEL ......................................................................................... xiii BAB 1 PENDAHULUAN .............................................................................

1

1.1 Latar Belakang .........................................................................................

1

1.2 Perumusan Masalah ................................................................................

2

1.3 Tujuan dan Manfaat ................................................................................

3

1.4 Sistematika Penulisan ..............................................................................

4

BAB 2 LANDASAN TEORI ........................................................................

5

2.1 Graf .........................................................................................................

5

2.2 Digraf ..................................................................................................... 17 2.3 Digraf Eksentrik ...................................................................................... 23 2.4 Graf Komplit Bipartit ............................................................................. 35 2.5 Digraf Komplit Multipartit ...................................................................... 38 BAB 3 METODE PENELITIAN ................................................................. 41 3.1 Penemuan Masalah .................................................................................. 41 3.2 Perumusan Masalah ................................................................................ 41 3.3 Studi Pustaka .......................................................................................... 42 3.4 Analisis Pemecahan Masalah .................................................................. 42 3.5 Penarikan Kesimpulan ............................................................................. 43 BAB 4 HASIL PENELITIAN DAN PEMBAHASAN ................................. 44 4.1 Langkah-langkah Mengkonstruksi Digraf Eksentrik ................................. 44 ix

4.2 Digraf Eksentrik dari Graf Komplit Bipartit ............................................ 46 4.3 Digraf Eksentrik dari Digraf Komplit Multipartit ..................................... 62 BAB 5 SIMPULAN DAN SARAN ............................................................... 78 5.1 Simpulan .................................................................................................. 78 5.2 Saran........................................................................................................ 80 DAFTAR PUSTAKA .................................................................................... 81

x

DAFTAR SIMBOL 1.

Graf

2.

Digraf

3.

Himpunan titik di Graf

4.

Himpunan sisi di Graf ,

5.

Graf G dengan order

dan size

Graf G reguler dengan derajat

6. ,

7.

raf G dengan order

dan size

Sub bagian

8. 9.

Reduksi Digraf D

10.

Komplemen reduksi Digraf D

11.

,

Jarak dari

ke

pada suatu graf

12.

,

Jarak dari

ke

pada suatu digraf

Eksentrisitas dari titik

13. 14.

raf eksentrik pada G

15.

raf eksentrik pada raf eksentrik iterasi ke

16. 17.

Graf komplit dengan

18.

Digraf komplit dengan

titik titik

19.

Himpunan titik di Digraf

20.

Komplemen

21.

Digraf multipartit dengan partit

, , ,…,

22.

,

Graf komplit bipartit

23.

,

Digraf komplit bipartit

24.

,

Komplemen

25.

pada

,

,

raf eksentrik dari

26.

Himpunan graf atau digraf ke

27. ∞

Tak hingga xi

,

DAFTAR GAMBAR Gambar

Halaman

1. Gambar 2.1.1 Graf G .................................................................................. 8 2. Gambar 2.1.2 Graf G .................................................................................. 9 3. Gambar 2.1.3 Graf regular orde 4 .............................................................. 10 4. Gambar 2.1.4 Graf G dan komplemennya .................................................. 11 5. Gambar 2.1.5 Graf G ................................................................................. 12 6. Gambar 2.1.6 Graf G .................................................................................. 13 7. Gambar 2.1.7 Graf G ................................................................................. 14 8. Gambar 2.1.8 Graf G Sederhana ................................................................ 15 9. Gambar 2.1.9 Graf Ganda dan Graf Semu ................................................. 15 10. Gambar 2.1.10 Dua Graf Tak Berhingga .................................................... 16 11. Gambar 2.1.11Graf Berarah dan Tak Berarah ............................................. 17 12. Gambar 2.2.1 Digraf D .............................................................................. 17 13. Gambar 2.2.2 Digraf

Subgraf Digraf

............................................... 19

14. Gambar 2.2.3 Digraf Komplit ..................................................................... 20 15. Gambar 2.2.4 Graf Berarah......................................................................... 20 16. Gambar 2.2.5 Digraf G, reduksi digraf G, komplemen redusi digraf G ....... 21 17. Gambar 2.2.6 Digraf D .............................................................................. 21 18. Gambar 2.2.7 (a) Digraf Terhubung Lemah, (b) Digraf Terhubung Kuat ... 23 19. Gambar 2.3.1 Graf G ................................................................................. 23 20. Gambar 2.3.2 Graf Hubungan Radius G dan Diameter G ........................... 25 21. Gambar 2.3.3 Eksentrisitas ........................................................................ 25 22. Gambar 2.3.4 Digraf D ............................................................................... 28 23. Gambar 2.3.5 Graf G dan Digraf Eksentrisnya ........................................... 29 24. Gambar 2.3.6 Digraf Eksentrik dari Digraf D ............................................ 30 25. Gambar 2.3.7 Digraf Eksentrik pada iterasi k pada Digraf G ..................... 31 26. Gambar 2.4.1 Graf Komplit Kn ................................................................... 37 27. Gambar 2.4.2 Graf Bipartit K3,4 .................................................................. 37 xii

28. Gambar 2.4.3 Graf Komplit Bipartit K2,3 .................................................... 38 29. Gambar 2.5.1 Digraf Multipartit K2,2,2,3 Tak Komplit .................................. 39 30. Gambar 2.5.2 Digraf Komplit Multipartit K2,2,2,3 ......................................... 39 31. Gambar 4.2.1 Graf Komplit Bipartit K2,2 .................................................... 48 32. Gambar 4.2.2 Digraf Eksentrik dari Graf Komplit Bipartit K2,2 ................... 49 33. Gambar 4.2.3 Graf Komplit Bipartit K2,3 .................................................... 50 34. Gambar 4.2.4 Digraf Eksentrik dari Graf Komplit Bipartit K2,3 ................... 51 35. Gambar 4.2.5 Graf Komplit Bipartit K2,4 .................................................... 52 36. Gambar 4.2.6 Digraf Eksentrik dari Graf Komplit Bipartit K2,4 ................... 53 37. Gambar 4.2.7 Graf Komplit Bipartit K2,5 .................................................... 54 38. Gambar 4.2.8 Digraf Eksentrik dari Graf Komplit Bipartit K2,5 ................... 56 39. Gambar 4.2.9 Graf Komplit Bipartit K3,2 .................................................... 56 40. Gambar 4.2.10 Digraf Eksentrik dari Graf Komplit Bipartit K3,2.................. 57 41. Gambar 4.2.11 Graf Komplit Bipartit K3,3 ................................................... 58 42. Gambar 4.2.12 Digraf Eksentrik dari Graf Komplit Bipartit K3,3.................. 58 43. Gambar 4.2.13 Graf Komplit Bipartit K3,4 ................................................... 59 44. Gambar 4.2.14 Digraf Eksentrik dari Graf Komplit Bipartit K3,4.................. 59 45. Gambar 4.2.15 Graf Komplit Bipartit K3,5 ................................................... 60 46. Gambar 4.2.16 Digraf Eksentrik dari Graf Komplit Bipartit K3,5.................. 60 47. Gambar 4.3.1 Digraf Komplit Multipartit K2,2,3........................................... 64 48. Gambar 4.3.2 Digraf Komplit Multipartit K2,3 ............................................. 68 49. Gambar 4.3.3 Digraf Eksentrik dari Digraf Komplit Multipartit K2,3 ........... 69 50. Gambar 4.3.4 Digraf Komplit Multipartit K2,2,3........................................... 70 51. Gambar 4.3.5 Digraf Eksentrik dari Digraf Komplit Multipartit K2,2,3 ......... 72 52. Gambar 4.3.6 Digraf Eksentrik Iterasi kedua dari Digraf Komplit Multipartit K2,3 .................………… ............................................................................. 75 53. Gambar 4.3.7 Digraf Eksentrik Iterasi kedua dari Digraf Komplit Multipartit K2,2,3 .............. ………… ............................................................................. 77

xiii

DAFTAR TABEL Tabel

Halaman

1. Tabel 2.3.1 Eksentrisitas Graf G ................................................................ 26 2. Tabel 2.3.2 Eksentrisitas Digraf

............................................................... 29

3. Tabel 2.3.3 Eksentrisitas Digraf D pada Gambar 2.3.7 ............................... 32 4. Tabel 2.3.4 Eksentrisitas Digraf

pada Gambar 2.3.7 ........................ 33

5. Tabel 2.3.5 Eksentrisitas Digraf

pada Gambar 2.3.7....................... 34

6. Tabel 4.2.1 Eksentrisitas Graf Komplit Bipartit K2,2 .................................... 49 7. Tabel 4.2.2 Eksentrisitas Graf Komplit Bipartit K2,3 .................................... 50 8. Tabel 4.2.3 Eksentrisitas Graf Komplit Bipartit K2,4 .................................... 52 9. Tabel 4.2.4 Eksentrisitas Graf Komplit Bipartit K2,5 .................................... 55 10. Tabel 4.2.5 Eksentrisitas Graf Komplit Bipartit K3,4 .................................... 57 11. Tabel 4.2.6 Eksentrisitas Graf Komplit Bipartit K3,5 .................................... 60 12. Tabel 4.3.1 Eksentrisitas Digraf Komplit Multipartit K2,3 ............................ 69 13. Tabel 4.3.2 Eksentrisitas Digraf Komplit Multipartit K2,2,3 .......................... 71 14. Tabel 4.3.3 Eksentrisitas Iterasi Kedua Digraf Komplit Multipartit K2,3 ...... 74 15. Tabel 4.3.4 Eksentrisitas Iterasi Kedua Digraf Komplit Multipartit K2,2,3 .... 77

xiv

BAB 1 PENDAHULUAN

1.1 Latar Belakang Dewasa ini teori graf telah memantapkan dirinya sebagai alat matematika yang sangat penting dan berguna. Hal ini sangat berhubungan dengan struktur diskrit yang ada pada sistem. Banyak ilmu yang memanfaatkan Teori Graf (Graph Theory), mulai dari proses komputasi sampai dengan Kimia, Genetika, Sosiologi, Kartografi dan beberapa masalah dalam jaringan komunikasi, transportasi, ilmu komputer, riset operasi, dan lain sebagainya. Graf digunakan untuk mempresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graf adalah dengan menyatakan objek sebagai noktah, bulatan, verteks atau titik. Sedangkan hubungan antara objek dinyatakan dengan garis atau edge. Graf dapat digunakan untuk merepresentasikan beberapa struktur objek, salah satu aplikasinya adalah menentukan jarak 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. Kumpulan titik eksentrik yang dihubungkan dengan garis pada suatu graf disebut digraf eksentrik pada suatu graf. Sedangkan kumpulan titik eksentrik yang dihubungkan dengan busur pada suatu digraf disebut digraf eksentrik pada digraf. 1

2

Digraf eksentrik pada graf diperkenalkan pertama kalinya oleh Fred Buckley pada tahun 1990-an yakni digraf Eksentrik ED(G) pada graf G didefinisikan sebagai graf yang mempunyai himpunan titik yang sama dengan himpunan titik di G atau V(ED(G))=V(G), di mana arc (busur) yang menghubungkan titik

ke

, jika

adalah titik eksentrik dari

. Sedangkan Bolland dan

Miller pada tahun 2001 mulai memperkenalkan digraf eksentrik pada digraf atau dituliskan

didefinisikan sebagai digraf yang mempunyai

himpunan titik yang sama dengan himpunan titik di D atau , dimana arc (busur) menghubungkan titik adalah titik eksentrik dari

ke

, jika hanya jika

.

Berdasarkan deskripsi di atas, penulis mempunyai rasa ingin tahu lebih dalam tentang digraf eksentrik baik dari graf maupun digraf dan untuk mengembangkan penelitian ini, penulis tertarik untuk membahas digraf eksentrik dari graf komplit bipartit dan digraf eksentrik dari digraf komplit multipartit.

1.2 Perumusan Masalah Berdasarkan uraian di atas, maka permasalahan yang dapat dirumuskan dalam penulisan ini adalah sebagai berikut. 1.2.1 Bagaimana langkah-langkah mengkonstruksi digraf eksentrik dari graf dan digraf? 1.2.2 Bagaimana bentuk digraf eksentrik dari graf komplit bipartit? 1.2.3 Bagaimana bentuk digraf eksentrik dari digraf komplit multipartit?

3

1.3 Tujuan dan Manfaat 1.3.1 Tujuan Tujuan dari penelitian ini adalah sebagai berikut. 1.3.1.1 Mengetahui bagaimana langkah-langkah mengkonstuksi digraf eksentrik dari graf dan digraf. 1.3.1.2 Mengetahui bagaimana bentuk digraf eksentrik dari graf komplit bipartit. 1.3.1.3 Mengetahui bagaimana bentuk digraf eksentrik dari

digraf

komplit multipartit. 1.3.2 Manfaat Manfaat dari penelitian ini adalah sebagai berikut. 1.3.2.1 Bagi penulis Untuk mengembangkan ilmu pengetahuan, terutama dalam menentukan bentuk digraf eksentrik dari graf komplit bipartit dan digraf eksentrik dari digraf komplit multipartit. 1.3.2.2 Bagi Jurusan Matematika Universitas Negeri Semarang Dapat digunakan sebagai khazanah dan sumber referensi baru khususnya dalam kajian matematika mata kuliah Matematika Diskrit. 1.3.2.3 Bagi pembaca Untuk menambah ilmu pengetahuan terutama dalam hal menentukan bentuk digraf eksentrik dari graf komplit bipartit dan digraf eksentrik dari digraf komplit multipartit.

4

1.4 Sistematika Penulisan BAB 1

Merupakan bab pendahuluan yang berisi tentang latar belakang, perumusan masalah, tujuan dan manfaat penelitian.

BAB 2

Menguraikan materi penunjang yang menjadi dasar teori disusunnya skripsi ini.

BAB 3

Menguraikan tentang metode penelitian yaitu langkah-langkah yang dilakukan peneliti.

BAB 4

Menguraikan

pembahasan

tentang

langkah-langkah

mengkonstruksi digraf eksentrik dari graf komplit bipartit dan digraf eksentrik dari digraf komplit multipartit. BAB 5

Berisi kesimpulan dan saran dari pembahasan tentang bentuk digraf eksentrik dari graf komplit bipartit dan digraf eksentrik dari digraf komplit multipartit.

BAB 2 LANDASAN TEORI 2.1 Graf Teori graf merupakan pokok bahasan yang sudah tua usianya namun memiliki banyak terapan sampai saat

ini. Graf digunakan untuk

merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graf adalah dengan menyatakan objek sebagai noktah, bulatan, atau titik, sedangkan hubungan antara objek dinyatakan dengan garis. Sebelum mempelajari teori graf lebih lanjut, diperlukan pengantar sebagaimana berikut. 2.1.1 Sejarah Graf 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 teori tersebut tidak ada perkembangan berarti mengenai 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.

5

6

Pada masa Kirchoff dan Cayley juga telah lahir dua hal penting dalam teori graf. Salah satunya berkenaan dengan konjektur empat warna, yang menyatakan bahwa untuk mewarnai sebuah atlas cukup dengan menggunakan empat macam warna sedemikian hingga 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 (1970-1868) dalam salah satu kuliahnya di tahun 1840. Sepuluh tahun kemudian, A. Demorgan dianggap sebagai referensi pertama berkenaan dengan masalah empat warna. Masalah empat warna ini menjadi sangat terkenal setelah Cayley mempublikasikasikan tahun 1839 dalam Proceeding of the Royal Geographic Society volume pertama. Hal

yang

penting

untuk

dibicarakan

sehubungan

dengan

perkembangan teori graf adalah apa yang dikemukakam oleh Sir W. R. Hamilton (1805-1865). Pada tahun 1859 ia berhasil menemukan suatu permainan yng 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 dan lain-lain. Masalah dalam permainan ini adalah mencari suatu rute melalui sisi-sisi dodecahedron

7

sehingga tiap kota dari 20 kota yang ada dapat dilalui tepat satu kali. Walaupun saat ini masalah tersebut dikategorikan mudah, akan tetapi saat iti tidak ada seorangpun yang menemukan syarat perlu dan cukup dari eksistensi rute yang dicari. Kurang lebih setengah abad setelah masa Hamilton, aktivitas penelitian dalam bidang graf 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 diterbitkan pada tahun 1936. Tiga puluh tahun terakhir ini merupakan periode yang sangat intensif dalam aktifitas pengembangan teori graf baik murni maupun terapan. Sejumlah penelitian telah dilakukan, ribuan artikel telah diterbitkan, dan lusinan buku telah banyak tertulis. Di antara orang terkenal yang banyak berkecimpung dalam bidang Graf adalah Claude Berge, Oysten Ore, Paul Erdos, William Tutte, dan Frank Harary. 2.1.2 Definisi dan Terminologi Dasar Graf Definisi 2.1.2.1 Graf G adalah pasangan (

,

, di mana

himpunan berhingga titik-titik (vertices) yang tak kosong dan

adalah adalah

himpunan sisi (mungkin kosong), sedemikian hingga setiap sisi (edge) di

8

adalah pasangan tak berurutan dari titik-titik di dari

dinotasikan dengan

dengan

. Himpunan titik

, sedangkan himpunan sisi dinotasikan

(Budayasa, 1997).

Definisi 2.1.2.2 Jika terdapat sisi menghubungkan titik dan

,

,

, maka sisi

,

dan . Jika

dikatakan

adalah sisi pada graf , maka

disebut titik yang berhubungan langsung atau bertetangga (adjacent).

Sedangkan

dan

disebut terkait (incident), sama seperti

dan

(Chartrand

and Lesniak, 1996). Contoh

v5

Gambar 2.1.1 Graf G Pada gambar 2.1.1, titik

bertetangga dengan titik

titik

tidak bertetangga dengan titik

titik

dan

seterusnya.

dan

, tetapi

. Sisi e1 incident (terkait) dengan

, sisi e2 incident (terkait) dengan titik

dan

, dan

9

Definisi 2.1.2.3 Kardinalitas himpunan titik dari graf , | | atau

dinotasikan dengan

disebut order dari graf

dan

jika graf yang dimaksudkan jelas.

Sedangkan kardinalitas dari himpunan sisi disebut size yang dinotasikan , | | atau

dengan

,

. Suatu graf

mempunyai order

dan size

(Chartrand and Lesniak, 1996). Contoh Graf

pada gambar 2.1.1 halaman 8, mempunyai order 4 dan size 5.

Definisi 2.1.2.4 Derajat dari titik

pada graf

adalah jumlah sisi pada

yang terkait

atau deg . Suatu titik dikatakan

dengan , yang dinotasikan dengan

ganjil atau genap sesuai dengan derajat titik tersebut ganjil atau genap (Chartrand and Lesniak, 1996). Contoh

G

v

e

e

e

v

e Gambar 2.1.2 Graf G Pada gambar 2.1.2, titik sedangkan

dan

dan

v e v

berderajat 2 atau merupakan titik genap,

berderajat 3 atau merupakan titik ganjil.

10

Definisi 2.1.2.5 Suatu graf setiap titik di

jika deg

dikatakan reguler dengan derajat

untuk

(Chartrand and Lesniak, 1996).

Contoh

Gambar 2.1.3 Graf reguler orde 4 Pada gambar 2.1.3, graf reguler graf reguler

berderajat 0, graf reguler

berderajat 2, dan graf reguler

berderajat 1,

berderajat 3.

Definisi 2.1.2.6 Suatu graf sederhana dikatakan komplit (complete) jika setiap 2 titiknya bertetangga. Graf komplit 1 dan jumlah sisi

derajat

,

, dengan

merupakan graf reguler dengan dan dinotasikan dengan

(Chartrand and Lesniak, 1996). Contoh Pada gambar 2.1.3, graf reguler

adalah graf komplit.

Definisi 2.1.2.7 Komplemen dari graf himpunan titik

(diberi simbol dengan

adalah graf dengan

di mana dua titik dikatakan bertetangga di

jika dan

11

hanya jika titik tersebut tidak bertetangga di

(Chartrand and Lesniak,

1996). Contoh

G:

:

Gambar 2.1.4 Graf G dan komplemennya Definisi 2.1.2.8 Misal

dan

titik-titik pada graf

. Jalan (walk)

pada graf

adalah barisan berhingga titik dan sisi

sedemikian hingga panjang dari jalan. Suatu jalan disebut terbuka jika

,

1,2,3, … , , dengan disebut tertutup jika

(Chartrand and Lesniak, 1996).

adalah dan jalan

12

Contoh

Gambar 2.1.5 Graf G Pada gambar 2.1.5 jalan adalah jalan tertutup dengan panjang 5 dan adalah jalan terbuka dengan panjang 6. Definisi 2.1.2.9 Jika semua sisi

dalam suatu jalan adalah

berbeda, maka disebut jejak (trail) dan jika semua titik dalam suatu jejak juga berbeda, maka disebut lintasan (path) (Sutarno, 2003). Contoh Pada gambar 2.1.5, jalan adalah jejak tetapi bukan lintasan, sedangkan adalah lintasan. Definisi 2.1.2.10 Lintasan terpendek (shortest path) adalah lintasan dengan jumlah sisi paling sedikit.

13

Contoh Pada gambar 2.1.5 halaman 12, lintasan terpendek dari titik

ke

adalah

dengan panjang lintasan 2. Definisi 2.1.2.11 Jejak tertutup disebut sirkuit. Sirkuit yang titik intervalnya berlainan disebut siklus (Cycle) (Sutarno, 2003). Contoh Pada gambar 2.1.5 halaman 12, jalan adalah siklus. Definisi 2.1.2.12 Suatu graf

dikatakan terhubung jika terdapat lintasan untuk setiap

pasang titik di . Contoh G:

a

d

H: a b

d c

b

c

e

Gambar 2.1.6 Graf G Pada gambar 2.1.6, graf terhubung.

adalah graf terhubung dan graf

adalah graf tidak

14

Definisi 2.1.2.13 Jika terdapat lebih dari dua sisi yang berkaitan dengan sepasang titik pada graf maka sisi tersebut disebut sisi ganda (pararel edges). Sedangkan loop adalah sisi yang kedua titik ujungnya sama. Contoh

Gambar 2.1.7 Graf G Pada gambar 2.1.7, titik (1,3) merupakan sisi ganda yang dihubungkan oleh sisi e3 dan e4, titik (3,4) merupakan merupakan sisi ganda yang dihubungkan oleh sisi e6 dan e7, sedangkan e8 merupakan loop yang kedua titik ujungnya adalah titik 3. 2.1.3 Jenis-Jenis Graf Graf dapat dikelompokkan menjadi beberapa kategori (jenis) bergantung pada sudut pandang pengelompokannya. Pengelompokan graf dapat dipandang berdasarkan ada tidaknya sisi ganda atau loop, berdasarkan jumlah titik, atau berdasarkan orientasi arah pada sisi.

15

Berdasarkan ada tidaknya sisi ganda atau loop pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis. a. Graf sederhana (simple graph). Graf yang tidak mengandung loop atau sisi ganda dinamakan graf sederhana. Contoh 1

2 4 3

Gambar 2.1.8 Graf sederhana b. Graf tak-sederhana (unsimple-graph). Graf yang mengandung sisi ganda atau gelang dinamakan graf taksederhana (unsimple graph). Ada dua macam graf tak sederhana, yaitu graf ganda (multigraph) dan graf semu (pseudograph). Graf ganda adalah graf yang mengandung sisi ganda. Sedangkan graf semu adalah graf yang mengandung loop dan terkadang memiliki sisi ganda pula. Contoh (a) Graf ganda

(b) Graf semu

Gambar 2.1.9 (a) graf ganda dan (b) graf semu

16

Berdasarkan jumlah titik pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis: a. Graf berhingga (limited graph) Graf berhingga adalah graf yang jumlah simpulnya

berhingga. Dua

buah graf pada Gambar 2.1.9 adalah contoh graf yang berhingga. b. Graf tak-berhingga (unlimited graph) Graf yang jumlah simpulnya

, tidak berhingga banyaknya disebut

graf tak-berhingga. Dua buah graf pada Gambar 2.1.10 adalah contoh graf yang tidak berhingga.

Gambar 2.1.10 Dua buah graf tak berhingga Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis: a. 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 (vj, vk) = (vk, vj) adalah sisi yang sama. Tiga buah graf pada Gambar 2.1.9 dan dua graf pada Gambar 2.1.10 adalah graf tak berarah. b. Graf berarah (directed graph atau digraph) Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Sisi berarah biasa disebut busur (arc). Pada graf

17

2.1.11 merupakan graf berarah, (vj, vk)

(vk, vj) menyatakan dua buah

busur yang berbeda atau dengan kata lain vj dinamakan titik asal (initial vertex) dan titik vk dinamakan titik terminal (terminal vertex).

Gambar 2.1.11 (a) graf berarah (b) graf-ganda berarah

2.2 Digraf Definisi 2.2.1 Graf berarah atau digraf (digraph) D adalah himpunan berhingga tak kosong dari objek-objek yang disebut titik dengan himpunan (mungkin kosong) pasangan berurutan dari titik di D yang disebut arc atau sisi berarah atau busur (Chartrand and Lesniak, 1996). Contoh :

Gambar 2.2.1. Digraf D Seperti pada graf himpunan titik-titik dari himpunan sisi dinotasikan dengan , ,

dan

,

,

dinotasikan dengan

dan

. Pada gambar 2.2.1, digraf

dengan

,

,

,

. Sisi

,

,

.

18

Definisi 2.2.2 Order dari digraf D adalah kardinalitas himpunan titik dari digraf D dinotasikan dengan n(D) atau

. Size dari digraf D adalah kardinalitas dari

himpunan arc digraf D dinotasikan dengan adalah digraf dengan order

dan size

atau

. Digraf

,

.

Contoh Pada gambar 2.2.1, digraf

mempunyai order 3 dan size 3.

Definisi 2.2.3 ,

Jika menghubungkan sedangkan

adalah arc dari digraf

ke

terkait ke

bertetangga ke

dan

,

jika dan

. Arc

terkait dari

terkait dari

bertetangga dari . Titik

bertetangga (nonadjacent) jika

, maka

disebut

dan terkait ke ,

. Atau dapat dikatakan dan

pada digraf

tidak bertetangga ke

tidak

atau tidak

bertetangga dari . Contoh ,

Pada gambar 2.2.1 halaman 17, misal . Titik

bertetangga ke titik , tetapi ,

Jika terdapat

terkait dari

tidak bertetangga ke titik . ,

dan ,

dalam dua bentuk yaitu dua busur

maka dapat digambarkan dan

dengan satu busur yang arahnya bolak-balik. Contoh a v

u b

a

u

dan terkait ke

v

b

Gambar 2.2.2. Digraf D dengan arc (u,v) dan (v,u)

,

atau cukup

19

Definisi 2.2.4 Out-neighbours pada digraf bertetangga dari suatu titik

adalah himpunan titik di digraf

dinotasikan dengan

dengan kardinalitas

sama dengan derajat keluar . In-neighbours pada digraf titik yang bertetangga ke suatu titik

yang

pada digraf

adalah himpunan dinotasikan dengan

dengan kardinalitas sama dengan derajat masuk . Contoh Pada gambar 2.2.1 halaman 17,

,

dan

.

Definisi 2.2.5 Suatu digraf

adalah subdigraf dari

jika

dan

. Contoh

Gambar 2.2.3 Digraf

adalah subdigraf dari digraf

Definisi 2.2.6 Suatu arc disebut pararel arc jika ada lebih dari satu arc pada arah yang sama yang menghubungkan dua titik dalam digraf. Digraf yang memuat pararel arc disebut multidigraf (Chartrand and Lesniak, 1996). Sebagai contoh graf pada gambar 2.2.4(b).

20

Definisi 2.2.7 Loop adalah busur yang menghubungkan suatu titik pada dirinya sendiri. Digraf yang mempunyai pararel arc dan loop disebut pseudodigraf (Chartrand and Lesniak, 1996). Contoh

(a)

(b)

Gambar 2.2.4 Graf Berarah Pada gambar 2.2.4, (a) pseudodigraf, (b) multidigraf. Definisi 2.2.8 Komplemen digraf

dinotasikan dengan

mempunyai himpunan titik komplemen

yang sama dengan ,

arc

Misalkan suatu digraf

dengan

yaitu digraf yang dan himpunan |

titik, reduksi dari

,

.

dinotasikan dengan

adalah digraf yang diperoleh dengan menghapus semua arc yang terkait dari titik yang mempunyai derajat keluar

1.

Contoh

Gambar 2.2.5 Digraf D, reduksi digraf D, komplemen reduksi digraf D

21

Definisi 2.2.9 Untuk setiap titik

dan

di digraf

, jalan

-

pada

adalah

barisan berhingga titik dan arc

,

sedemikian hingga

1,2,3, … , , dengan

adalah

panjang dari jalan (Chartrand and Lesniak, 1996). Contoh b

a c d

f

e

Gambar 2.2.6 Digraf D Pada gambar 2.2.6, jalan

adalah jalan dengan

panjang 3. Definisi 2.2.10 Lintasan berarah (directed path) sama seperti pada lintasan sederhana dan setiap arc mempunyai arah yang sama, ini berarti bahwa setiap titik internalnya mempunyai derajat masuk dan derajat keluar 1. Titik terjangkau (reachable) dari titik

jika terdapat lintasan berarah dari

dikatakan ke .

Definisi 2.2.11 Lintasan berarah terpendek (shortest directed path) adalah lintasan berarah dengan jumlah sisi paling sedikit.

22

Contoh Pada gambar 2.2.6 halaman 21, lintasan yang menghubungkan titik 1 ke titik 3 adalah :

,

, dan

.

Yang memiliki jumlah sisi paling sedikit yaitu lintasan lintasan

adalah lintasan terpendek dari titik

terjangkau dari titik

, jadi ke titik

, karena terdapat lintasan berarah dari

ke

. Titik .

Definisi 2.2.12 Digraf

disebut terhubung kuat (strongly connected) jika untuk

setiap pasang titik sembarang dan juga lintasan berarah dari

dan

di

terdapat lintasan berarah dari

ke

ke .

Definisi 2.2.13 Digraf

dikatakan terhubung lemah (weakly connected) jika tidak

terhubung kuat tetapi terhubung pada graf tak berarahnya. Contoh w

a

x y

z (a)

c

b (b)

Gambar 2.2.7 (a) digraf terhubung lemah, (b) digraf terhubung kuat

23

2.3 Digraf Eksentrik Definisi 2.3.1 Jarak terpendek lintasan dari

,

dari

di

.(Chartrand and Lesniak, 1996). Jika tidak terdapat

ke

maka

ke

,

pada graf

adalah panjang lintasan

∞.

Contoh

Gambar 2.3.1 Graf G Gambar 2.3.1,

,

= 2 sedangkan

,

∞.

Definisi 2.3.2 Eksentrisitas setiap

di

dari

dalam

adalah jarak maksimal dari ,

, atau dapat ditulis

disebut titik eksentrik jika jarak dari

ke

|

sama dengan

adalah eksentrisitas minimum dari setiap titik di |

,

sedangkan

diameter

ke

. Titik . Radius dari , dapat ditulis dari

adalah eksentrisitas maksimum dari setiap titik di , dapat ditulis | disebut titik sentral (central) jika

(Chartrand and Lesniak, 1996). Titik . Central dari

dinotasikan

24

adalah subgraf pada

yang terbentuk dari titik central. Titik

dikatakan titik eksentrik dari

jika jarak dari

eksentrik dari , dapat dituliskan

,

ke

sama dengan titik

.

Teorema 2.3.1 Untuk setiap graf terhubung , antara radius dan diameter

terdapat

hubungan sebagai berikut: 2 Bukti: Pertidaksamaan

adalah suatu konskuensi langsung dari min

definisi yaitu

max

dan

menunjukkan ketidaksaman yang kedua, pilih titik hingga . Titik

, ke

. Kemudian misalkan melalui titik sentral

dan

. Karena

di , sedemikian

sebagai titik central dari

karena jarak

panjang dari lintasan terpendek yang menghubungkan melalui titik sentral

. Untuk

, dan

adalah metrik pada

di

merupakan di

jika

ke

, sedemikian

hingga terdapat sifat ketaksamaan segitiga (triangle inequality) sebagai berikut. ,

,

,

2

Sehingga grafnya dapat digambarkan pada Gambar 2.3.2

25

Gambar 2.3.2 Graf hubungan radius G dan diameter G Eksentrisitas titik, titik eksentrik, radius, diameter dan central dari graf dapat dilihat pada gambar 2.3.3 Contoh

Gambar 2.3.3 Eksentrisitas

Dari gambar 2.3.3 diperoleh eksentrisitas sebagai berikut. ,

,

,

,

1, 1, 2, 2, 3 ,

,

,

1,2,1,2,3

,

,

,

,

3, ,

1,2,1,1,2 ,

,

,

. ,

,

,

,

,

2, ,

, . ,

3,

,

,

,

,

, .

26

,

,

,

2,1,1,1,2 ,

,

,

3,2,3,2,1

,

,

,

,

,

2, ,

2,1,2,1,1 ,

,

, . ,

,

,

,

,

,

2, ,

, . ,

,

,

,

,

,

3,

, .

Tabel 2.3.1 Eksentrisitas Graf G dari Gambar 2.3.3 Titik

Eksentrisitas

Titik Eksentrik

a

3

f

b

2

c, f

c

3

f

d

2

a, f

e

2

a, c

f

3

a, c

Diperoleh rad (G) = min {3,2,3,2,2,3}=2, diam (G) = maks {3,2,3,2,2,3}=3, dan titik central

= b, d dan e sehingga

d

e

b

adalah

27

Definisi 2.3.3 ,

Jarak (berarah) terpendek

dari ,

di D. Jarak

ke

adalah panjang lintasan berarah ,

dan

tersebut didefinisikan untuk

setiap pasang titik pada digraf terhubung kuat (Chartrand and Lesniak, 1996). Jika tidak terdapat lintasan berarah dari

ke

maka

,

∞.

,

∞.

Contoh Pada gambar 2.2.7 (a),

,

1 dan

dari

dalam

Definisi 2.3.4 Eksentrisitas setiap

di

adalah jarak maksimal dari ,

, atau dapat ditulis

disebut titik eksentrik jika jarak dari

ke

|

. Titik

sama dengan

. Radius dari

adalah eksentrisitas minimum dari setiap titik di |

ke

, dapat ditulis

, sedangkan diameter dari

adalah eksentrisitas maksimum dari setiap titik di , dapat ditulis |

(Chartrand and Lesniak, 1996). Titik

sentral (central) jika

disebut titik

.

Contoh f e

a

b

d

c

Gambar 2.3.4 Digraf D Dari gambar 2.3.4, diperoleh eksentrisitas sebagai berikut. ,

,

,

,

,

,

,

,

,

28

1, 2, 4, 3, 4 ,

,

4, ,

2,1,3,2,3 , 1,2,2,1,2

,

,

, . ,

,

,

,

3, ,

, . ,

,

,

,

,

2, ,

,

,

2,3,1,1,1 ,

, ,

2,4,1,1,2 ,

,

,

1,2,3,5,4

,

,

,

,

,

.

,

,

4, ,

. ,

,

,

,

,

,

3, ,

. ,

,

,

,

,

5,

, .

Tabel 2.3.2 Eksentrisitas Digraf D dari Gambar 2.3.4 Titik

Eksentrisitas

Titik Eksentrik

a

4

d, f

b

3

d, f

c

2

b, d, f

d

4

b

e

3

b

f

5

d

Diperoleh rad (D) = min {4,3,2,4,3,5}= 2, diam (D) = maks {4,3,2,4,3,5}= 5, dan titik sentral D adalah c sehingga

adalah c itu sendiri.

29

Definisi 2.3.5 Digraf Eksentrik dari graf

(dinotasikan

) didefinisikan

sebagai graf yang mempunyai himpunan titik yang sama dengan himpunan titik di

atau

, dengan arc dari titik

dan hanya jika

ke

di

jika

adalah titik eksentrik dari .

Contoh a

b

b

a e c

e

f

d

c

f

d

G

Gambar 2.3.5 Graf G dan Digraf Eksentriknya Definisi 2.3.6 Digraf Eksentrik dari digraf

yang dinotasikan dengan

didefinisikan sebagai digraf yang mempunyai himpunan titik yang sama dengan himpunan titik di , dengan arc dari titik hanya jika

adalah titik eksentrik dari .

ke

pada

jika dan

30

Contoh Dari gambar 2.3.4 halaman 28, diperoleh digraf eksentrik sebagai berikut. f d

e

a

b

c

Gambar 2.3.6 Digraf Eksentrik dari Digraf D Definisi 2.3.7 2, eksentrik digraf pada iterasi

Diberikan bilangan bulat positif digraf D ditulis

di mana

pada .

Contoh (a)

a

(b)

b

a e

c

d D

b

f

e c

d

f

31

a

(c)

b

a

e c

f

e

d

c

f

d

Gambar 2.3.7 Digraf Eksentrik iterasi Dari digraf

(d)

b

pada digraf D

pada gambar 2.3.7 (a), diperoleh digraf eksentrisitas

dengan perhitungan sebagai berikut. ,

,

,

,

3, 1,2, 3, 4 ,

,

,

,

,

2,1,3,1,2 ,

,

3,2,4,1,1 ,

,

4,3,5,2,1

,

,

,

,

. ,

,

,

,

,

2, ,

3,2,1,2,3 ,

,

4,

1,2,1,1,2 ,

,

, . ,

,

,

,

,

,

3, ,

, . ,

,

,

,

,

,

,

,

,

3 ,

,

,

,

4, ,

. ,

5,

,

,

,

,

, .

32

Tabel 2.3.3 eksentrisitas

dari Gambar 2.3.7

Titik

Eksentrisitas

Titik Eksentrik

a

4

f

b

2

c, f

c

3

a, f

d

3

c

e

4

c

f

5

c 4,2,3,3,4,5

Diperoleh

2,

diam (D) = maks {4,2,3,3,4,5}= 5, dan titik sentral D adalah b. Dari ED(D) pada gambar 2.3.7(b), diperoleh digraf eksentrisitas E

(D)


,

,

∞, 2, ∞, ∞, 1 ,

,

2,1, ∞, ∞, 1 ,

,

,

,

,

,

2, ∞, 1, ∞, ∞

,

,

, , ,

,

,

,

,

,

,

, ,

,

,

,

,

,

,

∞ ,

, , ,

,

,

,

,

,

∞ ,

2, ∞, 1, ∞, 2 ,

,

∞

2, ∞, 1, ∞, 2 ,

,

∞

1, ∞, ∞, ∞, 1 ,

,

, ,

,

,

,

,

,

∞ ,

, ,

∞

,

,

,

,

, , ,

33

Tabel 2.3.4 Eksentrisitas ED(D) dari Gambar 2.3.7 Titik

Eksentrisitas

Titik Eksentrik

a

∞

b,d,e

b

∞

d,e

c

∞

b,d e

d

∞

b, c

e

∞

b,d

f

∞

b,d e

Diperoleh rad ED(D) = min {∞, ∞, ∞, ∞, ∞}= ∞, diam ED(D) = maks {∞, ∞, ∞, ∞, ∞}= ∞ dan titik sentral ED(D) adalah a,b,c,d,e,dan f. Dari E

(D) pada gambar 2.3.7(c), diperoleh digraf eksentrisitas E

(D)


,

1, ∞, 2,2, ∞, ,

,

,

,

,

,

∞, 1, ∞, 1, ∞ ,

,

∞, 1, ∞, 1, ∞

,

,

,

, ,

,

,

,

,

,

,

∞ ,

∞, 1,1,2, ∞ ,

,

∞

∞, ∞, 1,1, ∞ ,

,

, , ,

,

,

,

,

,

∞ ,

, ,

,

,

,

,

,

∞ ,

, , ,

∞

,

,

,

,

, , ,

34

,

,

∞, 1, ∞, 1,1 Tabel 2.3.5 eksentrisitas E

,

,

,

,

,

,

∞

, ,

(D) dari Gambar 2.3.7

Titik

Eksentrisitas

Titik Eksentrik

a

∞

b,d,e

b

∞

d,e

c

∞

b,d e

d

∞

b, c

e

∞

b,d

f

∞

b,d e

Diperoleh rad (D) = min {∞, ∞, ∞, ∞, ∞}= ∞, diam (D) = maks {∞, ∞, ∞, ∞, ∞}= ∞ dan titik sentral D adalah a,b,c,d,e,dan f. Pada gambar 2.3.7 hanya digambar sampai dengan ,

, karena

, dst.

2.4 Graf Komplit Bipartit Graf Komplit ialah graf sederhana yang setiap titiknya mempunyai sisi ke semua titik lainnya. Graf komplit dengan dengan

buah titik dilambangkan

(Munir, 2001: 204).

Lemma 2.4.1 Untuk setiap graf G dengan

titik dan

sisi berlaku :

35

2

Bukti : Misalkan

adalah banyak sisi dan

adalah banyak titik dalam graf

Jelas untuk setiap sisi akan terhubung oleh 2 titik ∑

== 2 kali banyak sisi

2

Lemma 2.4.2 Jumlah sisi pada graf komplit yang terdiri dari

buah titik adalah

.

Bukti: Misalkan

adalah banyak sisi dalam graf komplit.

Ambil graf

dengan setiap pasang titik di

terdapat sebuah sisi yang

menghubungkan. Karena tiap titik dalam graf komplit selalu dihubungkan dengan titik lain melalui satu sisi, maka derajat tiap titik dalam sebuah graf komplit titik adalah

1.

dengan

36

Berdasarkan lemma 2.4.1, maka ∑

2 2 1

2 1 2

.

Akibatnya jumlah sisi pada graf komplit yang terdiri dari

buah titik adalah

. Contoh

Gambar 2.4.1 Graf komplit Pada gambar 2.4.1 untuk graf komplit

,

mempunyai 4 buah titik dan 6 buah

sisi. Sedangkan graf komplit

mempunyai 5 buah titik dan 10 buah sisi.

Kemudian untuk graf komplit

mempunyai 6 buah titik dan 15 buah sisi.

Graf G di bawah ini adalah graf bipartit, karena titik-titikya dapat , ,

dibagi menjadi a

, , ,

dan b

g

c

f e

d

37

Gambar 2.4.2 Graf bipartit Graf bagian

,

Tak Lengkap

yang himpunan titiknya dapat dipisah menjadi dua himpunan

dan

, sehingga setiap sisi pada

ke sebuah titik di

disebut graf bipartit dan dinyatakan sebagai

Dengan kata lain, setiap pasang titik di ,

, maka

,

.

bertetangga dengan semua titik di

disebut graf komplit bipartit (complete bipartite graph),

dilambangkan dengan Graf

menghubungkan sebuah titik di

,

(Munir, 2001: 206).

adalah bukan bipartisi jika himpunan titik tidak dapat dipartisi

menjadi dua himpunan bagian

dan

menghubungkan sebuah titik di

, maka setiap sisi pada

ke sebuah titik di

(Goodaire dan

Parmenter, 1998: 550). Contoh a

b

c

e

d

Gambar 2.4.3 Graf bipartisi komplit ,

Pada gambar 2.4.2 graf dipartisi menjadi titik di

,

,

dan

dihubungkan dengan sisi.

adalah graf komplit bipartit karena dapat , ,

sehingga setiap titik di

dan

38

2.5 Digraf Komplit Multipartit Digraf komplit dengan

-titik dinotasikan

yaitu digraf yang

setiap pasang titik-titiknya terhubung dengan sisi dua arah (bidirectional edge). Digraf n-partit (n-partite digraph) didefinisikan sebagai digraf di mana himpunan titik V(D) dapat dipisah menjadi

himpunan titik, yaitu V1(D),

V2(D), ... , Vn(D). Busur-busur pada digraf -partit terhubung dari titik-titik pada Vi(D) ke titik-titik pada himpunan titik selain Vi(D) atau adalah komplemen dari Vi(D). Untuk

, di mana

2 dinamakan bipartit, jika

| |= k dan | |= l, maka digraf bipartit tersebut dinotasikan dengan 3, dinamakan digraf tripartit yang dinotasikan

sedangkan untuk

Demikian seterusnya hingga dinotasikan

, , ,…,

,

, ,

.

dinamakan digraf multipartit yang

.

Contoh Digraf Multipartit

, , ,

Tak Komplit pada Gambar 2.5.1 dan

Digraf Multipartit Komplit terdapat pada Gambar 2.5.2.

39

G2

G

G4 G

Gambar 2.5.1 Digraf Multipartit

, , ,

Tak Komplit G

G2

G

G

Gambar 2.5.2 Digraf Komplit Multipartit

, , ,

BAB 3 METODE PENELITIAN

Langkah-langkah yang dilakukan dalam penelitian ini yaitu sebagai berikut.

1.

Penemuan Masalah Tahapan ini merupakan tahapan pertama dalam penelitian yaitu dengan pencarian ide atau gagasan materi eksentrisitas suatu titik, digraf eksentrik dari graf dan digraf. Kemudian menentukan permasalahan yaitu menentukan digraf eksentrik dari graf komplit bipartit dan digraf komplit multipartit untuk dikaji pada penelitian ini.

2.

Perumusan Masalah Tahap ini dimaksudkan untuk memperjelas permasalahan yang telah ditemukan yaitu sebagai berikut. 3.2.1 Bagaimana

langkah-langkah

eksentrik dari graf

mengkonstruksi

digraf

komplit bipartit dan digraf komplit

multipartit? 3.2.2 Bagaimana bentuk digraf eksentrik dari graf

komplit

bipartit? 3.2.3 Bagaimana bentuk digraf eksentrik dari digraf komplit multipartit ?

40

41

3.

Studi Pustaka Studi pustaka merupakan penelaah sumber pustaka relevan yang digunakan untuk mengumpulkan data maupun informasi yang diperlukan dalam penelitian ini. Studi pustaka diawali dengan mengumpulkan sumber pustaka yaitu berupa buku-buku maupun referensi yang menjadi dasar dalam penelitian ini. Setelah sumber pustaka terkumpul dilanjutkan dengan penelaahan isi sumber pustaka tersebut. Pada akhirnya sumber pustaka ini dijadikan landasan untuk melakukan penelitian ini.

4.

Analisis Pemecahan Masalah Pada tahap ini dilakukan analisa dan pemecahan masalah yaitu dengan langkah-langkah sebagai berikut. i. Mempelajari dan mengkaji tentang eksentrisitas titik, digraf eksentrik dari graf dan digraf eksentrik dari digraf. ii. Menentukan

langkah-langkah

eksentrik dari graf

untuk

mengkonstruksi

digraf

komplit bipartit dan digraf komplit

multipartit dengan menggunakan referensi yang ada serta bagaimana

membuktikan

teorema

yang

mendukung

keberadaannya. iii. Menggunakan kajian tentang digraf eksentrik untuk menemukan bagaimana bentuk digraf eksentrik dari graf komplit bipartit dan digraf komplit multipartit.

42

5.

Penarikan Simpulan Tahap ini merupakan tahap terakhir dari penelitian. Setelah menganalisis

dan memecahkan masalah berdasarkan studi pustaka dan pembahasannya kemudian dibuat sebagai simpulan sebagai jawaban dari permasalahan yang telah dirumuskan sebelumnya.

BAB 4 HASIL PENELITIAN DAN PEMBAHASAN Pada bab ini, akan kita bahas mengenai langkah-langkah untuk mengkonstruksi digraf eksentrik dari graf komplit bipartit dan digraf komplit multipartit, serta mencari bentuk digraf eksentrik dari graf komplit bipartit dan digraf komplit multipartit.

4.1 Langkah – Langkah Mengkonstruksi Digraf Eksentrik Pada BAB 2 telah didefinisikan tentang jarak, eksentrisitas titik, dan digraf eksentrik. Digraf

eksentrik pada graf

dinotasikan

didefinisikan

sebagai graf yang mempunyai himpunan titik yang sama dengan himpunan titik di atau

dimana arc menghubungkan titik

titik eksentrik dari

ke , jika

adalah

(Gafur, 2008:1).

Untuk menentukan digraf eksentrik dari suatu graf , langkah-langkahnya sebagai berikut. ,

4.1.1 Menentukan jarak setiap titik di

, dinotasikan dengan

dari titik

1,2, … ,

ke titik

,

1,2, … ,

ke semua titik

yaitu panjang lintasan terpendek

sehingga diperoleh juga eksentrisitas dari titik

,

1,2, … ,

dan

disebut titik eksentrik dari

dan titik eksentrisnya. Titik

43

jika jarak dari

, ke

44

sama dengan

,

dengan

,

1,2, … , . Titik eksentrik dari

mungkin tidak tunggal. 4.1.2 Membangun digraf

dengan himpunan titik ,

dan himpunan arc ,

1,2, … , ,

), dengan

eksentrik dari

,

,…,

1,2, … ,

, di mana

dan

adalah titik

.

,

Misalkan digraf D dengan himpunan titik ,

himpunan arc

,

,…,

,

,…,

dan

. Maka digraf eksentrik dari digraf D

dapat dikonstruksi dengan langkah-langkah sebagai berikut. ,

4.1.1 Menentukan jarak setiap titik , dinotasikan dengan

di

berarah dari titik

1,2, … ,

ke titik

,

1,2, … ,

, yaitu panjang lintasan terpendek

sehingga diperoleh eksentrisitas dari titik

,

1,2, … ,

dan


sama dengan

ke semua titik


dengan

,

,

jika jarak dari

, ke


mungkin tidak tunggal. 4.1.2 Membangun digraf


dan himpunan arc , .

)

1,2, … , ,

1,2, … ,

dan

,

,…,

, di mana

adalah titik eksentrik dari

45

4.2 Digraf Eksentrik dari Graf Komplit Bipartit Pada bagian ini akan dibahas tentang bentuk digraf eksentrik dari graf komplit bipartit. Teorema berikut ini akan digunakan untuk mengkonstruksi digraf eksentrik dari graf komplit bipartit. Misal graf komplit bipartit ,

,

dan himpunan sisi E

mempunyai himpunan titik

,…, , ,…, ,

,

untuk setiap

,

,…,

1,2,3, … ,

,

dan

,…,

,…,

1,2,3, … ,

.

dimana

Teorema 4.2.1 Eksentrisitas titik

pada graf komplit bipartit

2 untuk setiap

1,2,3, … ,

,

adalah sebagai berikut.

.

Bukti: Dari definisi graf komplit bipartit, jarak terjauh (maksimal lintasan terpendek) dari

untuk setiap

adalah semua titik di dari

1,2,3, … ,

adalah 2, dengan titik eksentriknya

kecuali dirinya sendiri, demikian juga jarak terjauh

, untuk setiap

1,

2, … ,

eksentriknya adalah semua titik di untuk setiap

di

1,2,3, … ,

di

adalah 2 dengan titik

kecuali dirinya sendiri. Jadi

.

Akibat a. Titik eksentrik pada graf komplit bipartit

,


2,

46

Titik eksentrik di

adalah

dari

. Titik eksentrik di 2, … ,

dengan

dari

, untuk , adalah

adalah

1,

, untuk setiap

1,2,3, … ,

, untuk setiap

di

, untuk setiap

di

, untuk ,

di

, untuk setiap

di

titik eksentrik dari adalah

dengan

.

b. Dari teorema 4.2.1, titik eksentrik dari 1,2,3, … ,

1,2,3, … ,

dan

1,

1,

2, … ,

dan

2, … , dan

.

Teorema 4.2.2 Digraf eksentrik dari graf komplit bipartit himpunan titik

,

,

untuk , untuk ,

,

,…, 1,2, … , 1

adalah digraf dengan

,

dan himpunan arc dengan ,2, … ,

dengan

Bukti: Titik eksentrik dari , untuk setiap

1,2,3, … ,

untuk ,

1,2,3, … ,

1,

2, … ,

2, … , ,

dan 1,

, untuk setiap

di

dan

1,2,3, … ,

sehingga ada arc dari

dan titik eksentrik dari adalah

di

di

ke

ke

yaitu

1,

yaitu

untuk

.

Jadi jelas bahwa himpunan titik

,

,

,…,

himpunan arc ,

di

, untuk setiap

, untuk setiap

sehingga ada arc dari 2, … ,

adalah

untuk , untuk ,

1,2, … , 1

dengan ,2, … ,

dengan

dan

47

Dari teorema 4.2.2 dapat ditarik kesimpulan bahwa digraf eksentrik dari graf komplit bipartit

adalah digraf komplemen

,

himpunan titik titik di

,

,

demikian juga di

,

,

dengan

dimana arcnya keluar ke semua

dengan jumlah arc

,

. Teorema 4.2.3 Misalkan

dengan

,

dengan

,

,

2, dapat diperoleh bentuk umum

,

2.

Bukti : Misalkan

,

,

dengan

himpunan titik dari graf dan Y, di mana

2 adalah suatu graf komplit bipartit, maka ,

,

dapat dipartisi menjadi dua himpunan bagian X ,…,

,

dan

,…,

. Berdasarkan

teorema 4.2.1 disebutkan bahwa jarak terjauh (maksimal lintasan terpendek) dari vi, untuk setiap i=1,2,3,…,m di X adalah 2 dengan titik eksentriknya adalah semua titik di X kecuali dirinya sendiri, demikian juga jarak terjauh dari wi , untuk setiap i=1,2,3,…,n di Y adalah 2 dengan titik eksentriknya adalah semua titik di Y kecuali dirinya sendiri. Maka eksentrisitas titik vi pada graf komplit bipartit

,

dengan

,

2 adalah e(vi)=2, untuk setiap

i=1,2,3,…,n dan e(wi)=2, untuk setiap i=1,2,3,…,m. Titik eksentrik dari vi di X adalah vj di X, untuk i=1,2,3…,m dan titik eksentrik dari wi di Y adalah wj di Y, untuk i=1,2,3…,n dan

dan

48

Dengan demikian himpunan titik di X membentuk digraf komplit dengan m titik, sedangkan himpunan titik di Y membentuk digraf komplit dengan n titik, sehingga digraf eksentrik dari graf komplit bipartit adalah

,

dengan

,

2

.

,

Berdasarkan pembuktian di atas bahwa bentuk umum digraf eksentrik dari graf komplit bipartit

,

dengan

,

2 adalah gabungan

dari digraf komplit Km dan Kn, atau dapat dituliskan dengan dengan

,

,

2.

Dengan menggunakan langkah - langkah mengkonstruksi digraf eksentrik pada bagian 4.1, akan dikonstruksi beberapa contoh digraf eksentrik dari graf komplit bipartit. a. Graf K2,2 Graf komplit bipartit K2,2 digambarkan sebagai berikut.

Gambar 4.2.1 Graf komplit bipartit K2,2 Dari gambar 4.2.1 diperoleh eksentrisitas sebagai berikut. , 2,1,1

,

,

,

2, ,

2,1,1

,

2,

. ,

,

,

, .

49

, 1,1,2

,

,

,

2, ,

1,1,2

,

. ,

,

,

,

2,

.

Tabel 4.2.1 Eksentrisitas dari Gambar 4.2.1 Titik

Eksentrisitas

Titik Eksentrik

2 2 2 2 Diperoleh rad (G) = diam (G) = 2. Sehingga dari gambar graf 4.2.1 diperoleh digraf eksentrik sebagai berikut.

Gambar 4.2.2 Digraf Eksentrik dari Graf Komplit Bipartit K2,2 Bentuk digraf eksentrik dari graf K2,2 adalah gabungan dari dua digraf komplit dengan titik sebanyak 2 atau dapat dituliskan

.

50

b. Graf K2,3 Graf komplit bipartit K2,3 digambarkan sebagai berikut.

Gambar 4.2.3 Graf komplit bipartit K2,3 Dari gambar 4.2.3 diperoleh eksentrisitas sebagai berikut. ,

,

2,1,1,1 ,

,

1,1,2,2

,

, .

,

,

,

,

,

, .

,

,

,

,

,

2, ,

1,1,2,2 ,

,

2,

1,1,2,2 ,

,

2,

2,1,1,1 ,

,

, ,

,

,

,

,

2, ,

, 2,

,

,

,

.

,

.

,

.

,

51

Tabel 4.2.2 eksentrisitas dari Gambar 4.2.3 Titik

Eksentrisitas

Titik Eksentrik

2 2 2

,

2

,

2

,

Diperoleh rad (G) = diam (G) = 2. Sehingga dari gambar graf 4.2.3 diperoleh digraf eksentrik sebagai berikut.

Gambar 4.2.4 Digraf Eksentrik dari Graf Komplit Bipartit K2,3 Bentuk digraf eksentrik dari graf K2,3 adalah gabungan dari digraf komplit dengan titik sebanyak 2 dan digraf komplit dengan titik sebanyak 3, atau dapat dituliskan

52

c. Graf K2,4 Graf komplit bipartit K2,4 digambarkan sebagai berikut.


,

2,1,1,1,1 ,

,

,

,

,

,

,

,

,

,

, .

,

,

,

,

,

,

2, ,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

. ,

, ,

2

,

,

2,

.

, ,

,

1,1,2,2,2

, ,

2,

1,1,2,2,2 ,

,

. ,

,

1,1,2,2,2 ,

,

2,

1,1,2,2,2 ,

,

2,

2,1,1,1,1 ,

,

,

,

.

, ,

,

.

53

Tabel 4.3 eksentrisitas dari Gambar 4.2.5 Titik

Eksentrisitas

Titik Eksentrik

2 2 2

,

,

2

,

,

2

,

,

2

,

,



54

d. Graf K2,5 Graf komplit bipartit K2,5 digambarkan sebagai berikut.


,

,

,

,

,

,

,

,

,

,

,

, 2,1,1,1,1,1

2,

,

,

,

. ,

,

,

,

,

, 2,1,1,1,1,1

2,

,

,

,

. ,

,

,

,

,

,

,

, 1,1,2,2,2,2

2,

,

,

, ,

,

,

,

,

,

,

, ,

. ,

, 1,1,2,2,2,2

2, ,

,

,

, ,

,

,

,

,

, ,

, ,

. ,

55

1,1,2,2,2,2

2, ,

,

, ,

,

,

,

,

,

,

,

. ,

,

, 1,1,2,2,2,2 ,

2, ,

, ,

,

,

,

,

,

,

, ,

. ,

, 1,1,2,2,2,2

2,

,

,

,

.


Eksentrisitas

Titik Eksentrik

2 2 2

,

,

,

2

,

,

,

2

,

,

,

2

,

,

,

2

,

,

,


56

Gambar 4.2.8 Digraf Eksentrik dari Graf Komplit Bipartit K2,5 Bentuk digraf eksentrik dari graf K2,5 adalah gabungan dari digraf komplit dengan titik sebanyak 2 dan digraf komplit dengan titik sebanyak 5, atau dapat dituliskan e. Graf K3,2 Graf komplit bipartit K3,2 digambarkan sebagai berikut.


,

2,2,1,1 ,

2,2,1,1

,

,

,

,

2, ,

2,2,1,1 ,

,

,

,

,

,

2,

,

,

,

,

.

,

.

,

2, ,

,

, ,

.

57

, 1,1,1,2 ,

,

,

,

,

,

,

2, ,

1,1,1,2

. ,

,

,

2,

, .


Eksentrisitas

Titik Eksentrik

2

,

2

,

2

,

2 2 Diperoleh rad (G) = diam (G) = 2. Sehingga dari gambar graf 4.2.9 diperoleh digraf eksentrik sebagai berikut.


58

Berdasarkan Teorema 4.2.3 yang menyatakan bahwa jika komplit bipartit dengan dengan ,

,

,

,

adalah graf

2, dapat diperoleh bentuk umum

,

2. Maka dengan mudah dapat diperoleh digraf eksentrik

tanpa harus mengikuti langkah-langkah mengkontruksi digraf eksentrik pada

bagian 4.2.1 f. Graf K3,3 Graf komplit bipartit K3,3 digambarkan sebagai berikut.

Gambar 4.2.11 Graf komplit bipartit K3,3 Sehingga dari gambar graf 4.2.11 diperoleh digraf eksentrik sebagai berikut.


.

59

g. Graf K3,4 Graf komplit bipartit K3,4 digambarkan sebagai berikut.



.

60

h. Graf K3,5 Graf komplit bipartit K3,5 digambarkan sebagai berikut.



.

61

4.3 Digraf Eksentrik dari Digraf Komplit Multipartit Pada bagian ini akan dibahas tentang bentuk digraf eksentrik dari digraf komplit multipartit. Teorema berikut ini akan digunakan untuk mengkonstruksi digraf eksentrik dari digraf komplit multipartit. Misal digraf komplit multipartit , , , , , , , , , ,

mempunyai himpunan titik

, ,

, ,

,

,

,

,

dan himpunan busur ,

,…, , ,…, ,

, , ,…, ,

…, , , ,

,

…, …,

, ,

,…, ,

,…, ,

,…, , ,

, , ,…, ,

,

,

,…, ,…,

,

,…,

,

,…, ,

, ,…, ,…, ,…,

,

,… ,

, , ,… ,

, , …,

,… ,

dengan busur

ke

: dengan

1,2,

, dan

1,2,

, di mana

adalah busur yang menghubungkan titik ke busur

ke

dan titik

. ke

: dengan

1,

2,

,

dan

1,2,

,

,

,

62

busur

ke

: 1,

dengan 1,2,

dan busur

ke

busur

1, ke

,

1,

2,

2, … ,

,

: 1,

dengan 1,

dan

busur

ke

2,

2, … ,

,

: 1,

dengan 1,

dan

busur

2,

: dengan

dan

,

ke

2,

,

2,

,

2,

,

: 1,

dengan dan 1,

,

Contoh pada digraf komplit multipartit

2,

, ,

63

Gambar 4.3.1 Digraf Komplit Multipartit

, ,

mempunyai himpunan titik , ,

, ,

, ,

dan himpunan busur

,

, , , ,

, ,

, , ,

, , ,

,

, , ,

dengan busur

ke

: dengan

1,2 dan

1,2 di mana

adalah busur yang menghubungkan titik ke busur

sehingga ke

ke

,

,

dan titik ,

: dengan

2

1, 2

2, 2

3

3,4,5 dan

1, 2 di mana

64

adalah busur yang menghubungkan titik ke

sehingga

,

,

,

busur

ke

dan titik ,

,

.

: dengan

2

dan

ke

1, 2

2

2+1, 2+2, 2+3 = 3,4,5 3,4 di mana

adalah busur yang menghubungkan titik ke

sehingga

,

,

,

ke

dan titik ,

,

.

Teorema 4.3.1 Eksentrisitas titik

pada digraf komplit multipartit

, , ,

adalah sebagai

berikut. 2 untuk setiap

1,2,

,

Bukti: Dari definisi digraf komplit multipartit, jarak terjauh (maksimal lintasan terpendek) dari

untuk setiap

eksentriknya adalah semua titik di

1,2,

,

di


kecuali dirinya sendiri. Selanjutnya

jarak terjauh (maksimal lintasan terpendek) dari ,

untuk setiap

1,

2,

di

kecuali dirinya sendiri dan demikian juga seterusnya jarak terjauh

di

adalah 2 dengan titik eksentriknya adalah semua titik

(maksimal lintasan terpendek) dari 1,

2,

,

untuk setiap di


65

eksentriknya adalah semua titik di 1,2,

untuk setiap

kecuali dirinya sendiri. Jadi

,

2

.

Akibat a. Dari hasil perhitungan mencari jarak setiap digraf komplit multipartit , ,…,

dapat dirumuskan sebagai berikut.

,

1

1,2,

,

,

1

1,2,

,

1,

2,

1,

,

1

1,2,

2,

,

1, ,

1

2,

1,

2,

,

1,

,

1

1,

2,

2,

,

,

1,

,

2,

1 1,

2,

1,

2,

dan ,

2

,

1,2,

,

,

, ,

,

,

,

66

,

2

,

,

2

,

,

2

,

1,

2,

,

1,

2,

,

1, 2,

,

b. Dari pencarian titik eksentrik pada digraf eksentrik pada digraf komplit multipartit


, , ,

Titik eksentrik di Titik 2,

eksentrik

dari di

adalah

untuk ,

1,2,

dari

adalah

untuk

adalah

dari

1,

1,

2,

untuk ,

,

Dari teorema 3.4.1 titik eksentrik dari adalah

di di

2,

titik eksentrik dari , 1,

1,2,

untuk setiap 1,

untuk

1,

2,

,

,

Titik eksentrik di

dari

,

,

2,

dimana di

,

dimana

,

adalah

2,

,

1,2,

untuk

,

. Titik eksentrik di

untuk setiap

. Demikian seterusnya sehingga 1,

untuk adalah

di

di

untuk setiap dimana

.

67

Ilustrasi untuk mencari titik

pada digraf komplit multipatit

, ,…,

adalah sebagai berikut. ,

1. Menentukan jarak setiap titik , dinotasikan dengan berarah dari titik

1,2, … ,

,

ke titik

1,2, … ,

, yaitu panjang lintasan terpendek

sehingga diperoleh eksentrisitas dari titik

,

1,2, … ,

dan


sama dengan

ke semua titik di

,


,

dengan

,

jika jarak dari


mungkin tidak tunggal. Contoh : a. Digraf

,

Digraf komplit multipartit

digambarkan sebagai berikut.

,

Gambar 4.3.2 Digraf komplit mutipartit

,


,

ke

,

,

,

,

,

68

2,1,1,1 ,

2, ,

,

2,1,1,1 ,

,

,

,

, .

,

,

,

,

,

2, ,

1,1,2,2 ,

,

2,

1,1,2,2 ,

.

, ,

,

,

,

,

2, ,

1,1,2,2

,

,

,

,

.

,

.

,

.

,

2,

Tabel 4.3.1 eksentrisitas dari Digraf pada Gambar 4.3.2 Titik

Eksentrisitas

Titik Eksentrik

2 2 2

,

2

,

2

,


Gambar 4.3.3 Digraf Eksentrik dari Digraf Komplit Multipartit

,

69

b. Digraf

, ,

Digraf komplit mutipartit

, ,

digambarkan sebagai berikut.

Gambar 4.3.4 Digraf komplit mutipartit

, ,


,

,

2,1,1,1,1,1

2,

,

,

,

2,1,1,1,1,1

2,

,

,

,

,

,

,

,

,

,

,

,

, . ,

,

,

,

,

,

,

. ,

,

,

,

,

,

,

, 1,1,2,1,1,1 , ,

,

2, ,

. ,

,

,

,

,

,

,

70

1,1,2,1,1,1 ,

2,

,

,

. ,

,

,

,

,

,

,

, 1,1,1,1,2,2

2,

,

,

,

, ,

,

,

,

,

. ,

,

, 1,1,1,1,2,2 ,

2,

,

,

, ,

,

,

,

,

.

,

,

, 1,1,1,1,2,2

2,

,


Eksentrisitas

Titik Eksentrik

2 2 2 2 2

,

2

,

2

,

Diperoleh rad (G) = diam (G) = 2.

,

.

71

Sehingga dari gambar digraf 4.3.4 diperoleh digraf eksentrik sebagai berikut. V

W

X Gambar 4.3.5 Digraf Eksentrik dari Graf Komplit Mutipartit Setelah eksentrisitas titik multipartit

, , ,

, ,

dan titik eksentrik pada digraf komplit

diperoleh, selanjutnya diperoleh teorema berikut.

Teorema 3.4.2 Digraf eksentrik iterasi kedua pada digraf komplit multipartit adalah digraf komplit multipartit

, , ,

, , ,

itu sendiri.

Bukti: Dari akibat kedua pada digraf eksentrik iterasi pertama, titik eksentrik dari 1,2,

di dimana dari

,

adalah

di

sehingga ada busur dari di 1,

1,

untuk 2,

,

2,

dimana

ke ,

1,2,

untuk setiap yaitu adalah

,

, Titik eksentrik di

untuk setiap

sehingga ada busur dari

ke

72

yaitu

. Demikian seterusnya sehingga titik eksentrik dari 1,

adalah 2,

di

2,

1,

dimana

yaitu

untuk

,

untuk setiap

,

di

sehingga ada busur dari

ke

.

Sedangkan

pada

iterasi

kedua

karena

tidak

ada

busur

yang

menghubungkan antar setiap himpunan titik pada digraf eksentrik iterasi pertama maka jarak terjauh (maksimal lintasan terpendek) dari titik ke setiap titik yang berbeda himpunan titiknya adalah ∞ sehingga titik eksentrik

di

,

1,2,

, titik eksentrik dari

,

di

adalah semua titik yang tidak berada di

semua titik yang tidak berada di eksentrik dari 2,

di

1,

untuk

2,

adalah

, demikian seterusnya sehingga titik 1,

untuk

,

,

adalah semua titik yang tidak berada di

.

Dari teorema 4.3.2 dapat disimpulkan bahwa digraf eksentrik iterasi kedua pada digraf komplit multipartit , , ,

, , ,

adalah digraf komplit multipartit

itu sendiri atau dengan kata lain

=

, , ,

adalah digraf komplit multipartit maka

Jadi D

, , ,

.

Dari gambar 4.3.3(digraf eksentrik dari digraf pada gambar 4.3.2) diperoleh eksentrisitas sebagai berikut. ,

,

,

1, ∞, ∞, ∞

∞,

,

,

,

,

,

,

, ,

,

,

,

,

,

.

73

1, ∞, ∞, ∞ ,

∞, ,

,

∞, ∞, 1,1

,

,

,

,

∞, ∞, 1,1 ,

,

,

,

,

,

,

,

.

,

∞,

Eksentrisitas

.

,

,

Tabel 4.3.3 eksentrisitas dari Digraf pada Gambar 4.3.3 Titik

,

Titik Eksentrik

∞

,

,

∞

,

,

∞

,

∞

,

∞

,

.

,

∞, ,

∞, ∞, 1,1

,

,

,

∞,

,

,

.

74

Sehingga dari gambar graf 4.3.3 diperoleh digraf eksentrik (iterasi kedua dari digraf pada gambar 4.3.2) sebagai berikut.

Gambar 4.3.6 Digraf Eksentrik iterasi kedua dari Digraf Komplit Multipartit

,

Selanjutnya dari gambar 4.3.5 (digraf eksentrik dari digraf pada gambar 4.3.4) diperoleh eksentrisitas sebagai berikut. ,

,

,

,

,

,

,

,

,

,

,

,

, 1, ∞, ∞, ∞, ∞, ∞

∞, ,

,

, ,

,

,

,

, ,

,

, ,

. ,

75

1, ∞, ∞, ∞, ∞, ∞

∞, ,

,

,

,

,

,

,

,

,

,

,

.

,

,

,

,

,

, ∞, ∞, 1, ∞, ∞, ∞

∞, ,

,

,

,

,

,

,

,

,

,

.

,

,

, ∞, ∞, 1, ∞, ∞, ∞

∞, ,

,

,

,

,

,

,

,

,

,

.

,

,

,

,

,

,

,

, ∞, ∞, ∞, ∞, 1,1

∞, ,

,

,

,

,

,

,

,

,

,

, ∞, ∞, ∞, ∞, 1,1

∞, ,

,

,

.

76

,

,

,

,

,

,

,

,

,

, ∞, ∞, ∞, ∞, 1,1

∞, ,


Eksentrisitas

Titik Eksentrik

∞

,

,

,

,

∞

,

,

,

,

∞

,

,

,

,

∞

,

,

,

,

∞

,

,

,

∞

,

,

,

∞

,

,

,

,

,

.

,

77

Sehingga dari gambar graf 4.3.5 diperoleh digraf eksentrik (iterasi kedua dari digraf pada gambar 4.3.4) sebagai berikut.

Gambar 4.3.7 Digraf Eksentrik iterasi kedua dari Digraf pada Gbr. 4.3.4

BAB 5 SIMPULAN DAN SARAN 5.1 Simpulan Berdasarkan pembahasan yang telah dilakukan, maka kesimpulan yang dapat diambil mengenai digraf eksentrik dari graf komplit bipartit dan digraf komplit multipartit adalah sebagai berikut. 5.1.1 Langkah-langkah mengkonstruksi digraf eksentrik dari suatu graf adalah sebagai berikut. ,

(1) Menentukan jarak setiap titik , dinotasikan dengan

titik di

terpendek dari titik

ke titik ,

dari titik , jika jarak dari

,

ke

dan

(2) Membangun digraf

disebut titik eksentrik dari ,

dengan himpunan titik

, )

titik eksentrik dari

,

dengan

mungkin tidak tunggal, dan

dan himpunan arc mana

, yaitu panjang lintasan


sama dengan


ke semua

sehingga diperoleh eksentrisitas

1,2, … ,

1,2, … ,

1,2, … ,

1,2, … , , .

78

, 1,2, … ,

,

,…,

dan

, di adalah

79

5.1.2 Langkah-langkah mengkonstruksi digraf eksentrik dari suatu digraf adalah sebagai berikut. ,

(1) Menentukan jarak setiap titik , dinotasikan dengan

titik di

berarah terpendek dari titik eksentrisitas

dari

,

dengan

sehingga diperoleh

, ,

eksentrisnya. Titik

1,2, … ,

1,2, … , ke

,

Titik

1,2, … , .

dan

dan

jika jarak dari ,

ke semua

, yaitu panjang lintasan

ke titik

titik

eksentrik dari

1,2, … ,

titik

disebut titik sama dengan eksentrik

dari

mungkin tidak tunggal, dan (2) Membangun digraf


dan himpunan arc ,

1,2, … , ,

)

eksentrik dari

1,2, … ,

,

,…,

dan

, di mana adalah titik

.

5.1.3 Bentuk digraf eksentrik dari graf komplit bipartit dinotasikan dengan dan umum

,

,

2 adalah gabungan dari digraf komplit dengan m titik

titik dengan sisi berarah bolak-balik atau diperoleh bentuk ,

dengan

,

2.

5.1.4 Digraf eksentrik iterasi kedua pada digraf komplit multipartit , , ,

adalah digraf komplit multipartit

, , ,

itu sendiri.

80

5.2 Saran 1. Berkaitan dengan hasil penelitian, ada beberapa hal yang perlu mendapat perhatian yaitu penelitian ini hanya mengkaji digraf eksentrik dari graf komplit bipartit dan digraf komplit multipartit. Untuk itu perlu penelitian lebih lanjut tentang digraf eksentrik iterasi pertama dari digraf komplit multipartit dan pada klasifikasi graf maupun digraf lainnya.

81

DAFTAR PUSTAKA Budayasa, I Ketut. 2007. Teori Graph dan Aplikasinya. Surabaya: Unesa University Press. Chartrand, G. and Lesniak, 1996, Graphs & Digraphs, 3rd edition. London: Chapman & Hill. Gimbert, J. et al., 2006. Characterization of Eccentric Digraphs. Tersedia di: http://www.lingkinghub.elsevier.com/retrieve/pii/S0012365X050059 11 [14 Agustus 2009]. Goodaire, Edgar G., 2003. Discrete Mathematics with Graph Theory. New Delhi: Prentice Hall of India Private Limited. J. Boland dan M. Miller, 2001. The Eccentric Digraph of a Digraph. Tersedia di : www.etsu.edu/math/boland/papers/mirka.ps [13 September 2009] Kumalasari, Retno Catur. 2008. Eksentrik Digraf pada Graf sikel, Digraf Komplit dan Digraf Komplit Multipartit. Jurnal Matematika FMIPA UNDIP. Semarang. Munir, Rinaldi. 2001. Buku Teks Ilmu Komputer Matematika Diskrit. Bandung: Informatika Bandung. Setyaningrum, Vera Widi. 2010. Eksentrik Digraf dari Digraf Komplit Simetri dan Siklus Berarah. Skripsi Matematika UNNES. Semarang Sutarno, Heri. 2003. Matematika Diskrit. Bandung: JICA. Weisstein, Eric W, 2009. Graph. Tersedia di : http://mathworld.wolfram.com [13 September 2009] Wilson. Robin J dan Walkins, John J. 1990. Graphs An Introductory Approach: A first Course in Discrete Mathematic. New York: John Wiley & Sons, Inc.

DIGRAF EKSENTRIK DARI GRAF KOMPLIT BIPARTIT DAN DIGRAF KOMPLIT MULTIPARTIT

Recommend Documents