TEORI GRAF
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 Friendster bisa direpresentasikan dengan graf:
simpul-simpulnya adalah para pemakai Friendster dan ada sisi antara A dan B
jika dan hanya jika A berteman (berkoinsidensi) dengan B. Perkembangan algoritma 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).
Suatu
graph G dapat dinyatakan sebagai G = < V,E > . Graph
G terdiri atas himpunan V yang berisikan simpul pada graf tersebut dan himpunan
dari E yang berisi sisi pada graf tersebut. Himpunan E dinyatakan sebagai
pasangan dari simpul yang ada dalam V. Sebagai contoh definisi dari graf pada
gambar di atas adalah : V = {1,2,3,4,5,6} dan E =
{(1,2),(1,5),(2,3),(3,4),(4,5),(5,2),(4,6)}
Pada digraf maka
pasangan-pasangan ini merupakan pasangan terurut. Untuk menyatakan digraf
(gambar kedua yang menggunakan tanda panah) kita dapat menggunakan himpunan edge
sebagai berikut :
E = { < 1,2 > , < 1,5 > ,
< 2,5 > , < 3,2 > , < 4,3 > , < 5,4 > , < 4,6 > }
Dalam
himpunan edge untuk digraf, urutan pasangan verteks menentukan arah dari
edge tersebut.
Dalam
teori graf, formalisasi ini untuk memudahkan ketika nanti harus membahas
terminologi selanjutnya yang berhubungan dengan graph. Beberapa terminologi
berhubungan dengan teori graf :
- Degree atau derajat dari suatu node, jumlah edge yang dimulai atau berakhir pada node tersebut. Node 5 berderajat 3. Node 1 berderajat 2.
- Path suatu jalur yang ada pada graph, misalnya antara 1 dan 6 ada path
- Cycle siklus ? path yang kembali melalui titik asal 2 kembali ke 2.
- Tree merupakan salah satu jenis graf yang tidak mengandung cycle. Jika edge f dan a dalam digraf di atas dihilangkan, digraf tersebut menjadi sebuah tree. Jumlah edge dalam suatu tree adalah nV - 1. Dimana nV adalah jumlah vertex
- Graf Tak Berarah (Undirected Graph) Graf G disebut graf tak berarah (undirected graph) jika setiap sisinya tidak berarah. Dengan kata lain (vi,vj)=(vj,vi)
- Graf Berarah (Directed Graph) Graf G disebut graf berarah (directed graph) jika setiap sisinya berarah. Titik awal dari suatu sisi disebut verteks awal (initial vertex) sedangkan titik akhir dari suatu sisi disebut verteks akhir (terminal vertex). Loop pada graf adalah sisi yang verteks awal dan verteks akhirnya sama.
http://id.wikipedia.org/wiki/Teori_graf
Tidak ada komentar:
Posting Komentar