BAB I PENDAHULUAN

A. Pendahuluan

Teori graf adalah cabang kajian yang mempelajari sifat-sifat graf. Secara

informal, suatu graf adalah himpunan benda-benda yang

disebut simpul (vertex atau node) yang terhubung oleh sisi (edge) atau busur (arc).

Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan simpul) yang

dihubungkan oleh garis-garis (melambangkan sisi) atau garis berpanah (melambangkan

busur). Suatu sisi dapat menghubungkan suatu simpul dengan simpul yang sama. Sisi

yang demikian dinamakan gelang (loop).

Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak

masalah yang bisa diselesaikan dengan bantuan graf. Jaringan persahabatan

pada Facebook bisa direpresentasikan dengan graf, yakni simpul-simpulnya adalah para

pengguna Facebook dan ada sisi antar pengguna jika dan hanya jika mereka berteman.

Perkembanganalgoritma untuk menangani graf akan berdampak besar bagi ilmu

komputer.

Sebuah struktur graf bisa dikembangkan dengan memberi bobot pada tiap sisi.

Graf berbobot dapat digunakan untuk melambangkan banyak konsep berbeda. Sebagai

contoh jika suatu graf melambangkan jaringan jalan maka bobotnya bisa berarti panjang

jalan maupun batas kecepatan tertinggi pada jalan tertentu. Ekstensi lain pada graf adalah

dengan membuat sisinya berarah, yang secara teknis disebut graf

berarah atau digraf (directed graph). Digraf dengan sisi berbobot disebut jaringan.

Jaringan banyak digunakan pada cabang praktis teori graf yaitu analisis jaringan.

Perlu dicatat bahwa pada analisis jaringan, definisi kata "jaringan" bisa berbeda, dan

sering berarti graf sederhana (tanpa bobot dan arah).

1

BAB II PEMBAHASAN

A. Penerapan Teori Graf

1. Penerapan Graf Pada Penjadwalan Kuliah

Metode pewarnaan graf yang cocok untuk penyusunan jadwal perkuliahan

adalah pewarnaan sisi. Dari proses metode pewarnaan graf tersebut, dapat dibuat

jadwal yang tepat sehingga jadwal dari mata kuliah yang sama dan dosen yang sama

yang dibuat tidak pada waktu yang sama/tidak terjadi tumpah tindih jadwal selain itu

dapat diatur jumlah maksimal mata kuliah dari masing-masing kelas. Dari sebuah

graf yang dibuat dengan pewarnaan sisi, dari warna sisi, dapat diketahui apabila sisi

yang berwarna sama, menunjukkan apabila sisi-sisi tersebut dapat dibuat pada waktu

yang sama. Namun apabila warna yang digunakan berbeda, maka jadwal tersebut

tidak dibuat pada waktu yang sama.

a. Metode Penelitian

Adapun tahap-tahap penelitian jika disajikan dalam bentuk bagan alir penelitian

(flowchart) seperti pada gambar 3.1 berikut

2

HASIL PENELITIAN DAN PEMBAHASAN

Graf Penjadwalan Perkuliahan Dengan terbatasnya ketersediaan ruang

perkuliahan dibandingkan jumlah kelas pada setiap tingkatan semester, maka

diperlukan jadwal yang efisien yang tidak saling tumpang tindih baik dalam hal ruang

kuliah maupun waktu perkuliahan. Oleh karena itu, sebelum membuat graf

penjadwalan perkuliahan terlebih dahulu merepresentasikan komponen-komponen

dalam penjadwalan ke dalam graf.

Adapun graf yang menggambarkan banyaknya mata kuliah, banyaknya jumlah

kelas dan banyaknya hari adalah sebagai berikut:

Graf antara Banyaknya Mata Kuliah, Banyaknya Jumlah Kelas dan

Banyaknya Hari Dari gambar graf diatas dapat terlihat untuk masing-masing kelas

untuk setiap tingkatan semester mendapat jumlah sebaran mata kuliah yang sama

untuk semester ganjil. Selain itu, terlihat juga untuk setiap kelas pada setiap tingkatan

semester memiliki jadwal kuliah mulai dari Senin sampai hari Jumat.

