GRAF

GRAPH

Sejarah Graf

         Penemu graf adalah L. Euler ( Leonhard Euler ). Graf ditemukan disebuah jembatan Königsberg (tahun1736). Di kota Königsberg (sebelah timur negara bagian Prussia, Jerman), yang sekarang bernama kota Kaliningrad, terdapat sungai Pregal yg mengalir mengintari pulau Kneiphof lalu bercabang menjadi dua buah anak sungai. Ada 7 buah jembatan yg menghubungkan daratan yg dibelah oleh sungai tersebut. Sejarah Graf : masalah jembatan Königsberg (tahun 1736)

Graf yang merepresentasikan jembatan Königsberg:

                        Simpul (vertex)            à menyatakan daratan

              Sisi (edge)                    à menyatakan jembatan

Definisi Graf

        Graf merupakan sebagai pasangan himpunan (V, E), ditulis dengan notasi G = (V,   E), yang dalam hal ini:

– V  = himpunan tidak - kosong dari simpul-simpul (vertices) = { v1 , v2 , ... , vn }, dan

– E  = himpunan sisi (edges) yang mnghubungkan sepasang simpul = {e1 , e2 , ... , en }

        Definisi diatas mengatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong.

Jadi sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpulnya harus ada.

Unsur  - Unsur dari Graf

• Simpul (Vertex) adalah daratan ( titik - titik yg dihubungkan oleh jembatan ), yang dinyatakan sebagai titik (noktah). 
• Sisi (Edge) adalah jembatan yang dinyatakan sebagai garis.
• Garis Paralel adalah pada G_2, sisi E₃ = (1,3) dan sisi E₄ = (1,3) dinamakan sisi ganda.

Komponen Graf

• Alur adalah setiap lintasan yang semua titik simpul berbeda satu sama lain kecuali titik awal dan titik akhirnya.
•  Panjang adalah banyak sisi / lintasan yang ditempuh.
•  Derajat adalah jumlah rusuk atau sisi yang menuju satu titik simpul.
• Titik terasing adalah titik yang tidak memiliki garis penghubung / jalan.
•  Jalan tapak adalah suatu lintasan yang tidak memiliki dua rusuk yang sama.
•  Ketetanggan adalah dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.
• Simpul terpencil adalah simpul yang tidak mempunyai sisi yang bersisian dengannya. 
• Graf  Kosong adalah graf yang himpunan sisinya merupakan himpunan kosong (N_n). 
• Siklus atau sirkuit adalah lintasan yang berawal dan berakhir pada simpul yang sama.
• Panjang sirkuit adalah jumlah sisi dalam sirkuit tersebut. 
• Terhubung adalah dua buah simpul v₁ dan simpul v₂ disebut terhubung jika terdapat lintasan dari v₁. Graf berarah G dikatakan terhubung jika graf tidak berarahnya terhubung (graf tidak berarah dari Gdiperoleh 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.

• Upagraf dan Komplomen Upagraf                                                              Komplemen dari upagraf G₁ terhadap graf G adalah graf G₂ = (V₂, E₂) sedemikian sehingga E₂ = E - E₁ dan V₂ adalah himpunan simpul yang anggota-anggota E₂ bersisian dengannya.Komponen graf (connected component) adalah jumlah maksimum upagraf terhubung dalam graf G.
• UpagrafRentang                                                                                                      Upagraf G₁ = (V₁, E₁) dari G = (V, E) dikatakan upagraf rentang jika V₁ =V (yaitu G₁ mengandung semua simpul dari G). 
• Cut - Set  adalah adalah himpunan sisi yang bila dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen. 
  Contoh : 
  Pada graf di bawah, {(1,2), (1,5), (3,5), (3,4)} adalah cut-set. Terdapat banyak cut-set pada sebuah graf terhubung. Himpunan {(1,2), (2,5)} juga adalah cut-set, {(1,3), (1,5), (1,2)} adalah cut-set, {(2,6)} juga cut-set, tetapi {(1,2), (2,5), (4,5)} bukan cut-set sebab himpunan bagiannya, {(1,2), (2,5)} adalah cut-set.
• Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot).

Jenis - Jenis Graf

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

1. Graf sederhana (simple graph).

