BAB I
PENDAHULUAN
1.1 Latar Belakang
Matematika itu pada dasarnya berkaitan dengan pekerjaan menghitung, sehingga tidak salah jika kemudian ada yang menyebut matematika adalah ilmu hitung atau ilmu al-hisab. Dalam urusan hitung-menghitung ini, Allah adalah rajanya. Allah sangat cepat dalam menghitung dan sangat teliti (Abdusysyakir, 2007: 83). Hal tersebut telah dijelaskan dalam Al-Qur’an surat Ali Imran ayat 199 yang berbunyi:
Alam semesta memuat bentuk-bentuk dan konsep matematika, meskipun alam semesta tercipta sebelum matematika itu ada. Alam semesta serta segala isinya diciptakan Allah dengan ukuran-ukuran yang cermat dan teliti, dengan perhitungan-perhitungan yang mapan dan dengan rumus-rumus serta persamaan yang seimbang dan rapi (Abdusysyakir, 2007: 79).
Dalam kehidupan sehari-hari banyak permasalahan yang memerlukan pemecahan. Seiring dengan bantuan matematika permasalahan tesebut menjadi lebih mudah dipahami, lebih mudah dipecahkan atau bahkan dapat ditunjukkan bahwa suatu persoalan tidak mempunyai penyelesaian. Untuk keperluan tersebut, perlu dicari pokok permasalahannya dan kemudian dibuat rumusan atau model matematikanya.
Diantara cabang matematika yang banyak manfaatnya untuk kehidupan sehari-hari adalah teori graf. Dengan menggunakan rumusan atau model teori graf yang tepat, suatu permasalahan menjadi semakin jelas, sehingga mudah menganalisisnya. Permasalahan yang dirumuskan dengan teori graf dibuat sederhana, yaitu diambil aspek-aspek lainnya.
Graf G adalah pasangan himpunan (V, E) dengan V adalah himpunan tidak kosong dan berhingga dari objek-objek yang disebut sebagai titik dan E adalah himpunan (mungkin kosong) pasangan tak berurutan dari titik-titik berbeda di V yang disebut sebagai sisi. Himpunan titik di G dinotasikan dengan V(G) dan himpunan sisi dinotasikan dengan E(G) (Chartrand dan Lesniak, 1986: 4).
Graf komplit (complete graph) adalah graf yang setiap dua titik yang berbeda saling terhubung langsung. Graf komplit dengan n titik dinotasikan sebagai Kn (Wilson dan Watkins, 1990: 36). Graf bipartisi (bipartite graph) adalah graf yang himpunan titiknya dapat dipartisi menjadi himpunan M dan N sedemikian sehingga setiap sisi graf menghubungkan titik di M ke titik di N. Graf bipartisi komplit adalah graf bipartisi yang setiap titik di partisi M dihubungkan dengan tepat satu sisi ke setiap titik di partisi N. Graf bipartisi komplit dengan m titik pada M dan n titik pada N, dilambangkan dengan Km,n dan jumlah sisi pada graf bipartisi komplit adalah mn (Wilson dan Watkins, 1990: 38).
Sebuah titik dan sisi dikatakan saling cover pada graf G jika titik dan sisi tersebut incident pada G. Titik cover di G merupakan himpunan dari titik-titik yang mengcover semua sisi di G dan sisi cover pada graf G (tanpa titik terisolasi) merupakan himpunan sisi-sisi yang mengcover semua titik di G. Kardinalitas minimum titik cover pada graf G disebut bilangan cover titik (vertex covering number) dan dilambangkan dengan α(G). Sedangkan kardinalitas minimum sisi cover pada graf G disebut bilangan cover sisi (edge covering number) dan dilambangkan dengan α1(G) (Chartrand dan Lesniak, 1986: 243).
Hal yang menarik untuk dikaji mengenai himpunan cover adalah penentuan α dan α1. Sejauh ini penelitian tentang penentuan α dan α1 masih jarang dilakukan. Penelitian yang mirip adalah penentuan β dan β1 yang dilakukan oleh Denok Sanggrahati (2009). Oleh karena itu, penulis ingin mengkaji tentang himpunan cover titik dan himpunan cover sisi pada graf komplit Kn, graf bipartisi komplit Kn,n dan graf bipartisi komplit Km,n. Dalam pembahasan ini difokuskan pada penentuan bilangan cover titik dan cover sisi.
Dalam penentuan α dan α1 penulis yakin akan menemukan rumusnya, karena segala sesuatu itu pasti ada qadarnya (ketentuannya), ada aturan dan ada rumusnya. Hal tersebut terdapat dalam Al-Qur’an surat Al-Furqaan ayat 2 yang berbunyi:
Berdasarkan uraian tersebut maka penulis tertarik mengambil judul pada skripsi ini yaitu “ Menentukan Bilangan Cover Titik Dan Cover Sisi Pada Graf Komplit Kn, Graf Bipartisi Komplit Kn,n dan Graf Bipartisi Komplit Km,n dengan m, n _ _”.
1.2 Rumusan Masalah
Berdasarkan latar belakang tersebut, maka rumusan masalah dalam penulisan skripsi ini adalah:
1. Bagaimana cara menentukan bilangan cover titik dan cover sisi pada graf komplit Kn dengan n _ _ ?
2. Bagaimana cara menentukan bilangan cover titik dan cover sisi pada graf bipartisi komplit Kn,n dengan n _ _?
3. Bagaimana cara menentukan bilangan cover titik dan cover sisi pada graf bipartisi komplit Km,n dengan m, n _ _ dan m _ n?
1.3 Tujuan
Berdasarkan rumusan masalah di atas, maka tujuan penulisan skripsi ini
adalah:
1. Untuk mengetahui cara menentukan bilangan cover titik dan cover sisi pada graf komplit Kn dengan n _ _.
2. Untuk mengetahui cara menentukan bilangan cover titik dan cover sisi pada graf bipartisi komplit Kn,n dengan n _ _.
3. Untuk mengetahui cara menentukan bilangan cover titik dan cover sisi pada graf bipartisi komplit Km,n dengan m, n _ _ dan m _ n.
1.4 Manfaat Penulisan
a. Bagi penulis
Dengan penulisan ini, diharapkan dapat menambah wawasan dan pengetahuan tentang himpunan cover titik dan himpunan cover sisi pada graf komplit dan graf bipartisi komplit dan selanjutnya dapat digunakan sebagai sarana untuk mengembangkan pengetahuan tentang ilmu yang diperoleh selama mengikuti perkuliahan khususnya yang berkaitan dengan graf.
b. Bagi Pembaca
Sebagai bahan untuk menambah wawasan pengetahuan tentang himpunan cover titik dan himpunan cover sisi pada graf komplit dan graf bipartisi komplit.
c. Bagi Lembaga
Dapat digunakan sebagai tambahan bahan pustaka, tambahan sarana pembelajaran dan bahan pengembangan ilmu pengetahuan khususnya ilmu matematika yang berkaitan dengan teori graf
1.5 Metode Penelitian
Metode yang digunakan dalam penelitian ini adalah metode penelitian kepustakaan (library research) atau kajian pustaka, yakni melakukan penelitian untuk memperoleh data-data dan informasi-informasi serta objek yang digunakan dalam pembahasan masalah tersebut. Studi kepustakaan merupakan penampilan argumentasi penalaran keilmuan untuk memaparkan hasil olah pikir mengenai suatu permasalahan atau topik kajian kepustakaan yang dibahas dalam penelitian ini.
Adapun langkah-langkah yang digunakan oleh peneliti dalam membahas penelitian ini adalah sebagai berikut:
a. Menggambar beberapa contoh graf komplit dan graf bipartisi komplit.
b. Mencari himpunan cover titik dan himpunan cover sisi pada beberapa contoh graf komplit dan graf bipartisi komplit.
c. Menentukan bilangan cover titik dan cover sisi dengan menghitung kardinalitas minimum dari himpunan cover titik dan himpunan cover sisi pada beberapa contoh graf komplit dan graf bipartisi komplit.
d. Mencari pola dari bilangan cover titik dan cover sisi pada graf komplit dan graf bipartisi komplit. Pola tersebut kemudian dirumuskan sebagai konjektur dan dibuktikan kebenarannya.
