Minggu, 04 Desember 2011

SEJARAH GRAPH

http://sejarahgraph.blogspot.com/2011/04/sejarah-graph_11.html
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:
–  = himpunan tidak - kosong dari simpul-simpul (vertices) = { v1 , v2 , ... , vn }, dan
–  = 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 G2, sisi E3 = (1,3) dan sisi E4 = (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 bertetanggabila keduanya terhubung langsung.
  • Simpul terpencil adalah simpul yang tidak mempunyai sisi yang bersisian dengannya. 
  • Graf  Kosong adalah graf yang himpunan sisinya merupakan himpunan kosong (Nn). 
  • 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 v1 dan simpul v2 disebut terhubung jika terdapat lintasan dari v1. Graf berarah Gdikatakan 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 vdan juga lintasan berarah dari v ke u. Jika u dan v tidak terhubung kuat tetapi terhubung pada graf tidak berarahnya, maka u dan dikatakan terhubung lemah (weakly coonected).
    Graf berarah G disebut graf terhubung kuat (strongly connected graph) apabila untuk setiap pasang simpul sembarangu dan v di G, terhubung kuat. Kalau tidak, G disebut graf terhubung lemah.
  • Upagraf dan Komplomen Upagraf                                                             Komplemen dari upagraf G1 terhadap graf G adalah graf G2 = (V2E2) sedemikian sehingga E2 = E - E1 dan V2 adalah himpunan simpul yang anggota-anggota E2 bersisian dengannya.Komponen graf (connected component) adalah jumlah maksimum upagraf terhubung dalam graf G.
  • UpagrafRentang                                                                                                      Upagraf G= (V1E1) dari G = (VE) dikatakan upagraf rentang jika V=V (yaitu G1 mengandung semua simpul dari G). 
  • Cut - Set  adalah adalah himpunan sisi yang bila dibuang dari Gmenyebabkan 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-setsebab 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, nberhingga.
2. Graf tak-berhingga (unlimited graph)
    Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebutgraf 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)
            din(v) = derajat-masuk (in-degree)
          = jumlah busur yang masuk ke simpul  v

            dout(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 = (VE), maka :
Tinjau graf G1:  d(1) + d(2) + d(3) + d(4) = 2 + 3 + 3 + 2 = 10
                                                               = 2 ´ jumlah sisi = 2 ´ 5
Tinjau graf G2:  d(1) + d(2) + d(3) = 3 + 3 + 4 = 10
                                           = 2 ´ jumlah sisi = 2 ´ 5
Tinjau graf G3:  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 v0 ke simpul tujuan vndi dalam graf G ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v0e1v1e2v2,... , vn –1envn sedemikian sehingga e1 = (v0v1), e2 = (v1v2), ... , en = (vn-1vn) adalah sisi-sisi dari graf G.
            Tinjau graf G1: 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 G1 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 Kn. 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 Cn. 
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 V1 dan V2,  sedemikian sehingga setiap sisi pada Gmenghubungkan sebuah simpul di V1 ke sebuah simpul di V2 disebut graf bipartit dan dinyatakan sebagai G(V1V2). 

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)    : acf,  ecbde,adfba
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, Gdan G2 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 udan v di G1, maka sisi e’ yang berkoresponden di G2 harus bersisian dengan simpul u’ dan v’ yang di G2.
·         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.

Tidak ada komentar:

Posting Komentar