Graf yang tidak mengandung gelang maupun sisi ganda dinamakan graf sederhana. G1 pada contoh graf sederhana.

2. Graf tak-sederhana (unsimple-graph).

Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph). G2 dan G3 pada contoh adalah graf tak-sederhana.

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

1. Graf berhingga (limited graph)

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

2. Graf tak-berhingga (unlimited graph)

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

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

1. Graf tak-berarah (undirected graph)

Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. Tiga buah graf     pada contoh a,b,dan c adalah graf tak-berarah.

2. Graf berarah (directed graph atau digraph)

    Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah.

     Pada graf berarah notasi : d(v)

            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

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

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.

Beberapa Graf Sederhana Khusus

a. Graf Lengkap

Graf lengkap ialah graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya. Graf lengkap dengan n buah simpul dilambangkan dengan K_n. Jumlah sisi pada graf lengkap yang terdiri dari n buah simpul adalah n(n – 1)/2.

b. Graf Lingkaran  

            Graf lingkaran adalah graf sederhana yang setiap simpulnya berderajat dua. Graf lingkaran dengan n simpul dilambangkan dengan C_n.  

c. Graf Teratur

              Graf yang setiap simpulnya mempunyai derajat yang sama disebut graf teratur. Apabila derajat setiap simpul adalah r, maka graf tersebut disebut sbagai graf teratur derajat r.

d. Graf Bipartite

Graf G yang himpunan simpulnya dapat dipisah menjadi dua himpunan bagian V₁ dan V₂,  sedemikian sehingga setiap sisi pada G menghubungkan sebuah simpul di V₁ ke sebuah simpul di V₂ disebut graf bipartit dan dinyatakan sebagai G(V₁, V₂). 

Macam - Macam Graf

A.  Graf Euler

Lintasan Euler ialah lintasan yang melalui masing-masing sisi di dalam graf tepat satu kali. Sirkuit Euler ialah sirkuit yang melewati masing-masing sisi tepat satu kali.Graf yang mempunyai sirkuit Euler disebut graf Euler (Eulerian graph).

Graf yang mempunyai lintasan Euler dinamakan juga graf semi-Euler (semi-Eulerian graph)

Contoh : Lintasan Euler pada graf Gambar 6.42(a) : 3, 1, 2, 3, 4, 1

    Lintasan Euler pada graf Gambar 5.42(b) : 1, 2, 4, 6, 2, 3, 6, 5, 1, 3

    Sirkuit Euler pada graf Gambar 6.42(c)    : 1, 2, 3, 4, 7, 3, 5, 7, 6, 5, 2, 6, 1

    Sirkuit Euler pada graf Gambar 6.42(d)    : a, c, f,  e, c, b, d, e, a, d, f, b, a

Graf (e) dan (f) tidak mempunyai lintasan maupun sirkuit Euler.

B.  Graf Hamilton

  Lintasan Hamilton ialah lintasan yang melalui tiap simpul di dalam graf tepat satu kali.

Sirkuit Hamilton ialah sirkuit yang melalui tiap simpul di dalam graf tepat satu kali, kecuali simpul asal (sekaligus simpul akhir) yang dilalui dua kali.Graf yang memiliki sirkuit Hamilton dinamakan graf Hamilton, sedangkan graf yang hanya memiliki lintasan Hamilton disebut graf semi-Hamilton.

C.  Graf Isomorfik

·         Dua buah graf yang sama tetapi secara geometri berbeda disebut graf yang   saling         isomorfik. 

·         Dua buah graf, G₁ dan G₂ dikatakan isomorfik jika terdapat korespondensi satu-satu antara simpul-simpul keduanya dan antara sisi-sisi keduaya sedemikian sehingga hubungan kebersisian tetap terjaga.

·         Dengan kata lain, misalkan sisi e bersisian dengan simpul u dan v di G₁, maka sisi e’ yang berkoresponden di G₂ harus bersisian dengan simpul u’ dan v’ yang di G₂.

·         Dua buah graf yang isomorfik adalah graf yang sama, kecuali penamaan simpul dan sisinya saja yang berbeda.  Ini benar karena sebuah graf dapat digambarkan dalam banyak cara

sumber :www.google.com