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).
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).
Graf memiliki banyak jenis, dalam tulisan ini akan dibahas
beberapa jenis graf yang sering digunakan. Berdasarkan ada tidaknya gelang atau
sisi ganda pada suatu graf dan berdasarkan sisi pada graf yang mempunyai
orientasi arah.
Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf
maka graf digolongkan menjadi dua jenis:
- Graf sederhana (simple graph)
Graf yang tidak mengandung gelang maupun sisi
ganda dinamakan graf sederhana.
- Graf tak-sederhana (unsimple graph)
Graf yang mengandung sisi ganda atau gelang
dinamakan graf tak sederhana (unsimple graph). Ada dua macam graf tak
sederhana, yaitugraf ganda (multigraph) atau graf semu (pseudograph). Graf ganda adalah graf yang mengandung sisi ganda. Graf semu
adalah graf yang mengandung gelang (loop).
Jumlah simpul pada graf disebut sebagai kardinalitas graf, dan
dinyatakan dengan n = |V|, dan jumlah sisi kita nyatakan dengan m = |E|
Berdasarkan orientasi arah pada sisi, maka secara umum graf
dibedakan atas 2 jenis :
Berdasarkan
orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis :
- Graf tak-berarah (undirected graph)
Graf
yang sisinya tidak mempunyai orientasi arah disebut tak-berarah. Pada graf
tak-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak
diperhatikan. Jadi, (u, v) = (v, u) adalah sisi yang sama.
- Graf berarah (directed graph atau digraph)
Graf
yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Pada
graf berarah, (u, v) dan (v, u) menyatakan dua buah busur yang berbeda, dengan
kata lain (u, v)
(v, u). Untuk busur (u, v) simpul u dinamakan simpul asal (initial vertex)
dan simpul v dinamakan simpul terminal (terminal vertex).
Definisi
graf dapat diperluas sehingga mencakup graf-ganda berarah (directed multigraph).
Pada graf-ganda berarah, gelang dan sisi ganda diperbolehkan ada.
Sumber :
Munir, R.,
2005, Matematika
Diskrit, Informatika, Bandung.
http://aimprof08.wordpress.com/2012/04/26/jenis-jenis-graf/Contoh Graf dengan derajat 3
Derajat atau derajat busur adalah pengukuran sudut bidang yang
menunjukan 1/360 dari rotasi penuh. Satu derajat sama dengan n/180 radian. Ini
bukan satuan dari Sistem Internasional Satuan (SI)
Sumber :
http://danysatriokintoko.blogspot.com/
Tutorial cara membuat graf dengan derajat 3
http://youtu.be/YRVcl6NfXh0
Tidak ada komentar:
Posting Komentar