Teori graf: Perbedaan antara revisi

Di [[matematika]] dan [[ilmu komputer]], '''teori graf''' adalah cabang ilmu yang mempelajari sifat-sifat [[graf]]. Secara informal, suatu graf adalah himpunan benda-benda yang disebut [[verteks]] (atau ''node'') yang terhubung oleh ''edge''-''edge'' (atau ''arc''). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan verteks) yang dihubungkan oleh garis-garis (melambangkan ''edge'').

 

 

Sebuah struktur graf bisa dikembangkan dengan memberi bobot pada tiap ''edge''. 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 ''edge''nya berarah, yang secara teknis disebut [[graf berarah]] atau [[digraf]]. Digraf dengan ''edge'' berbobot disebut [[Jaringan (matematika)|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).