GRAPH

assalamualaikum wr wb
kali ini saya akan menjelaskan tentang graph. langsung saja kita ke pembahasannya

Pengertian Graph

Graph adalah kumpulan noktah (simpul) di dalam bidang dua dimensi yang dihubungkan dengan sekumpulan garis (sisi).Graph dapat digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graph adalah dengan menyatakan objek sebagai noktah, bulatan atau titik (Vertex), sedangkan hubungan antara objek dinyatakan dengan garis (Edge).

Dimana

G = Graph

V = Simpul atau Vertex, atau Node, atau Titik

E = Busur atau Edge, atau arc

Graf merupakan suatu cabang ilmu yang memiliki banyak terapan. Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan bantuan graf. Seringkali graf digunakan untuk merepresentasikan suaru jaringan. Misalkan jaringan jalan raya dimodelkan graf dengan kota sebagai simpul (vertex/node) dan jalan yang menghubungkan setiap kotanya sebagai sisi (edge) yang bobotnya (weight) adalah panjang dari jalan tersebut.

Ada beberapa cara untuk menyimpan graph di dalam sitem komputer. Struktur data bergantung pada struktur graph dan algoritma yang digunakan untuk memmanipulasi graph. Secara teori salah satu dari keduanya dapat dibedakan antara struktur list dan matriks, tetapi dalam penggunaannya struktur terbaik yang sering digunakan adalah kombinasi keduanya.

• Graph tak berarah (undirected graph atau non-directed graph) :

• Urutan simpul dalam sebuah busur tidak dipentingkan. Misal busur e1 dapat disebut busur AB atau BA

• Graph berarah (directed graph) :

• Urutan simpul mempunyai arti. Misal busur AB adalah e1 sedangkan busur BA adalah e8.

• Graph Berbobot (Weighted Graph)

• Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan memiliki bobot.

• Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, dll.

contoh graph tak berarah dan graph berarah

Sifat – sifat graph

• 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

Istilah Dalam Graph

1. Incident

Jika e merupakan busur dengan simpul-simpulnya adalah v dan w yang ditulis e=(v,w), maka v dan w disebut “terletak” pada e, dan e disebut incident dengan v dan w.

            2. Degree

Didalam Graph ada yang disebut dengan Degree, Degree mempuyai 3 jenis antara lain :

·         Degree dari suatu verteks x dalam undigraph adalah jumlah busur yang incident dengan simpul tersebut.

·         Indegree dari suatu verteks x dalam digraph adalah jumlah busur yang kepalanya incident dengan simpul tersebut, atau jumlah busur yang “masuk” atau menuju simpul tersebut..

·         Outdegree dari suatu verteks x dalam digraph adalah jumlah busur yang ekornya incident dengan simpul tersebut, atau jumlah busur yang “keluar” atau berasal dari simpul tersebut.

3. Adjacent

Pada graph tidah berarah, 2 buah simpul disebut adjacent bila ada busur yang menghubungkan kedua simpul tersebut. Simpul v dan w disebut adjacent.

Pada graph berarah, simpul v disebut adjacent dengan simpul w bila ada busur dari w ke v.

4. Successor dan Predecessor

Pada graph berarah, bila simpul v adjacent dengan simpul w, maka simpul v adalah successor simpul w, dan simpul w adalah predecessor dari simpul v.

            5. Path

Sebuah path adalah serangkaian simpul-simpul berbeda yang adjacent secara berturut-turut dari simpul satu ke simpul berikutnya.

Jenis graf

• Undirected (tanpa arah): Undirected graph adalah graf yang semua edge miliknya bersifat bi-directional. Dengan kata lain edge, tersebut tidak memiliki arah tertentu.

• Directed: Directed graph adalah graf yang semua edge miliknya bersifat uni-directional, dengan kata lain edge tersebut menuju ke arah tertentu.

• Weighted: Dalam weighted graf, setiap edge memiliki weight (bobot atau biaya). Perhatikan graf berisi 4 node yang ditunjukkan pada diagram di bawah ini. Sebagaimana yang dapat Anda lihat, setiap edge memiliki weight/bobot/biaya yang ditetapkan padanya. Jika Anda ingin berpindah dari vertex 1 ke vertex 3 Anda dapat menggunakan salah satu jalur berikut:
• 1 -> 2 -> 3
• 1 -> 3
• 1 -> 4 -> 3

Maka dari itu biaya total dari masing-masing jalur adalah sebagai berikut
– Biaya total dari 1 -> 2 -> 3 akan sebesar (1 + 2), atau 3 unit
– Biaya total dari 1 -> 3 sebesar 1 unit
– Biaya total dari 1 -> 4 -> 3 akan sebesar (3 + 2) yaitu 5 unit

Representasi graph pada matrik
graph tak berarah

 graph berarah