tugas teori graph

teori graf

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 (E1 – E2) ∪ (E2 – E1).
CONTOH
klik dsini untuk melihat hasil selanjut nya

materi teori graf

materi selanjutnya



http://www.scribd.com/doc/25489300/Teori-Graf

materi teori graf

 TEORI GRAPH 

Graph digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graf adalah dengan menuyatakan objek dinyatakan sebagai noktah, bulatan, atau titik, sedangkan hubungan antara objek dinyatakan dengan garis.

*

Gambar perkotaan

I. SEJARAH GRAPH
Teori graf pertama kali dikembangkan oleh Leonhard Euler dalam memecahkan masalah jembatan Königsberg (tahun 1736). Permasalahannya adalah " Apakah bisa seseorang  melalui  sekali setiap jembatan yang menghubungkan kota-kota tersebut, dan kembali lagi ke kota dari mana ia berjalan".

*

Gambar1.1  (a) Jembatan Königsberg [ROS99], dan (b) graf yang merepresentasikan jembatan Königsberg

Jawaban yang dikemukakan oleh Euler adalah: orang tidak mungkin melalui ketujuh jembatan itu masingmasing satu kali dan kembali lagi ke tempat asal keberangkatan jika derajat setiap simpul tidak seluruhnyagenap. Yang dimaksud dengan derajat adalah banyaknya garis yang bersisian dengan noktah. Sebagai contoh,simpul C memiliki derajat 3 karena ada tiga buah garis yang bersisian dengannya, simpul B dan D juga berderajat dua, sedangkan simpul A berderajat 5. Karena tidak semua simpul berderajat genap, maka tidak mungkin dilakuk an perjalananan berupa sirkuit (yang dinamakan dengan sirkuit Euler) pada graf tersebut.
II. DEFINISI GRAPH

Graf G didefinisikan sebagai pasangan himpunan (V, E), yang dalam hal ini:
V = himpunan tidak-kosong dari simpul-simpul (vertices atau node) = { v1 , v2 , ... , vn }
dan
E = himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul = {e1 , e2 , ... , en }
atau dapat ditulis singkat notasi G = (V, E).

CATATAN : menyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Jadi, sebuah graf
dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpulnya harus ada, minimal satu. Graf yang
hanya mempunyai satu buah simpul tanpa sebuah sisi pun dinamakan graf trivial.

Simpul pada graf dapat dinomori dengan huruf, seperti a, b, c, …, v, w, ..., dengan bilangan asli 1, 2, 3, ...,
atau gabungan keduanya. Sedangkan sisi yang menghubungkan simpul vi dengan simpul vj dinyatakan
dengan pasangan (vi, vj) atau dengan lambang e1, e2, …. Dengan kata lain, jika e adalah sisi yang
menghubungkan simpul vi dengan simpul vj , maka e dapat ditulis sebagai
e = (vi , vj)
Secara geometri graf digambarkan sebagai sekumpulan noktah (simpul) di dalam bidang dwimatra yang
dihubungkan dengan sekumpulan garis (sisi).

*

Gambar2.1

G1 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (1, 3), (2, 3), (2, 4), (3, 4) }

G2 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4) }
= { e1, e2, e3, e4, e5, e6, e7}

G3 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3) }
= { e1, e2, e3, e4, e5, e6, e7, e8}
Pada G2, sisi e3 = (1, 3) dan sisi e4 = (1, 3) dinamakan sisi-ganda (multiple edges atau paralel edges) karena
kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul 1 dan simpul 3. Pada G3, sisi e8 = (3, 3)
dinamakan gelang atau kalang (loop) karena ia berawal dan berakhir pada simpul yang sama.