Pewarnaan Graf Sebelum melakukan pewarnaan graf, dibuat terlebih dahulu

graf yang menggambarkan hubungan antara mata kuliah, kelas dan ruang kuliah per

harinya. Kemudian dibuat pewarnaan graf antara mata kuliah dan kelas serta antara

kelas dan ruang kuliah.

3

Pewarnaan yang digunakan pada graf penjadwalan ini yaitu pewarnaan sisi.

Pewarnaan sisi merupakan pemberian warna setiap sisi pada graf sehingga sisi-sisi

yang berhubungan tidak memiliki warna yang sama. Kemudian dari pewarnaan

tersebut dicari bilangan kromatiknya, yaitu banyaknya warna minimum yang dapat

digunakan untuk mewarnai sisi.

Dalam melakukan pewarnaan sisi akan dilihat bilangan kromatik dari

pewarnaan. Graf tersebut. Untuk memudahkan dalam pewarnaan sisinya diperlukan

algoritma (langkah-langkah pengerjaan) dalam pewarnaan sisi graf.

Algoritma dalam pewarnaan sisi graf dapat diilustrasikan dalam flowchart berikut:

Flowchart Algoritma Pewarnaan Sisi Dari sebuah graf yang dibuat dengan pewarnaan

sisi, dari warna sisi, dapat diketahui dua hal yaitu, pertama apabila sisi yang berwarna sama,

menunjukkan apabila sisi-sisi tersebut dapat dibuat pada waktu yang sama. Namun apabila

4

warna yang digunakan berbeda, maka jadwal tersebut tidak dibuat pada waktu yang sama.

Kemudian yang kedua, banyaknya warna yang digunakan menggambarkan jumlah mata

kuliah yang terjadwal untuk masing-masing kelas pada setiap harinya.

Contohnya graf yang menghubungkan antara mata kuliah, kelas dan ruang kuliah

yang terjadi pada hari Senin. Berikut ini adalah graf yang menghubungkan antara mata

kuliah, kelas dan ruang kuliah yang terjadi pada hari Senin:

Setelah dibuat graf penjadwalannya, kemudian dibuat pewarnaan grafnya

yaitu pewarnaan sisi. Ada dua hal yang akan dilihat dari pewarnaan sisi yang dibuat.

Yang pertama adalah jumlah mata kuliah dari masing-masing kelas. Jadi pewarnaan

graf yang akan dibuat yaitu pewarnaan graf antara mata kuliah dan kelas. Berikut ini

adalah pewarnaan graf antara mata kuliah dan kelas pada hari Senin:

5

Gambar 4.7 Pewarnaan Graf antara Matakuliah dan Kelas pada Hari Senin

Dari gambar pewarnaan graf di atas dapat dilihat graf bisa diwarnai dengan

minimal dua warna sehingga bilangan kromatiknya ()= 2.Warna yang berbeda

menyatakan bahwa jumlah mata kuliah pada hari Senin. Jadi, dari perwarnaan graf

diatas dapat dilihat bahwa jumlah mata kuliah untuk setiap kelas pada semester 1, 3,

dan 5 pada hari Senin adalah 2 mata kuliah.Hal kedua yang akan dilihat dari

perwarnaan sisi adalah waktu perkuliahan yang terjadi pada setiap ruang kuliah. Jadi

pewarnaan graf yang akan dibuat yaitu pewarnaan graf antara kelas dan ruang kuliah.

Berikut ini adalah pewarnaan graf antara kelas dan ruang kuliah pada hari Senin:

Gambar 4.8 Pewarnaan Graf antara Kelas dan Ruang Kuliah pada Hari Senin

Dari gambar pewarnaan graf di atas dapat dilihat graf bisa diwarnai dengan

minimal empat warna sehingga bilangan kromatiknya ()= 4.Warna yang berbeda

menyatakan bahwa waktu perkuliahan yang dilaksanakan pada waktu yang berbeda

pada tiap-tiap ruangan.

2. Penerapan Graf dari Persoalan Ruangan Rumah

Bagaimana Membangun Graf Berdasarkan Permasalahan Yang dihadapi

Selanjutnya akan dibahas tentang cara-cara menggunakan graf dalam berbagai

