Graph Berarah dan Tidak Berarah

Assalamualaikum wr.wb 

Hai teman-teman, kali ini saya akan membahas tentang GRAPH. Apa sih Graph itu ? .

GRAPH adalah kumpulan dari simpul dan busur yang secara matematis dinyatakan sebagai :

G = (V, E). Graf juga didefinisikan sebagai himpunan benda-benda yang disebut verteks (node) yang terhubung oleh sisi (atau edge ata u arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan verteks) yang dihubungkan oleh garis-garis (melambangkan sisi).

Dimana

            G = Graph

            V = Simpul atau Vertex , atau Node, atau Titik

            E = Busur atau Edge , atau Arc

Graph dibagi menjadi dua yaitu :

DIREKTED (Berarah)

Urutan pasangan simpul disini sangat diperhatikan karena dapat menyatakan hal yang berbeda. Urutan simpul mempunyai arti. Misal busur RI adalah e1 sedangkan busur IR adalah e8.

Keterangan Simpul atau Node:

                      R = v1            

                      I   = v2

                      D  = v3

                      H  = v4

                      O = v5

            Keterangan Busur :

                      R1  = e1

                      IR  = e8

                      RO = e2

                      OH = e6

                      OD = e5

                      DH = e7

                      ID  =  e3

                      IH  =  e4

                      DI  = e9

                      DO = e10

           

UNDIREKTED (Tidak Berarah )

Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak berarah. Pada graf tak-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Urutan simpul dalam sebuah busur tidak dipentingkan. Misal busur e1 dapat disebut busur MU atau UM.

Keterangan Busur : Busur e1 dapat disebut Busur  MU atau UM

                                Busur e2 dapat disebut Busur  MA atau AM

                                Busur e3 dapat disebut Busur  UN atau NU

                                Busur e4 dapat disebut Busur  UF atau FU

                                Busur e5 dapat disebut Busur  AN atau NA
                                Busur e6 dapat disebut Busur  AF atau FA

                                Busur e7 dapat disebut Busur  NF atau FN      

Secara umum terdapat dua macam representasi dari struktur data graf yang dapat diimplementasi. 

- Pertama, disebut Adjacency List( diimplementasi dengan menampilkan masing-masing simpul sebagai sebuah struktur data yang mengandung semua simpul yang saling berhubungan). 

- Kedua adalah representasi berupa Adjacency Matrix dimana baris dan kolom dari matriks (jika dalam konteks implementasi berupa senarai dua dimensi) tersebut merepresentasikan simpul awal dan simpul tujuan dan sebuah entri di dalam  menyatakan apakah terdapat sisi di antara kedua simpul tersebut.

* Adjacency List

Dalam teori graf, adjacency list merupakan bentuk representasi dari seluruh sisi atau busur dalam suatu graf sebagai suatu senarai. Simpul-simpul yang dihubungkan sisi atau busur tersebut dinyatakan sebagai simpul yang saling terkait. Dalam implementasinya, hash table digunakan untuk menghubungkan sebuah simpul dengan senarai berisi simpul-simpul yang saling terkait tersebut..

Graf pada gambar diatas dapat dideskripsikan sebagai senarai {a,b},{a,c},{b,c}. Dan representasi adjacency list dapat digambarkan melalui tabel di bawah ini.

Tabel 1. Representasi Adjacency List 

Vertex	Adjacency	Array of Adjacent
A	Adjacent to	B,c
B	Adjacent to	A,c
C	Adjacent to	A,b

Salah satu kekurangan dari teknik representasi ini adalah tidak adanya tempat untuk menyimpan nilai yang melekat pada sisi. Contoh nilai ini antara lain berupa jarak simpul, atau beban simpul.

Adjacency Matrix
Adjacency Matrix merupakan representasi matriks yang menyatakan hubungan antar simpul dalam suatu graf. Kolom dan baris dari matriks ini merepresentasikan simpul-simpul, dan nilai entri dalam matriks ini menyatakan hubungan antar simpul.

Gambar diatas merupakan adjacency matrix yang berkorelasi dengan graf tak berarah. Kolom dan baris pada matriks merupakan simpul- simpul berlabel 1-6. Kelebihan dari adjacency matrix ini adalah elemen matriksnya dapat diakses langsung melalui indeks, dengan begitu hubungan ketetanggan antara kedua simpul dapat ditentukan dengan langsung. Sedangkan kekurangan pada representasi ini adalah bila graf memiliki jumlah sisi atau busur yang relative sedikit.

Sekian penjelasan dari saya , mohon maaf jika ada kesalahan J .Wassalamualaikum wr.wb