TUGAS TEORI GRAPH

TEORI GRAPH

Dalam matematika dan ilmu komputer, teori graf adalah cabang kajian yang mempelajari sifat-sifat graf. Secara informal, suatu graf adalah himpunan benda-benda yang disebut simpul (vertex atau node) yang terhubung oleh sisi (edge) atau busur (arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan simpul) yang dihubungkan oleh garis-garis (melambangkan sisi) atau garis berpanah (melambangkan busur). Suatu sisi dapat menghubungkan suatu simpul dengan simpul yang sama. Sisi yang demikian dinamakan gelang (loop).

Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan bantuan graf. Jaringan persahabatan pada Friendster bisa direpresentasikan dengan graf: simpul-simpulnya adalah para pemakai Friendster dan ada sisi antara A dan B jika dan hanya jika A berteman (berkoinsidensi) dengan B. Perkembangan algoritma untuk menangani graf akan berdampak besar bagi ilmu komputer.

Sebuah struktur graf bisa dikembangkan dengan memberi bobot pada tiap sisi. Graf berbobot dapat digunakan untuk melambangkan banyak konsep berbeda. Sebagai contoh jika suatu graf melambangkan jaringan jalan maka bobotnya bisa berarti panjang jalan maupun batas kecepatan tertinggi pada jalan tertentu. Ekstensi lain pada graf adalah dengan membuat sisinya berarah, yang secara teknis disebut graf berarah atau digraf (directed graph). Digraf dengan sisi berbobot disebut jaringan.

Jaringan banyak digunakan pada cabang praktis teori graf yaitu analisis jaringan. Perlu dicatat bahwa pada analisis jaringan, definisi kata "jaringan" bisa berbeda, dan sering berarti graf sederhana (tanpa bobot dan arah).

Gambar yang menunjukkan suatu graf dengan 6 simpul dan 7 sisi.

sumber : http://id.wikipedia.org/wiki/Graf

SEJARAH GRAF
       Menurut catatan sejarah, masalah jembatan Königsberg adalah masalah yang pertama kali menggunakan graf (tahun 1736).  Di kota Königsberg (sebelah timur Prussia, Jerman sekarang), sekarang bernama kota Kaliningrad, terdapat sungai Pregal yang mengalir mengitari pulau Kneiphof  lalu  bercabang menjadi dua buah anak sungai.

(a)                                          (b)

Gambar  (a) Jembatan Königsberg [ROS99], dan (b) graf yang merepresentasikan jembatan Königsberg

Ada tujuh buah jembatan yang menghubungkan daratan yang dibelah oleh sungai tersebut (Gambar (a)). Masalah jembatan Königsberg adalah: apakah mungkin melalui ketujuh buah jembatan itu masing-masing tepat satu kali, dan kembali lagi ke tempat semula? Sebagian penduduk kota sepakat bahwa memang tidak mungkin melalui setiap jembatan itu hanya sekali dan kembali lagi ke tempat asal mula keberangkatan, tetapi mereka tidak dapat menjelaskan mengapa demikian jawabannya, kecuali dengan cara coba-coba.

Tahun 1736, seorang matematikawan Swiss, L.Euler, adalah orang pertama yang berhasil menemukan jawaban masalah itu dengan pembuktian yang sederhana. Ia memodelkan masalah ini ke dalam graf. Daratan (titik- titik yang dihubungkan oleh jembatan) dinyatakannya sebagai titik (noktah) –yang disebut simpul (vertex)- dan jembatan dinyatakan sebagai garis –yang disebut sisi (edge). Setiap titik diberi label huruf A, B, C, dan D. Graf yang dibuat oleh Euler diperlihatkan pada Gambar (b).

DEFINISI GRAF

      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.

sumber : http://protokol-gallery.blogspot.com/2010/12/teori-graph.html

JENIS – JENIS GRAF

•   Berdasarkan  ada  tidaknya  gelang  atau  sisi  ganda  pada  suatu  graf,  maka  graf digolongkan menjadi dua jenis:

1. Graf sederhana (simple graf).

Graf  yang  tidak  mengandung  gelang  maupun  sisi-ganda  dinamakan  graf sederhana.

2. Graf tak-sederhana (unsimple-graf/multigraf).

Graf yang mengandung ruas ganda atau gelung dinamakan  graf tak-sederhana

(unsimple graf atau multigrapf).

•   Berdasarkan  jumlah  simpul  pada  suatu  graf,  maka  secara  umum  graf  dapat digolongkan menjadi dua jenis:

 1. Graf berhingga (limited graf)

     Graf berhingga adalah graf yang jumlah simpulnya, n, berhingga.

2. Graf tak-berhingga (unlimited graf)

    Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graf tak- berhingga.

•   Berdasarkan orientasi arah pada sisi, maka secara umum graf  dibedakan atas 2 jenis:

1.  Graf tak-berarah (undirected graf)
    Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah.


2.  Graf berarah (directed graf atau digraf)

   Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Dua buah graf pada Gbr 3 adalah graf berarah.

          TERMINOLOGI GRAF

             Graf  G1               Graf  G2                           Graf G3

graf G1       : d(1) = d(4) = 2

d(2) = d(3) = 3

graf G3       : d(5) = 0    Æ simpul terpencil / simpul terisolasi

d(4) = 1    Æ simpul bergantung / simpul akhir

graf G2       : d(1) = 3     Æ bersisian dengan ruas ganda

d(3) = 4    Æ bersisian dengan self-loop (derajat sebuah self-loop = 2)

1. Ketetanggaan (Adjacent)

Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.

Tinjau graf G₁ : simpul 1 bertetangga dengan simpul 2 dan 3,
                        simpul 1 tidak bertetangga dengan simpul 4.

2. Bersisian (Incidency)

Untuk sembarang sisi e = (v_j, v_k) dikatakan

          e bersisian dengan simpul v_j , atau

          e bersisian dengan simpul v_k

Tinjau graf G₁: sisi (2, 3) bersisian dengan simpul 2 dan simpul 3,

    sisi (2, 4) bersisian dengan simpul 2 dan simpul 4,

 tetapi sisi (1, 2) tidak bersisian dengan simpul 4.

3. Simpul Terpencil (Isolated Vertex)

Simpul terpencil ialah simpul yang tidak mempunyai sisi yang bersisian dengannya. Tinjau graf G₁: simpul 5 adalah simpul terpencil.

4. Graf  Kosong (null graph atau empty graph)

Graf yang himpunan sisinya merupakan himpunan kosong (N_n). 

Graf N6 :

Null Graph

5. Derajat (Degree)

Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut. Notasi: d(v)

Tinjau graf G₁:  d(1) = d(4) = 2

                            d(2) = d(3) = 3

Tinjau graf G₃:  d(5) = 0    à simpul terpencil

  d(4) = 1    à simpul anting-anting (pendant vertex)

Tinjau graf G₂: d(1) = 3     à bersisian dengan sisi ganda        

                            d(2) = 4     à bersisian dengan sisi gelang (loop)      

Pada graf berarah,

          d_in(v)    = derajat-masuk (in-degree)

           = jumlah busur yang masuk ke simpul v

          d_out(v)   = derajat-keluar (out-degree)

= jumlah busur yang keluar dari simpul v

          d(v) = d_in(v) + d_out(v)                 

Tinjau graf G₄:

           d_in(1) = 1; d_out(1) = 1

                       d_in(2) = 1; d_out(2) = 3

           d_in(3) = 1; d_out(3) = 1

                       d_in(4) = 2; d_out(3) = 0

 6. Lemma Jabat Tangan. 
    Jumlah derajat semua simpul pada suatu graf adalah genap, yaitu dua kali  jumlah sisi pada graf tersebut. Dengan kata lain, jika G = (V, E), maka

                                                        

Tinjau graf G₁:  d(1) + d(2) + d(3) + d(4) = 2 + 3 + 3 + 2 = 10  = 2 ´ jumlah sisi = 2 ´ 5

Tinjau graf G₂:  d(1) + d(2) + d(3) = 3 + 3 + 4 = 10 = 2 ´ jumlah sisi = 2 ´ 5

Tinjau graf G₃:  d(1) + d(2) + d(3) + d(4) + d(5) = 2 + 2 + 3 + 1 + 0 = 8  

                                                                          = 2 ´ jumlah sisi  = 2 ´ 4

 Contoh. Diketahui graf dengan lima buah simpul. Dapatkah kita menggambar graf tersebut jika derajat masing-masing simpul adalah:

          (a) 2, 3, 1, 1, 2

          (b) 2, 3, 3, 4, 4

Penyelesaian:     

(a) tidak dapat, karena jumlah derajat semua simpulnya ganjil

 (2 + 3 + 1 + 1 + 2 = 9).

(b) dapat, karena          jumlah derajat semua simpulnya genap

       (2 + 3 + 3 + 4 + 4 = 16).

7. Lintasan (Path)

Lintasan yang panjangnya n dari simpul awal v₀ ke simpul tujuan v_n di dalam graf G ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v₀, e₁, v₁, e₂, v₂,... , v_{n –1}, e_n, v_n sedemikian sehingga e₁ = (v₀, v₁), e₂ = (v₁, v₂), ... , e_n = (v_n-1, v_n) adalah sisi-sisi dari graf G.

Tinjau graf G₁: lintasan 1, 2, 4, 3 adalah lintasan dengan barisan sisi (1,2), (2,4), (4,3).

Panjang lintasan adalah jumlah sisi dalam lintasan tersebut. Lintasan 1, 2, 4, 3 pada G₁ memiliki panjang 3.

8. Siklus (Cycle) atau Sirkuit (Circuit)

Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atau siklus.

Tinjau graf G₁: 1, 2, 3, 1 adalah sebuah sirkuit.

Panjang sirkuit adalah jumlah sisi dalam sirkuit tersebut. Sirkuit 1, 2, 3, 1 pada G₁ memiliki panjang 3.

9. Terhubung (Connected)

Dua buah simpul v₁ dan simpul v₂ disebut terhubung jika terdapat lintasan dari v₁ ke v₂.

G disebut graf terhubung (connected graph) jika untuk setiap pasang simpul v_i dan v_j dalam himpunan V terdapat lintasan dari v_i ke v_j.

Jika tidak, maka G disebut graf tak-terhubung (disconnected graph).

Contoh graf tak-terhubung:

Graf berarah G dikatakan terhubung jika graf tidak berarahnya terhubung (graf tidak berarah dari G diperoleh dengan menghilangkan arahnya).

Dua simpul, u dan v, pada graf berarah G disebut terhubung kuat (strongly connected) jika terdapat lintasan berarah dari u ke v dan juga lintasan berarah dari v ke u.

Jika u dan v tidak terhubung kuat tetapi terhubung pada graf tidak berarahnya, maka u dan v dikatakan terhubung lemah (weakly coonected).

Graf berarah G disebut graf terhubung kuat (strongly connected graph) apabila untuk setiap pasang simpul sembarang u dan v di G, terhubung kuat. Kalau tidak, G disebut graf terhubung lemah.

                                              graf  berarah terhubung lemah                     graf berarah terhubung kuat

REPRESENTASI 

1. Matriks Ketetanggaan (adjacency matrix)

A = [a_ij],

                                1, jika simpul i dan j bertetangga  

                     a_ij = {       

                                0, jika simpul i dan j tidak bertetangga   

                                     

Contoh:

2. Matriks Bersisian (incidency matrix)

A = [a_ij],

                             1,    jika simpul i bersisian dengan sisi j   

                   a_ij = {

                              0,   jika simpul i tidak bersisian dengan sisi j

3. Senarai Ketetanggaan (adjacency list)

Simpul	Simpul Tetangga		Simpul	Simpul Tetangga		Simpul	Simpul Terminal
1	2, 3		1	2, 3		1	2
2	1, 3, 4		2	1, 3		2	1, 3, 4
3	1, 2, 4		3	1, 2, 4		3	1
4	2, 3		4	3		4	2, 3
			5	-