DEFINISI GRAPH
Graph kumpulan simpul-simpul yang dihubungkan dengan garis. Simpul biasa dinyatakan dengan istilah verteks dan garis biasa dinyatakan dengan istilah edges atau busur.
JENIS GRAPH
Pengelompokkan graf dapat didasarkan pada ada tidaknya sisi ganda atau sisi kalang, pada jumlah simpul, atau berdasarkan orientasi arah pada sisi.
Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, secara umum graf dapat digolongkan menjadi dua jenis :
1. Graph sederhana
Graf yang tidak mengandung gelang maupun sisi ganda dinamakan graf sederhana. Jaringan komputer merupakan contoh aplikasi graf sederhana.
2. Graph tak sederhana
Dibagi menjadi 2, yaitu graf ganda dan graf semu. Graf ganda ialah graf yang mengandung sisi ganda. Graf semu ialah graf yang mengandung gelang.
Berdasarkan jumlah simpul pada suatu graf, secara umum graf dapat digolongkan menjadi dua jenis :
1. Graf berhingga
Ialah graf yang jumlah simpulnya berhingga.
2. Graf tak berhingga
Ialah graf yang jumlah simpulnya tak berhingga.
Berdasarkan orientasi arah pada sisi, secara umum graf dibedakan atas dua jenis :
1. Graf berarah
Graf yang setiap sisinya diberikan orientasi arah disebut graf berarah.
2. Graf tak berarah
Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak berarah.
Terminologi Dasar
Banyak terminologi yang akan sering digunakan dalam pembahasan graf, diantaranya :
1. Bertetangga (Adjacent)
Dua buah simpul pada graf tak-berarah G dikatakan bertetangga jika keduanya terhubung langsung dengan sebuah sisi.
2. Bersisian (Incident)
Untuk sembarang sisi e = (vj, vk), sisi e dikatakanbersisian dengan simpul vj dan vk.
3. Simpul Terpencil (Isolated Vertex)
Simpul yang tidak mempunyai sisi yang bersisian dengannya disebut simpul terpencil.
4. Graf Kosong (Null Graph atau Empty Graph)
Graf yang himpunan sisinya merupakan himpunan kosong disebut graf kosong.
5. Derajat (Degree)
Derajat suatu simpul pada graf tak berarah adalah jumlah sisi yang bersisian dengan simpul tersebut. Pada graf berarah, derajat suatu simpul ialah jumlah busur yang masuk ke simpul ditambah dengan jumlah busur yang keluar dari simpul.
6. Lintasan (Path)
Lintasan yang panjangnya n dari simpul awal vo ke simpul tujuan vn di dalam graf G ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v0, e1, v1, e2, v2, … , vn-1, en, vn,
sedemikian sehingga e1 = (v0,v1), e2 = (v1,v2), … , en = (vn-1,vn) adalah sisi-sisi dari graf G. Panjang lintasan adalah jumlah sisi dalam lintasan tersebut.
7. Siklus (Cycle) atau Sirkuit (Circuit)
Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atau siklus. Panjang sirkuit adalah jumlah sisi di dalam sirkuit tersebut.
8. Terhubung (Connected)
Graf tak berarah G disebut graf terhubung jika untuk setiap pasang simpul vi dan vj dalam himpunan V terdapat lintasan dari vi ke vj. Jika tidak, maka graf G tak terhubung.
9. Upagraf (Subgraph) dan Komplemen Upagraf
Misalkan G = (V,E) adalah sebuah graf. G1 = (V1, E1) adalah upagraf dari G jika V1 ⊆ V dan E1 ⊆ E. Komplemen dari upagraf G1 terhadap graf G adalah graf G2 = (V2, E2) sedemikian sehingga E2 = E – E1 dan V2 adalah himpunan simpul yang anggota-anggota E2 bersisian dengannya.
10. Upagraf Merentang (Spanning Subgraph)
Upagraf G1 = (V1, E1) dari G = (V,E) dikatakan upagraf merentang jika V1 = V (yaitu G1 mengandung semua simpul dari G)
11. Cut-Set
Cut-set dari graf terhubung G adalah himpunan sisi yang bila dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen terhubung. Nama lain untuk cut-set ialah bridge (jembatan). 12. Graf Berbobot (Weighted Graph) Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot). Graf inilah yang digunakan untuk mencari lintasan terpendek.
