Dalam matematika dan
ilmu komputer, 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 Facebook bisa
direpresentasikan dengan graf, yakni simpul-simpulnya adalah para pengguna
Facebook dan ada sisi antar pengguna jika dan hanya jika mereka berteman.
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).
JENIS-JENIS GRAF
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 :
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) \neq (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.
Pengertian Graf
Secara sederhana graf didefinisikan sebagai kumpulan titik
yang dihubungkan oleh garis. Secaramatematis, graf adalah pasangan himpunan (V
, E ) dimana V adalah himpunan tak kosong yangmemiliki elemen disebut simpul
(vertices) dan E adalah kumpulan dari dua elemen subsets V yang disebut busur (edges).
Berikut ini saya telah menggambarkan hasil dari graf 3,4 dan
5
dan 1 buah video yang telah saya Upload di Youtube.com
anda bisa membukanya di
http://www.youtube.com/watch?v=3uLWgP7cZSc&feature=youtu.be
Comments
Post a Comment