Jumat, 26 November 2010

PENGERTIAN GRAF DALAM STRUKTUR DATA


Graf adalah :
·         4 Himpunan V (Vertex) yang elemennya disebut simpul (atau point atau node atau titik)
·         Himpunan E (Edge) yang merupakan pasangan tak urut  dari simpul, anggotanya disebut ruas (rusuk atau sisi)

Notasi : G(V,E)

Simpul u dan v disebut berdampingan bila terdapat ruas (u,v).
Graf dapat pula disajikan  secara geometrik,  simpul  disajika sebagai sebuah titik, sedangkan ruas disajikan sebagai sebua garis yang menghubungkan 2 simpul.

Contoh 1 :
Graf G(V,E) dengan :
1. V terdiri dari 4 simpul, yaitu simpul A, B, C dan D
2. E terdiri dari 5 ruas, yaitu e1 = (A, B)   e2 = (B, C)   e3 = (A, D e4 = (C, D)    e5 = (B, D)
                       
                        A                     e3                    D
 

               e1                                                          e4
                                                e5

                       
B                     e2                    C                    


Banyak simpul disebut ORDER, banyak ruas disebut SIZE dari graf.
Graf yang lebih umum disebut Multigraf
Contoh 2 :    
Graf G(V,E) dengan :
1.    V terdiri dari 4 simpul, yaitu simpul A, B, C dan D
2.    E terdiri dari 6 ruas, yaitu e1 = (A, C)    e2 = (A, A)    e3 = (A, D)
e4 = (C, D)    e5 = (B, C)     e6 = (B, C)

           
                        A   e2              e3                    D
 

                                                                             e4
                                                e1

                       
B                     e5                    C                    
                        e6


Di sini ruas e2 kedua titik ujungnya adalah simpul yang sama, yaitu simpul A, disebut Gelung atau Self-Loop. Sedangkan ruas e5 dan e6 mempunyai titik ujung yang sama, yaitu simpul B dan C, disebut Ruas Berganda atau Ruas Sejajar.
Suatu graf yang tidak mengandung ruas sejajar ataupun self-loop disebut Graf Sederhana atau Simple Graf.

Suatu graf G'CV'.E1) disebut subgraf dari G(V,E), jika V himpunan bagian dari V dan E' himpunan bagian dari E.
Jika E' mengandung semua ruas dari E yang titik ujungnya di V, maka  G'  disebut subgraf yang direntang  oleh  V  (Spanning subgraf).

Contoh :

            G

                        A                     e5                    D
 

               e1                                                          e4
                                                  e3

                       
B                     e2                    C                    


