Pengenalan Graph

 

Graph pada awalnya digunakan untuk memecahkan masalah jembatan Konigsberg pada tahun 1763 di Swiss oleh Matematikawan Swiss bernama L.Euler.

Graph sendiri merupakan pasangan himpunan (V,E). Teori graph merupakan pokok bahasan yang sudah tua usianya namun memiliki banyak terapan sampai saat ini.

        V - Himpunan tidak kosong dari simpul-simpul(titik atau verticles atau node)

        E – Himpunan sisi(ruas/sisi/edges/arcs) yang menghubungkan sepasang simpul.

Dalam notasi matematika,graph dapat ditulis dengan :

G – (V,E)

Contoh Graph

Contoh :

V = (A1,A2,A3,A4,A5)  

E = {(A1,A4),(A1,A2),(A2,A3),(A3,A5)}

Degree dari A1 , deg(A1) = 2

 Degree merupakan banyaknya ruas yang menghubungi simpul tersebut.

 A1 terhubung dengan A2 dan A4.

Cardinality , |G| = 5

 Cardinality merupakan jumlah simpul.

                       

 Adjecemy List

A1 : A2,A4

A2 : A1,A3,

A3 : A5,A2

A4 : A1

A5 : A3

 Adjecemy List merupakan list dari simpul yang terhubung dengan satu simpul.

Graph diatas merupakan graph tree, dimana biasanya digunakan di pencarian. Dimana salah satu cara menuju A5 dari A1 adalah melalui A3 dan A2, begitupun sebaliknya. Beda halnya dengan Graph sirkuit.  

 

Jenis Graph

Berdasarkan ada tidaknya sisi ganda pada suatu graph, graph digolongkan menjadi :

1.      Graph Sederhana

Graph yang tidak mengandung sisi ganda.

2.      Graph Tak-Sederhana

Graph yang mengandung ruas ganda.

Berdasarkan jumlah simpul suatu graph, graph digolongkan menjadi  :

1.      Graph berhingga

Graph yang simpulnya n atau terdefinisi.

2.      Graph tak-berhingga

Graph yang jumlah simpulnya tak berhingga.

Berdasarkan orientasi arah pada sisi, maka graph dibedakan menjadi :

1.      Graph tak-berarah

Graph yang tidak mempunyai orientasi arah.

2.      Graph berarah

Graph yang setiap sisinya diberikan orientasi arah disebut graph berarah.

Referensi : patrickJMT

Adj

Author & Editor

Silahkan Copy Paste Tapi Cantumin Link Sumber Ya kk (^3^) Ok | Kalo Gak Tak Tabok (---)p