Mat Dan Imu Alamiah Dasar

PENGERTIAN GRAF

Graf dapat didefinisikan sebagai kumpulan simpul-simpul yang dihubungkan dengan garis. Simpul biasa dinyatakan dengan istilah verteks dan garis biasa dinyatakan dengan istilah edges atau busur. Dalam setiap persoalan, graf memberikan sebuah sruktur model tentang sistem yang kita pelajari, menjelaskan interaksi dan hubungan antara berbagai komponen dalam sistem. Sedangkan dalam berbagai persoalan, masalah yang sering muncul dalam pelaksanaannya adalah mendapatkan sebuah penyusunan yang memenuhi semua permintaan, dan optimal menurut beberapa kriteria seperti harga, pengeluaran atau penampilan.

JENIS – JENIS GRAF

• Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis:
1. Graf sederhana (simple graf).
Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana.
2. Graf tak-sederhana (unsimple-graf/multigraf).
Graf yang mengandung ruas ganda atau gelung dinamakan graf tak-sederhana (unsimple graf atau multigraf).
• Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:

1. Graf berhingga (limited graf)
Graf berhingga adalah graf yang jumlah simpulnya, n, berhingga.
2. Graf tak-berhingga (unlimited graf)
Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graf tak-berhingga.

• Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis:

1. Graf tak-berarah (undirected graf)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah.
2. Graf berarah (directed graf)
Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah.
Dua buah graf pada Gbr adalah graf berarah.

Masalah dasar yang sering muncul pada Matematika Diskret yaitu :

Masalah Alokasi

Pada  permasalahan  pengalokasian  frekuensi  pengangkutan  ke  stasiun pengirim, dimisalkan ada m  saluran  (frekuensi) yang mungkin digunakan oleh  n stasiun  pengirim. Stasiun  yang  dialokasikan  dekat  dengan  stasiun  yang  lain  dan tidak dapat menggunakan    saluran  yang  sama  tanpa menyebabkan percampuran. Jadi, diberikan dua  stasiun  yang dapat atau  tidak  dapat dinyatakan  bahwa kedua stasiun itu menggunakan saluran yang sama. Sejumlah persoalan terjadi.

Masalah Eksistensi

Apakah mungkin untuk mengalokasikan sebuah saluran pada setiap gardu di mana untuk dua stasiun  yang  berbeda  saluran  harus mempunyai  saluran  yang berbeda? Jika ya, bagaimana cara mendapatkan alokasi tersebut ?

Masalah Perhitungan

Berapa banyak alokasi yang sesuai ?

Masalah Optimasi

Berapa jumlah saluran minimum yang memenuhi kondisi alokasi ? Bagaimana kita dapat memodelkan situasi  ini ? Sebuah model graf dapat dikembangkan  sebagai  berikut.  Setiap  stasiun  dihubungkan  oleh  simpul  dan  2 simpul dihubungkan oleh 1 busur  jika dan  hanya  jika  stasiun  yang  berhubungan tidak menggunakan saluran yang sama.

BEBERAPA GRAF SEDERHANA KHUSUS

a. Graf Lengkap (Complete Graph)

Graf lengkap ialah graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya. Graf lengkap dengan  n buah simpul dilambangkan dengan  Kn. Jumlah sisi pada graf lengkap yang terdiri dari n buah simpul adalah n(n – 1)/2.

b. Graf Lingkaran

Graf lingkaran adalah graf sederhana yang setiap simpulnya berderajat dua. Graf lingkaran dengan n simpul dilambangkan dengan Cn.

c. Graf Teratur (Regular Graphs)

Graf yang setiap simpulnya mempunyai derajat yang sama disebut  graf teratur. Apabila derajat setiap simpul adalah  r, maka graf tersebut disebut sebagai graf teratur derajat r. Jumlah sisi pada graf teratur adalah nr/2.

d. Graf Bipartisi (Bipartite Graph)

Graf G yang himpunan simpulnya dapat dipisah menjadi dua himpunan bagian V1 dan V2,  sedemikian sehingga setiap sisi pada G menghubungkan sebuah simpul di V1 ke sebuah simpul di V2 disebut graf bipartisi dan dinyatakan sebagai G(V1, V2).  Dilambangkan KMN.

e.  Graf Platonik

Graf yang berasal dari penggambaran bangun ruang, dimana titik sudut merupakan simpul, dan rusuk meruakan ruas.

OPERASI GRAF

G1 = (E1,V1)  ,  G2 = (E2,V2)

1.  Gabungan G1 ∪ G2 adalah graf dgn himpunan ruasnya E1 ∪ E2.

2.  Irisan G1 ∩ G2 adalah graf dgn himpunan ruasnya E1 ∩ E2.

3.  Selisih G1 – G2 adalah graf dgn himpunan ruasnya E1 – E2.

4.  Selisih G2 – G1 adalah graf dgn himpunan ruasnya E2 – E1.

5.  Penjumlahan ring G1 ⊕ G2 adalah graf dgn himpunan ruasnya  (E1 ∪ E2) – (E1 ∩ E2) atau (E1E2)∪ (E2 – E1).

CONTOH

Sumber

http://krisna.students-blog.undip.ac.id/?p=48

Chartrand, Gary & Oellermann, Ortrud R. 1993, Applied and Algorithmic Graph Theory, McGraw-Hill, Inc.
McHugh,  James A. 1990, Algoritmic Graph Theory, Prentice-Hall  International, Inc.

Yuni Dwi Astuti, Logika dan Algoritma