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
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
Tidak ada komentar:
Posting Komentar