Arsiy

Arsiy

Follow

Sabtu, 01 Mei 2010

graph

Graph merupakan struktur data yang paling umum. Jika struktur linear memungkinkan pendefinisian keterhubungan sikuensial antara entitas data, struktur data tree memungkinkan pendefinisian keterhubungan hirarkis, maka struktur graph memungkinkan pendefinisian keterhubungan tak terbatas antara entitas data.
Banyak entitas-entitas data dalam masalah-masalah nyata secara alamiah memiliki keterhubungan langsung (adjacency) secara tak terbatas demikian. Contoh: informasi topologi dan jarak antar kota-kota di pulau Jawa. Dalam masalah ini kota x bisa berhubungan langsung dengan hanya satu atau lima kota lainnya. Untuk memeriksa keterhubungan dan jarak tidak langsung antara dua kota dapat diperoleh berdasarkan data keterhubungan-keterhubungan langsung dari kota-kota lainnya yang memperantarainya.
Representasi data dengan struktur data linear ataupun hirarkis pada masalah ini masih bisa digunakan namun akan membutuhkan pencarian-pencarian yang kurang efisien. Struktur data graph secara eksplisit menyatakan keterhubungan ini sehingga pencariannya langsung (straightforward) dilakukan pada strukturnya sendiri.

Definisi

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)
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.

Digraph & Undigraph

Graph Berarah (directed graph atau digraph): jika sisi-sisi pada graph, misalnya {x, y} hanya berlaku pada arah-arah tertentu saja, yaitu dari x ke y tapi tidak dari y ke x; verteks x disebut origin dan vertex y disebut terminus dari sisi tersebut. Secara grafis maka penggambaran arah sisi-sisi digraph dinyatakan dengan anak panah yang mengarah ke verteks terminus, secara notasional sisi graph berarah ditulis sebagai vektor dengan (x, y).
sumber : http://www.cs.ui.ac.id/WebKuliah/IKI10100/1998/handout/handout19.html

Tidak ada komentar:

Poskan Komentar