G’
G' subgraf dari G
(namun bukan dibentuk
olehV'^A.B.D})

 
 

                        A                                             D
 

               e1                                                          
                                                  e3

                       
B                                                                    



G’ subgraf yang dibentuk oleh V’ = (A,B,D)

                        A             e5                            D
 

               e1                                                         
                                                  e3

                       
B                                                                    


GRAF BERLABEL

Graf G disebut graf berlabel jika ruas dan atau simpulnya dikaitkan dengan suatu besaran tertentu. Jika setiap ruas e dari G dikaitkan dengan suatu bilangan non negatif d(e), maka d(e) disebut bobot atau panjang dari ruas e.


DERAJAT GRAF

Derajat simpul V, ditulis d(v) adalah banyaknya ruas yang rnenghubungi v. Karena setiap ruas dihitung dua kali ketika rnenentukan derajat suatu graf, maka:
Jumlah derajat semua simpul suatu graf (derajat) = dua kali banyaknya ruas graf (size graf).

Suatu simpul disebut genap/ganjil tergantung apakah derajat simpul tersebut genap/ganjil. Kalau terdapat self-loop, maka self-loop dihitung 2 kali pada derajat simpul.

                        A                     e5                    B                     F
 

               e1                                                          e4
                                                  e3

                       
C                     e2                    D                     E        


Di sini banyaknya ruas = 7, sedangkan derajat masing-masing simpul adalah:
d(A) = 2                      d(D) = 3                      derajat graf G = 14
d(B) = 5                      d(E) = 1                      ( 2 * 7 )
d(C) = 3                      d(F) = 0                     

Catatan : E disebut simpul bergantung/akhir, yakni simpul yang berderajat satu. Sedangkan F disebut simpul terpencil, yakni simpul berderajat riol.

KETERHUBUNGAN         

Walk atau perjalanan dalam graf G adalah barisan simpul dan ruas berganti-ganti: v1, e1, v2, e2, …. , en-1,vn
Di sini ruas 61 menghubungkan simpul vi dan vn+1

Banyaknya ruas disebut panj'ang walk.
Walk dapat ditulis lebih singkat dengan hanya menulis deretan ruas: e1, e2, …. , en-1,
atau deretan simpul :  v1, v2, …. , vn-1,vn
v1 disebut simpul awal, vn disebut simpul akhir

Walk disebut tertutup bila v1 = vn, dalam hal lain walk disebut terbuka, yang menghubungkan v1 dan vn

Trail adalah walk dengan semua ruas dalam barisan berbeda. Path atau jalur adalah walk dengan semua simpul dalam barisan berbeda. Jadi path pasti trail, sedangkan trail belum tentu path.

Dengan kata lain : Suatu path adalah suatu trail terbuka dengan deraj'at setiap simpulnya = 2, kecuali simpul awal v1 dan vn  simpul akhir berderajat = 1.
Cycle atau sirkuit adalah suatu trail tertutup dengan derajat setiap simpul = 2.

Contoh :

Graf yang tidak mengandung cycle disebut acyclic, contoh : pohon atau tree.
Suatu graf G disebut terhubung jika untuk setiap 2 simpul dari graf terdapat jalur yang menghubungkan 2 simpul tersebut.

Subgraf terhubung suatu graf disebut komponen dari G bila subgraf tersebut tidak terkandung dalam subgraf terhubung lain yang lebih besar.

Contoh : Graf G terdiri dari 3 komponen
           
                          B                                     C      D                              F
 






                                               
                                                A                                 E

Terlihat misalnya andara D dan A tidak ada jalur
Jarak antara  2  simpul  dalam  graf G  adalah  panjang jalur terpendek antara ke-2 simpul tersebut.
Diameter  suatu  graf terhubung G adalah maksimum jarak antara simpul-simpul G.
Contoh : Graf G (graf terhubung) terdiri dari 1 komponen C
                                    C                         E
 


  
               A                                D                         G




                                  B                          F
Jarak maksimum  dalam graf G adalah 3 (yaitu antara A - G atau B - G ataupun C - G). Jadi diameter = 3.

Kalau order dari G = n, size dari G = e, dan banyaknya komponen
= k, maka didefinisikan :
Rank(G) = n - k         Nullity(G) = e - (n - k)

MATRIKS PENYAJIAN GRAF

Pandang bahwa G graf dengan N simpul dan M ruas.

Untuk mempermudah komputasi, graf dapat disajikan dalam bentuk matriks, disebut Matriks Ruas, yang berukuran (2 x M) atau (M x 2) yang menyatakan ruas dari graf.

Matriks adjacency dari graf G tanpa ruas sejajar adalah matriks A berukuran (N x N), yang bersifat :
1, bila ada ruas ( Vi, Vj )
                 aij  =
0, dalam hal lain

Matriks adjacency merupakan matriks simetri.
Untuk graf dengan ruas sejajar, matriks adjacency didefinisikan sebagai berikut:

p, bila ada p buah ruas menghubungkan (Vj, Vj) (p > 0)
     aij  =
0, dalam hal lain

Matriks Incidence dari graf G, tanpa self-loop didefinisikan sebagai matriks M berukuran (N x M)

1, bila ruas 6j berujung di simpul Vj,
mij       
            0, dalam hal lain



Contoh :                   e5
                                               
                        v1                    e4                    v4    e8          v5
 

               e1                                                         
                                                     e2          e6     e7

                       
v2                    e3                    v3                   



  
1       2
1       3
1    4
1       5
2       3
3       4
3    5
4    5  
 
Matrik Ruas
 

1  1  1  1  2  3  3  4               atau
2  3  4  5  3  4  5  5







Matriks Adjacency  : N x N
v1   v2   v3   v4   v5
    v1           0    1    1    1    1    
    v2           1    0    1    0    0 
    v3           1    1    0    1    1 
    v4           1    0    1    0    1
    v5           1    0    1    1    0

Matriks Adjacency  : N x N
e1   e2   e3   e4   e5   e6   e7   e8
    v1            1    1    0    1    1      0     0    0    
    v2            1    0    1    0    0     0     0    0   
    v3            0    1    1    0    0     1     1    0
    v4            0    0    0    1    0      1     0    1
    v5            0    0    0    0    1      0     1    1










GRAF BERARAH (DIGRAF)

Suatu graf berarah (digraf) D terdiri atas 2 himpunan :
1     Himpunan \l', anggotanya disebut simpul
2     Himpunan A, merupakan himpunan pasangan terurut, yang disebut  ruas berarah atau arkus.

Notasi: D(V, A)

Simpul, anggota v, digambarkan sebagai titik (atau lingkarai kecil). Sedangkan arkus a=(u,v), digambarkan sebagai garii dilengkapi dengan tanda panah mengarah dari simpul u ke simpii v. Simpul u disebut titik pangkal, dan simpul v disebut titik termina dari arkus tersebut.


Tidak ada komentar:

Posting Komentar