LITERATUR UNTUK TEORI GRAF DALAM ILMU MATEMATIKA

LITERATUR UNTUK TEORI GRAF

1.       Latar Belakang 

Teori graf merupakan pokok bahasan yang sudah sangat tua usianya namun memiliki

banyak sekali terapan sampai saat ini. Graf dipakai untuk merepresentasikan objek –

objek diskrit dan hubungan antara objek – objek tersebut. Representasi visual dari graf

adalah dengan menyatakan objek – objek sebagai sebuah titik atau bulatan yang juga

sering disebut dengan verteks dan biasanya diberi lambang v, sedangkan hubungan

antara objek – objek tersebut dilambangkan dengan sebuah garis atau rusuk yang juga

sering disebut dengan edge dan biasa diberi lambang e.

Ada banyak jenis graf yang dapat digolongkan berdasarkan jenis rusuknya,

ataupun dapat juga digolongkan berdasarkan ada atau tidaknya arah pada rusuk dari

graf tersebut. Berdasarkan jenis rusuknya maka graf dibagi kepada 2 jenis yaitu graf

sederhana (simple graph) dan graf tak sederhana (unsimple graph). Adapun graf

sederhana adalah graf yang tidak mengandung gelang (loop) maupun rusuk ganda

(multiple edge). Sedangkan graf tak sederhana adalah graf yang mengandung rusuk

ganda dan dapat saja juga mengandung gelang. Adapun graf tak sederhana dapat

dibagi 2 yaitu graf ganda (multi graph) dan graf semu (pseudo graph). Graf ganda

adalah graf yang memiliki rusuk ganda tanpa memiliki gelang. Sedangkan graf semu

adalah graf yang memiliki gelang dan bisa juga sekalian memiliki rusuk ganda atau

hanya memiliki gelang tanpa rusuk ganda. Selanjutnya berdasarkan ada atau tidaknya

arah pada rusuk, maka graf dapat terbagi 2 yaitu graf tak berarah (undirected graph)

dan graf berarah (directed graph) yang biasa disebut juga digraf. Graf tak berarah

adalah graf yang setiap rusuknya tidak memiliki arah sehingga setiap rusuknya hanya

digambarkan berupa garis saja tanpa ada penunjuk arah. Sedangkan graf berarah

adalah graf yang setiap rusuknya memiliki arah tertentu sehingga rusuk – rusuknya

digambarkan berupa garis beserta tanda panah sebagai penunjuk arah tertentu.

2.       Pembatasan Masalah 

Permasalahan yang dibahas dalam penulisan ini adalah untuk sembarang graf yaitu

untuk semua model graf tanpa terkecuali baik dari graf sederhana maupun graf tak

sederhana.

3.       Tujuan Penelitian

Penelitian ini bertujuan untuk mencari dan menemukan suatu rumus yang tepat untuk mencari dan menghitung banyaknya jumlah seluruh subgraf dari graf.

4.       Manfaat Penelitian

Karena penelitian ini bertujuan untuk mencari suatu rumus yang tepat untuk

menghitung banyaknya subgraf dari graf sembarang, maka penulis mengharapkan

rumus yang berhasil ditemukan ini nantinya dapat berguna untuk menemukan dan

memetakan semua subgraf dari graf sembarang sehingga pada akhirnya akan lebih

memudahkan dalam penghitungan jumlah subgraf dari graf sembarang. Selain itu penulis juga berharap bahwa pada masa mendatang rumus ini dapat

dipakai untuk melahirkan rumus – rumus baru lainnya yang berguna untuk

menemukan suatu pola tertentu dari subgraf – subgraf yang bersifat khusus dari suatu

graf dan akhirnya dapat juga ditemukan suatu rumus untuk menghitung jumlah

subgraf – subgraf khusus tersebut. Misalkan untuk menghitung banyaknya subgraf

yang berbentuk graf terhubung (connected graph) dari suatu graf, subgraf yang

berbentuk graf teratur (regular graph), subgraf yang berbentuk bipartit (bipartite

graph), subgraf – subgraf yang isomorfik, subgraf – subgraf yang planar, maupun juga

untuk menemukan rumus untuk menghitung banyaknya subgraf – subgraf yang

memiliki lintasan Euler maupun lintasan Hamilton, dan lain – lain.

5.       Metodologi Penelitian

Penelitian ini merupakan penelitian literatur atau kepustakaan. Penelitian ini dilakukan dengan pertama kali melakukan kajian terhadap buku – buku mengenai teori graf maupun buku – buku matematika diskrit yang di dalamnya memuat topik – topik mengenai kombinatorika dan teori graf. Secara garis besar metodologi penelitian ini adalah sebagai berikut :

1. Mengumpulkan berbagai literatur yang berhubungan dengan

kombinatorika dan teori graf.

2. Mempelajari literatur – literatur yang telah dikumpulkan.

3. Mengamati dan meneliti berbagai macam contoh graf kemudian membuat

subgraf – subgraf yang memungkinkan dari graf – graf tersebut.

4. Menyusun dan mengelompokkan subgraf – subgraf secara baik dan teratur

dengan tujuan untuk mencari dan menemukan suatu pola tertentu

mengenai pembentukan subgraf ini.

5. Membuat dugaan – dugaan dari pola – pola yang telah didapat untuk

selanjutnya dijadikan acuan dasar dalam membuat rumus yang tepat untuk

menghitung jumlah subgraf dari suatu graf.