Teori graf Dan Aplikasinya

Pesatnya perkembangan ilmu pengetahuan dan teknologi membuat matematika menjadi sangat penting artinya. Karena perkembangan ilmu pengetahuan dan teknologi tidak lepas dari peranan matematika. Hampir dapat dipastikan bahwa setiap bagian dari ilmu dan teknologi baik dalam unsur kajian umum ilmu murni maupun terapannya memerlukan peranan matematika sebagai ilmu bantunya. Matematika digunakan sebagai alat penting di berbagai bidang, termasuk ilmu alam, teknik, kedokteran/medis, ilmu sosial seperti ekonomi, dan psikologi. Matematika terdiri dari beberapa cabang ilmu misalnya Aljabar, Geometri, Statistika, Probabilitas, Matematika Aplikasi, Matematika Komputasi, Matematika Ekonomi, Matematika Diskrit, Sain Komputer dan lain sebagainya. Cabang matematika terkini terkait dengan sain komputer yang cukup terkenal adalah teori graf.

contoh graph roda

Teori graf meruapakan teori lama yang hingga saat ini semakin banyak ditemukan aplikasinya di sekitar kita. Ide dasarnya diperkenalkan pertama kali pada abad ke-18 oleh matematikawan Swiss, Leonhard Euler. Pada waktu itu, ia menggunakan graf untuk menyelesaikan masalah jembatan Konigsberg. Teori graf merupakan pokok bahasan yang relatif muda namun memiliki banyak terapan yang sangat luas. Contohnya optimasi jaringan telepon, jaringan komputer, jaringan listrik, model papan sirkuit, model struktur ikatan kimia dan lain-lain.

Graf digunakan dalam kehidupan sehari-hari untuk mendeskripsikan model persoalan dan menggambarkannya secara konkret dan jelas, mempresentasikan objek-objek diskrit dan hubungan antara objek tersebut. Inti dari cara pengaplikasian graf ini adalah bagaimana kita bisa membaca permasalahan, kemudian mendefinisikan apa yang akan menjadi objek diskrit yang kemudian akan menjadi simpul-simpul dari graf yang akan kita bangun untuk menggambarkan permasalahan yang kita hadapi tadi, apabila telah kita dapatkan simpul simpul maka akan mudah bagi kita untuk membangun graf dengan memberi sisi pada simpul-simpul yang saling berhubungan. Representasi visual dari graf adalah dengan menyatakan objek sebagai noktah, bulatan atau titik (verteks), sedangkan hubungan antara objek tersebut dinyatakan dengan garis atau sisi (edge).

Salah satu kajian yang menarik dalam graf adalah pelabelan graf yang pertama kali diperkenalkan oleh Sedláček (1964), kemudian Stewart (1966), Kotzig dan Rosa (1970). Sejak saat itu kajian mengenai pelabelan graf bermunculan dan berkembang pesat belakangan ini. Hingga saat ini pemanfaatan teori pelabelan graf sangat dirasakan peranannya, terutama pada sektor sistem komunikasi dan transportasi, navigasi geografis, radar, penyimpanan data komputer, dan pemancar frekuensi radio. Pelabelan pada suatu graf adalah suatu pemetaan (fungsi) yang memasangkan unsur-unsur graf (titik dan/atau sisi) dengan bilangan (biasanya bilangan bulat). Jika domain dari fungsi adalah titik, maka pelabelan tersebut dinamakan pelabelan titik (vertex labellings), jika domainnya adalah sisi, maka pelabelannya disebut pelabelan sisi (edge labellings) dan jika domainnya adalah titik dan sisi, maka pelabelannya disebut pelabelan total (total labellings) (Wallis, 2001).

Hingga kini dikenal beberapa jenis pelabelan pada graf, antara lain pelabelan graceful (graceful labeling), pelabelan harmoni (harmonious labeling), pelabelan total tak beraturan (total irregularity labeling), pelabelan ajaib (magictype labeling), dan pelabelan anti ajaib (antimagic-type labeling). Pelabelan total titik irregular merupakan pemberian nilai bilangan bulat positif (nilai yang dipakai boleh berulang) pada himpunan titik dan sisi dari suatu graf G, dengan bobot setiap sisinya berbeda (Bača et al, 2007). Untuk sebuah graf G terdapat beberapa variasi pelabelan total sisi irregular, dengan kata lain pelabelannya tidak tunggal. Dalam pelabelan graf ini, asalkan bobot setiap sisinya berbeda maka pelabelan tersebut dinamakan dengan pelabelan total sisi irregular. Permasalahannya adalah bagaimana melabeli graf tersebut sedemikian hingga bilangan bulat positif terbesar yang di jadikan label pada beberapa variasi pelabelan total sisi irregular adalah seminimum mungkin. Bilangan bulat positif terbesar yang minimum tersebut dinamakan dengan total irregularity edge strength dari graf G yang dinotasikan dengan tes(G).

Related Post