Pages

Thursday, November 15, 2007

Graph Thoery Algorithm

Graph teori ?? Mula2 baca tajuk ni memang konfius.. mula2 ingtakan macam graf biasa, ada paksi x paksi Y tapi bila baca2 rupa2 nya bukan macam tu .. abis tu ?macammana?

Graph teori salah satu cabang dalam matematik dimana , connection /edge (samaada logikal atau conceptual) antara node (Vertex) di modelkan dalam bentuk seperti berikut:

G = (V,E)
V = set vertices
E = set of edge

maksudnya , satu set graph terdiri daripada set of vertex (v)/node dan set of edge (e)
so senang ceritanya

contohnya jika 3 node yang bersambung antara satu sama lain , bolehlah ditulis seperti berikut:

G = (V,E)
E = { 1 ,2 ,3 }
V = { { 1,2} , { 2,3} , {1,3 } }

maksudnya: ada node 1 2 dan 3 , kemudian ada connection dari node 1 ke node 2 , node 2 ke node 3 dan node 1 ke node 3. Perhatikan perkataan "ke" disitu , Ini menunjukkan arah jika graph tersebut si assumekan sebagai directed graph , tapi jika graf tersebut adalah jenis yang tiada arah .. maka perkataan ke kat situ bolehlah ditukarkan kepada perkataan "dan"

Untuk menulis program berkaitan dengan Graph Theory ni yang penting ialah data structure yang perlu digunakan. Paling jelas ialah dengan menggunakan list atau linked list atau lagi jelas menggunakan teknik list didalam list. Teknik yang kediua ialah dengan menggunakan array untuk represent matrix , connection setiap node diwakili oleh nilai 1 manakala jika tiada connection diwakili oleh nilai 0?

dari segi praktikaliti , faktor yang penting (saya rasa la... ) untuk memilih jenis struktur data ialah 1. Programming Language, 2. Aplikasi yang hendak dibangunkan

dari segi programming language contohnya jika menggunakan MATLAB, cara matrix tentulah lebih elok sebab memang MATLAB terkenal untuk matrix calculation, tapi jika menggunakan TCL lebih elok menggunakan list memandangkan salah satu strengh TCL ialah dekat List dan String processing.

Okey .. tu dulu..

nak kena belajar banyak lagi nih..