GRAPH
• Pengantar
Teori Graph atau teori Graphik dalam matematika dan ilmu komputer adalah cabang kajian yang
mempelajari sifat-sifat "Graph" atau "Graphik". Ini tidak sama dengan "Graphika". Secara
informal, suatu Graph adalah himpunan benda-benda yang disebut "simpul" (vertex atau node)
yang terhubung oleh "sisi" (edge) atau "busur" (arc). Biasanya Graph 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 Graph bisa dikembangkan dengan memberi bobot pada tiap sisi. Graph
berbobot dapat digunakan untuk melambangkan banyak konsep berbeda. Sebagai contoh jika suatu
Graph melambangkan jaringan jalan maka bobotnya bisa berarti panjang jalan maupun batas
kecepatan tertinggi pada jalan tertentu. Ekstensi lain pada Graph adalah dengan membuat sisinya
berarah, yang secara teknis disebut Graph berarah atau diGraph (directed graph). DiGraph dengan
sisi berbobot disebut jaringan.
Jaringan banyak digunakan pada cabang praktis teori Graph yaitu analisis jaringan. Perlu
dicatat bahwa pada analisis jaringan, definisi kata "jaringan" bisa berbeda, dan sering berarti Graph
sederhana (tanpa bobot dan arah).
• Graph
Graph adalah kumpulan dari simpul dan busur yang secara matematis dinyatakan sebagai :
G = (V, E)
Dimana :
G = Graph
V = Simpul atau Vertex, atau Node, atau Titik
E = Busur atau Edge, atau arc
Contoh graph :
V terdiri dari v1, v2, …, v5
E terdiri dari e1, e2, … , e7
✓ Sebuah graph mungkin hanya terdiri dari satu simpul.
✓ Sebuah graph belum tentu semua simpulnya terhubung dengan busur.
✓ Sebuah graph mungkin mempunyai simpul yang tak terhubung dengan simpul yang lain.
✓ Sebuah graph mungkin semua simpulnya saling berhubungan
• Jenis Graph
Berdasarkan orientasi arah pada sisi dan bobotnya, maka secara umum Graph dibedakan atas
empat jenis :
1. Graph tidak berarah dan berbobot (undirected graph)
Graph yang setiap sisinya tidak mempunyai arah anak panah tetapi memiliki bobot pada setiap
sisinya. Urutan pasangan simpul yang terhubung oleh sisi tidak diperhatikan. Sehingga (u,v) =
(v,u) adalah sisi yang sama.
Sehingga Graph tak berarah sering dipakai pada jaringan saluran telepon karena sisi pada
Graph tak berarah menyatakan bahwa saluran telepon dapat beroperasi pada dua arah. Perhatikan
contoh Graph tak berarah pada Gambar berikut dengan enam buah Vertex dan sebelas buah Edge.
2. Graph berarah dan berbobot (directed graph)
Graph yang setiap sisinya diberikan orientasi arah disebut sebagai Graph berarah. Secara umum
sisi berarah disebut dengan busur (arc). Pada Graph berarah (u,v) dan (v,u) menyatakan dua buah
busur yang berbeda, dalam arti kata bahwa (u,v) ≠ (v,u). Jadi untuk busur (u,v) simpul u dinamakan
simpul asal dan simpul v dinamakan simpul terminal atau simpul tujuan.
Graph berarah sering dipakai untuk menggambarkan aliran proses, peta lintas kota dan lain
sebagainya. Sehingga pada Graph berarah gelang atau looping diperbolehkan tetapi sisi ganda
tidak diperbolehkan.
“Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot). Bobot pada
tiap sisi dapat berbeda – beda bergantung pada masalah yang dimodelkan dengan graf. Bobot dapat
menyatakan jarak antara dua buah kota, biaya perjalanan antara dua buah kota, waktu tempuh
pesan (message) dari sebuah simpul komunikasi ke simpul komunikasi lain ( dalam jaringan
computer), ongkos produksi, dan sebagainya” ( Munir, 2009 : 376). Perhatikan contoh Graph
berarah pada Gambar berikut dengan enam buah Vertex dan sebelas buah Edge.
3. Graph tidak berarah dan tidak berbobot
Graph yang setiap sisinya tidak mempunyai arah dan tidak mempunyai bobot apapun. Perhatikan
contoh Graph tidak berarah dan tidak berbobot pada Gambar berikut.
4. Graph berarah dan tidak berbobot
Graph yang setiap sisinya mempunyai arah tetapi tidak mempunyai bobot apapun. Perhatikan
contoh Graph berarah dan tidak berbobot pada Gambar berikut.