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).
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:
1.
Graf sederhana (simple graph)
Graf yang tidak mengandung gelang maupun sisi ganda dinamakan
graf sederhana.
2.
Graf tak-sederhana (unsimple graph)
Graf yang mengandung sisi ganda atau gelang dinamakan graf
tak sederhana (unsimple graph). Ada dua macam graf tak sederhana, yaitu :
1. graf ganda (multigraph)
Graf ganda merupakan graf tak berarah yang tidak
mengandung gelang
(loop).
2. graf semu (pseudograph).
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 :
1.
Graf tak-berarah (undirected graph)
Graf berarah merupakan
graf yang setiap sisinya mempunyai arah dan
diantara dua buah simpul tidak mempunyai
dua sisi yang berlawanan.
2.
Graf berarah (directed graph atau digraph)
Graf ganda berarah
merupakan graf berarah yang membolehkan adanya sisi ganda pada graf
tersebut (boleh mempunyai dua sisi yang berlawanan antara dua buah simpul).
3. Graf ganda berarah (directed
multigraph).
Graf ganda berarah merupakan graf berarah yang
membolehkan adanya sisi ganda pada graf tersebut (boleh mempunyai dua sisi yang
berlawanan antara dua buah simpul).
Terminologi Graf
1. Bertetangga (Adjacent)
Jika kedua simpul tersebut terhubung langsungoleh suatu
sisi.
2. Bersisian (Incidency)
Suatu sisi e dikatakan bersisian dengan simpul v1 dan
simpul v2 jika e menghubungkan kedua simpul tersebut.
3. Simpul Terpencil (Isolated Vertex)
Jika suatu simpul tidak mempunyai sisi yang bersisian
dengan simpul itu sendiri.
4. Derajat (Degree)
Derajat suatu simpul merupakan jumlah sisi yang
bersisian dengan simpul tersebut. Misalkan, suatu simpul v mempunyai 3
buah sisi yang bersisian dengannya maka dapat dikatakan simpul tersebut
berderajat 3, atau dinotasikan oleh d(v) = 3.
Pada graf diatas :
d(P) = d(Q) = d (S)= 5,
sedangkan d(R) = 3.
Derajat sebuah simpul pada suatu graf berarah dijelaskan
sebagai berikut :
•
din(v) merupakan jumlah busur yang masuk ke simpul v
• dout(v) merupakan jumlah busur yang keluar dari
simpul v
Dengan demikian derajat pada simpul tersebut, diperoleh :
d(v) = din(v) + dout(v).
Lintasan (Path)
Lintasan dari suatu simpul awal v0 ke simpul
tujuan vT di dalam suatu graf G merupakan barisan
sebuah sisi atau lebih (x0, x1), (x1, x2), (x2, x3), …, (xn-1, xn) pada G,
dimana x0 = v0 dan xn = vT. Lintasan ini dinotasikan
oleh : x0, x1, x2, x3, …, xn.
• Pada graf tersebut
lintasan P, Q, R memiliki panjang 2. Sementara itu
lintasan P, Q, S, R memiliki panjang
3.
• Lintasan P, Q, R, S, P dinamakan siklus atau
sirkuit dengan panjang 4.
• Antara simpul P dan U maupun T tidak dapat
ditemukan lintasan.
Cut-Set
Cut-set dari suatu graf terhubung G adalah himpunan sisi
yang jika dibuang dari G menyebabkan G tidak terhubung. Jadi,
cut-set selalu menghasilkan dua buah subgraf . Pada graf di bawah,
{(1,4), (1,5), (2, 3), (2,4)} adalah cut-set. Terdapat banyak cut-set
pada sebuah graf terhubung. Himpunan {(1,5), (4,5)} juga adalah cut-set,
{(1,4), (1,5), (1,2)} adalah cut-set, {(5,6)} juga cut-set, tetapi {(1,4),
(1,5), (4,5)} bukan cut-set sebab himpunan bagiannya, {(1,5), (4,5)} adalah
cut-set.
Disini saya akan memberikan contoh graf teratur berderajat 3 , 4 dan 5 ( 3D, 4D, 5D ) maksud dari :
3D
yaitu setiap titik dapat menghasilkan 3 garis
4D
yaitu setiap titik dapat menghasilkan 4 garis
5D
yaitu setiap titik dapat menghasilkan 5 garis
berikut
contoh gambar dari graf teratur :
sumber:
Link Video:
