TEORI GRAPH

II. TEORI GRAPH

            A.Definisi Graph

      Suatu graph didefinisikan oleh himpunan verteks dan himpunan sisi (edge). Verteks menyatakan entitas-entitas data dan sisi menyatakan keterhubungan antara verteks. Biasanya untuk suatu graph G digunakan notasi matematis.

                                                  G = (V, E)

      Dimana :        G = Graph

                              V = Simpul atau Vertex, atau Node, atau Titik

                              E = Busur atau Edge, atau arc

V adalah himpunan verteks dan E himpunan sisi yang terdefinisi antara pasangan-pasangan verteks. Sebuah sisi antara verteks x dan y ditulis {x, y}. Suatu graph H = (V1, E1) disebut subgraph dari graph G jika V1 adalah himpunan bagian dari V dan E1 himpunan bagian dari E.

Cara pendefinisian lain untuk graph adalah dengan menggunakan himpunan keterhubungan langsung Vx. Pada setiap verteks x terdefinisi Vx sebagai himpunan dari verteks-verteks yang adjacent dari x. Secara formal:

Vx = {y | (x,y) -> E}

Dalam digraph didefinisikan juga terminologi-terminologi berikut ini. Predesesor dari suatu verteks x (ditulis Pred(x)) adalah himpunan semua verteks yang adjacent ke x. Suksesor dari verteks x (ditulis Succ(x)) adalah himpunan semua verteks yang adjacent dari x, yaitu adjacenct set di atas.

Struktur data yang berbentuk network/jaringan, hubungan antar elemen adalah many-to-many. Contoh dari graph adalah informasi topologi jaringan dan keterhubungan antar kota-kota. Keterhubungan dan jarak tidak langsung antara dua kota sama dengan data keterhubungan langsung dari kota-kota lainnya yang memperantarainya. Penerapan struktur data linear atau hirarkis pada masalah graph dapat dilakukan tetapi kurang efisien. Struktur data graph secara eksplisit menyatakan keterhubungan ini sehingga pencariannya langsung (straight forward) dilakukan pada strukturnya sendiri.

1.     1.    Struktur Data Linear = keterhubungan sekuensial antara entitas data

2.     2.    Struktur Data Tree = keterhubungan hirarki

3.                 Struktur Data Graph = keterhubungan tak terbatas antara entitas data. 

              Representasi Graph dalam Bentuk Matrik

               a. Graph Tak Berarah

Graf tersebut dapat direpresentasikan dalam sebuah matrik 5x5 , dimana baris dan kolom di matriks tersebut menunjukan vertex yang ada.

         b. Graph Berarah

Dalam matrik diatas dapat kita lihat bahwa kotak yang berisi angka satu menunjukan bahwa dalam dua vertex tersebut terdapat edge yang menghubungkannya. Dan jika dalam kotak terdapat angka nol, maka hal tersebut menandakan tidak ada edge yang mengubungkan secara langsung dua vertex tersebut.

Untuk representasi dalam pemorgraman komputer, graf tersebut dapat digambarkan seperti dibawah ini :