Dimatematika 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).
contoh video: http://www.youtube.com/watch?v=t9UJIV7pN9I
sumber: id.wikipedia.org/wiki/Teori_graf
Selasa, 10 Juni 2014
Langganan:
Posting Komentar (Atom)
0 komentar:
Posting Komentar