persoalan dan permasalahan untuk mempermudah dan memperjelas permasalahan

yang sedang dihadapi.

6

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.

Misalkan gambar di atas adalah denah lantai dasar sebuah gedung. Apakah

dimungkinkan berjalan melalui setiap pintu di lantai itu hanya satu kali saja jika kita

boleh mulai memasuki pintu yang mana saja? Kita tidak akan menyelesaikan

permasalahan tersebut di bahasan ini, tapi hanya untuk membangun graf yang

memodelkan permasalahan ini. Maka pertama-tama kita harus melihat dahulu apakah

permasalahan ini dapat dimodelkan menjadi graf, ternyata setiap ruangan termasuk

bagian luar rumah dapat dijadikan simpul, sehingga setiap pintu akan menjadi sisi-sisi

yang menghubungkan setiap simpul dalam graf yang akan kita bentuk, maka graf

yang akan terbentuk adalah seperti terlihat dalam gambar 2.d berikut ini.

7

3. Penerapan Graf Dalam Menentukan Jalur Angkot

Penerapan graf ini bertujuan untuk menentuakan sebuah jalur untuk sebuah Angkutan

Umum, dan sebagai rencana atau sketsa dalam proses pembuatannya sehingga dalam

proses pelaksanaan dapat tersusun dengn baik.

Keterangan gambar :

Coklat : Rute Kalapa-Dago

Kuning : Rute Panghegar-Dipati Ukur

Biru : Rute Caringin-Sadang Serang

Hijau : Rute Caheum-Ledeng

Ungu : Rute Cisitu-Tegallega

Simpul 1 : Persimpangan Cisitu - Tamansari

Simpul 2 : Simpang Dago

Simpul 3 : Persimpangan Ganeca – Ir. Juanda

Simpul 4 : Persimpangan Cikapayang – Ir. Juanda

Simpul 5 : Persimpangan Sulanjana – Ir. Juanda

Simpul 6 : Persimpangan Tamansari - Sulanjana

Simpul 7 : Persimpangan Tamansari - Cikapayang

Simpul 8 : Persimpangan Tamansari - Ganesha

8

Adapun prinsip-prinsip yang digunakan adalah :

Setiap simpul dari graf adalah suatu persimpangan yang merupakan tempat

bertemunya satu rute angkot dengan rute angkot lainnya.

Setiap sisi dari graf menyatakan 2 hal :

1. Jenis angkot (pada gambar diwakili oleh warna)

2. Arah angkot

Bobot pada graf adalah lama waktu tempuh yang diperlukan untuk berpindah

antara satu simpul ke simpul lainnya (dalam hal ini, waktu tempuh antar

persimpangan).

Maka bagaimana aplikasi dari graf di atas? Misalkansaja seorang pengguna jasa

angkot hendak pergi dariSimpul 5 ke Simpul 1, maka ada beberapa kemungkinan

jalur :

9

BAB III PENUTUP

A. Kesimpulan

Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak

masalah yang bisa diselesaikan dengan bantuan graf. Jaringan persahabatan

pada Facebook bisa direpresentasikan dengan graf, yakni simpul-simpulnya adalah para

pengguna Facebook dan ada sisi antar pengguna jika dan hanya jika mereka berteman.

Perkembanganalgoritma untuk menangani graf akan berdampak besar bagi ilmu

komputer.

Sebuah struktur graf bisa dikembangkan dengan memberi bobot pada tiap sisi.

Graf berbobot dapat digunakan untuk melambangkan banyak konsep berbeda. Sebagai

contoh jika suatu graf melambangkan jaringan jalan maka bobotnya bisa berarti panjang

jalan maupun batas kecepatan tertinggi pada jalan tertentu.

10

DAFTAR PUSTAKA

Makalah II2092 Probabilitas dan Statistik – Sem. ITahun 2010/2011

Penerapan Konsep Graf Dalam Penyusunan Jadwal Perkuliahan Di Jurusan Pendidikan

Matematika FMIPA UNG Nisky Imansyah Yahya, Perry Zakaria, Lailany Yahya

http://danysatriokintoko.blogspot.com/2013/02/teori-dasar-graf.html

11