Sabtu, 16 April 2011

MATEMATIKA DISKRIT


PEMBAHASAN
  1. Kerangka Teoritis
1.      Sejarah Graf
Tulisan pertama tentang teori graf adalah karya Leonard Euler pada tahun  1976. Tulisan tersebut  menyajukan sebuah teori umum yang menyertakan sebuahh solusi yang sekarang disebut masalah jembatan Konisberg.








Dua pulau terhampar disungai Pregel yang terletak dikota Konisberg (sekarang kuliningrat di Rusia) saling terhubung oleh jembata-jembatan, seperti yang di perlihatkan pada gambar  di bawah ini.
(a)    Konigsberg in 1736                                  
 (b)Euler’s graphical representation
Gambar 2.1 dua pulau dan tujuh jembatan dikota Konisberg
Masalahnya pada gambar (a) adalah untuk memulai dari sembarang lokasi  A,B,C dan D menyeberangi di setiap jembatan satu kali kemudian kembali lagi pada tempat semula. Orang-orang konisberg menuliskan kepada ahli matematika swiss, L.Euler mengenai peryanyaan ini. Euler membuktikan pada tahun 1736 bahwa perjalanan seperti itu adalah suatu yang tidak mungkin dilakukan.
Dia menempatkan kembali pulau-pulau dan dua sisi suangai dengan titik-titik, dan jembatan-jembatan dengan kurva seperti pada gambar (b). Konfigurasi jembatan dapat dimodelkan sebagai sebuah graf seperti yang di perlihatkan digambar (b). vertex-verteks mewakili lokasi  dan rusuk-rusuk mewakili jembatan. Masalah jembatan kosisberg sekarang di sederhanakan untuk mencari di sebuah siklus dalam graf dari gambar (b) yang menyertakan semua rusuk dan semua vertex. Untuk menghormati Euler, sebuah siklus dalam sebuah graf G yang menyertakan semua rusuk dari G di sebut siklus Euler.

2.      Konsep Dasar Graf
Menurut Rinaldi Munir (2003:291) dalam bukunya matematika Diskrit Graf G = (V, E), yang dalam hal ini:
     V  = himpunan tidak-kosong dari simpul-simpul (vertices)
= { v1 , v2 , ... , vn }
     E = himpunan sisi  (edges) yang menghubungkan sepasang  simpul.
= {e1 , e2 , ... , en }
V  titak boleh kosong, sedangkan E boleh kosong. Se buah graf di mungkinkan ttidak mempunyai satu buah simpul (vertek) tanpa satu buah pun dinamakan graft rival. Simpul (vertex) pada graf dapat dinomori dengan huruf seperti a,b,c, … dengan bilangn asli 1,2,3 … atau gabungan keduanya. Sedangkan sisi (edge) yang menghubungkan simpul (vertex) dinyatakan pasangan atau dengan lambang e1 , e2 , ... , en



Secara Geometri graf dapat digambarkan sebagai kumpulan simpul (vertek) di dalam bidang yang menghubungkan dengan sekumpulan sisi (edge)

         G1                                   G2                                    G3
Gambar 2.  (a) graf sederhana,  (b) graf ganda, dan      (c) graf semu
Contoh 1. Pada Gambar 2, G1 adalah graf dengan
V = { 1, 2, 3, 4 }
            E =  { (1, 2), (1, 3), (2, 3), (2, 4), (3, 4) }
G2 adalah graf dengan
V = { 1, 2, 3, 4  }
E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4) } = { e1, e2, e3, e4, e5, e6, e7}
G3 adalah graf dengan
V = { 1, 2, 3, 4  }
E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3) }
= { e1, e2, e3, e4, e5, e6, e7, e8}                                                                                
  • Pada G2, sisi  e3 = (1, 3) dan sisi e4 = (1, 3) dinamakan sisi-ganda (multiple edges atau paralel edges) karena kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul 1 dan simpul 3.
  • Pada G3, sisi e8 = (3, 3) dinamakan gelang atau kalang (loop) karena ia berawal dan berakhir pada simpul yang sama.

3.      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 Gambar 2 adalah 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 Gambar 2 adalah contoh 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 tak-berhingga.
Berdasarkan orientasi arah pada sisi, maka secara umum graf  dibedakan atas 2 jenis:
      1.  Graf tak-berarah (undirected graph)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. Tiga buah graf pada Gambar 2 adalah graf tak-berarah.
    2.  Graf berarah (directed graph atau digraph)



            Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Dua buah graf pada Gambar 3 adalah graf berarah.
                            (a) G4                       (b) G5
Gambar 3  (a) graf berarah,             (b) graf-ganda berarah

Tabel 1 Jenis-jenis graf [ROS99]
Jenis
Sisi
Sisi ganda dibolehkan?
Sisi gelang dibolehkan?
Graf sederhana
Graf ganda
Graf semu
Graf berarah
Graf-ganda berarah
Tak-berarah
Tak-berarah
Tak-berarah
Bearah
Bearah
Tidak
Ya
Ya
Tidak
Ya
Tidak
Tidak
Ya
Ya
Y
     



4. Terminologi Graf
                        G1                                G2                                            G3
Gambar 4. Graf yang digunakan untuk menjelaskan terminologi pada graf
1. Ketetanggaan (Adjacent)
Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.
Tinjau graf G1 : simpul 1 bertetangga dengan simpul 2 dan 3,
     simpul 1 tidak bertetangga dengan simpul 4.
2. Bersisian (Incidency)
Untuk sembarang sisi e = (vj, vk) dikatakan
            e bersisian dengan simpul vj , atau
            e bersisian dengan simpul vk
Tinjau graf G1: 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 G1: simpul 5 adalah simpul terpencil.
4. Graf  Kosong (null graph atau empty graph)



Graf yang himpunan sisinya merupakan himpunan kosong (Nn).
Graf N5. Gambar 5
5. Derajat (Degree)
Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut.
Notasi: d(v)
Tinjau graf G1:
            d(1) = d(4) = 2
                        d(2) = d(3) = 3
Tinjau graf G3: d(5) = 0    à simpul terpencil
       d(4) = 1    à simpul anting-anting (pendant vertex)
Tinjau graf G2: d(1) = 3     à bersisian dengan sisi ganda    
       d(2) = 4     à bersisian dengan sisi gelang (loop)           
Pada graf berarah,
            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
                                      G4                                             G5
                                Gambar 6
d(v) = din(v) + dout(v)   
Tinjau graf G4:
            din(1) = 1; dout(1) = 1
                        din(2) = 1; dout(2) = 3
            din(3) = 1; dout(3) = 1
                        din(4) = 2; dout(3) = 0
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 G1d(1) + d(2) + d(3) + d(4) = 2 + 3 + 3 + 2 = 10
                = 2 ´ jumlah sisi = 2 ´ 5
Tinjau graf G2d(1) + d(2) + d(3) = 3 + 3 + 4 = 10
                                      = 2 ´ jumlah sisi = 2 ´ 5
Tinjau graf G3d(1) + d(2) + d(3) + d(4) + d(5)
= 2 + 2 + 3 + 1 + 0 = 8
= 2 ´ jumlah sisi = 2 ´ 4
Contoh 2. 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).
6. Lintasan (Path)
Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan vn di dalam graf G ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v0, e1, v1, e2, v2,... , vn –1, en, vn sedemikian sehingga e1 = (v0, v1), e2 = (v1, v2), ... , en = (vn-1, vn) 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.
7. Siklus (Cycle) atau Sirkuit (Circuit)
Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atau siklus.
Tinjau graf G1: 1, 2, 3, 1 adalah sebuah sirkuit.
Panjang sirkuit adalah jumlah sisi dalam sirkuit tersebut. Sirkuit 1, 2, 3, 1 pada G1 memiliki panjang 3.
8. Terhubung (Connected)
Dua buah simpul v1 dan simpul v2 disebut terhubung jika terdapat lintasan dari v1 ke v2.
G disebut graf terhubung (connected graph) jika untuk setiap pasang simpul vi dan vj dalam himpunan V terdapat lintasan dari vi ke vj.



Jika tidak, maka G disebut graf tak-terhubung (disconnected graph).
Contoh graf tak-terhubung:
                        Gambar 7: Gambar G tidak 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   



(a) graf  berarah terhubung lemah                  (b) graf berarah terhubung kuat
                        gambar 8
8. Upagraf (Subgraph) dan Komplemen Upagraf
Misalkan G = (V, E) adalah sebuah graf. G1 = (V1, E1) adalah upagraf (subgraph) dari G jika V1  Í V dan E1 Í E.



Komplemen dari upagraf G1 terhadap graf G adalah graf G2 = (V2, E2) sedemikian sehingga E2 = E - E1 dan V2 adalah himpunan simpul yang anggota-anggota E2 bersisian dengannya.
            (a) Graf G1           (b) Sebuah upagraf       (c) komplemen dari upagraf (b)



Komponen graf (connected component) adalah jumlah maksimum upagraf terhubung dalam graf G.
Graf G di bawah ini mempunyai 4 buah komponen.
Pada graf berarah, komponen terhubung kuat (strongly connected component) adalah jumlah maksimum upagraf yang terhubung kuat.




Graf di bawah ini mempunyai 2 buah komponen terhubung kuat:
9. Upagraf Rentang (Spanning Subgraph)



Upagraf G1 = (V1, E1) dari G = (V, E) dikatakan upagraf rentang jika V1 =V (yaitu G1 mengandung semua simpul dari G).
             (a) graf G,        (b) upagraf rentang dari G,   (c) bukan upagraf rentang dari G

10. Cut-Set

Cut-set dari graf terhubung G adalah himpunan sisi yang bila dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen.

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.

(a)                                                        (b)


11. Graf Berbobot (Weighted Graph)



Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot).             
5.      Representasi Graf
a.      Matriks Ketetanggaan (adjacency matrix)
Matrik ketegangan adalah refresetasi graf yang paling umum. Misalkan G= (V,E) adalah graf dengan n simpul, n ≥ 1. Matriks ketetanggaan adalah G adalah matriks yang berukuran n x n. bila matriks tersebut di namakan A = [aij], maka aij = {1, jika simpul i dan j bertetangga, sebaliknya aij = 0 jika simpul i dan j tidak bertetangga. Karena matriks ketetanggaan hanya berisi 0 dan 1, maka matriks tersebut dinamakan juga matriks nol-satu (zero-one). Selain angka 0 dan 1, element matrik dapat juga dinyatakan dengan nilai false (menyatakan 0) dan true menyantakan 1). Matriks ketetanggaan di dasarkan pada pngurutan nomor simpul.








Contoh:
                                                                      
                                                           


(a)                                                     (b)                                     (c)

Matriks ketetanggaan untuk graf sederhana dan tidak berarah selalu simetri, sedangkan untuk graf berarah matriks ketetanggannya belum tentu simetri (akan simetri jika berupa graf berarah lengkap). Selain itu diagonal utamanya selalu nol karena tidak ada sisi gelang. Refresentasi dengan matriks  ketetanggaan adalah elemen matriksnya dapat diakses langsung melalui indeks. Selain itu, juga dapat di tentukan langsung apakah simpul i dan simpul j bertetangga. Dan derajat tiap simpul i dapat dihitung dari matriks ketetanggaan. Derajat tiap simpul i:
(a)  Untuk graf tak-berarah,   
                                      d(vi) =             
(b) Untuk graf berarah,                                                                                     
                        din (vj) = jumlah nilai pada kolom j                                            
                      dout (vi) = jumlah nilai pada baris i  =        



untuk graf berbobot, aij menyatakan bobot tiap sisi yang menghubungkan simpul i dengan simpul j.            
     a    b    c   d   e
         

Gambar : graf berbobot dengan graf ketetanggaannya.
Tanda “∞” menyatakan bahwa tidak ada sisi dari simpul i kesimpul i sendiri, sehingga aij tapat di beri nilai tak berhingga.

2. Matriks Bersisian (incidency matrix)
Bila matriks ketetanggaan menyatakan ketetanggaan simpul-simpul di dalam graf, maka matriks bersisian menyatakan kebersisian simpul dengan sisi. Misalnya G=(V,E) adalah graf dengan n simpul m buah sisi. Matriks bersisian G adalah matriks dwimatra yang berukuran n × m. baris menunjukkan label simpul, sedangkan kolom menunjukkan label sisinya. Bila matriks tersebut di namakan  A = [aij], maka aij = 1, jika simpul i bersisian dengan sisi j  maka aij =  0,   jika simpul i tidak bersisian dengan sisi j



Matriks bersisian dapat di gunakan untuk mempresentasikan graf yang mengandung sisi ganda atau sisi gelang. Derajat setiap simpul i dapat dihitung dengan menghitung jumlah seluruh elemen pada baris i ( kecuali pada graf yang mengandung gelang) jumlah elemen matriks bersisian adalah mn. Jika tiap elemen memputuhkan ruang memori sebesar p maka ruang memori yang di perlukan seluruhnya adalah pnm.

                                                                e1 e2 e3 e4  e5           
 

6. Garaf Berarah
Definisi sebuah graf berarah. Sebuag graf berarah atau digraph G terdiri dari:
1.      Sebuah himpunan V= V(G) yang elemen-elemennya di sebut vertex, titik atau node.
2.      Suattu koleksi E= E(G) dari pasangan –pasangan vertex terurut yang di sebut busur atau edge. Graf berarah G dikatakan berhingga jika himpunan V dari vertex-verteksnya dan himpunan E dari busurnya (edge berarahnya) behingga.
7.      Lintasan Terpendek
Lintasan terpendek adalah lintasan minimum yang diperlukan untuk mencapai suatu tempat dari tempat tertentu. Lintasan minimum yang di maksud dapat dicari dengan menggunakan graf.  Graf yang digunakan adalah graf berbobot yaitu graf yang tiap sisinya diberikan suatu nilai atau bobot. Bobot pada sisi graf dapat menyatakan graf antara kota, waktu pengiriman pesan, onkos pembangunan dan sebagainya. Kata “terpendek” tidak boleh selalu diartikan secara fisik sebagai minimum, sebab kata terpendek berbeda maknanya bergantung pada tipikal soal yang diberikan untuk diselesaikan.
Namun secara umum terpendendek berarti meminimisasikan bobot pada suatu lintasan graf. Misalkan simpul pada graf merupakan kota sedangkan sisi menyatakan jalan yang menghubungkan dua buah kota atau rata-rata waktu tempuh antara dua buah kota. Apabila terdapat lebih dari satu lintasan dari kota A ke kota B, maka persoalan lintasan terpendek disini adalah menentukan jarak terpendek atau waktu tersingkat dari kota A kekota B. dalam makalah ini, bobot yang dimaksud berupa jarak dan waktu kemacetan terjadi. Ada beberapa macam persoalan lintasan terpendek seperti:
a.       Lintasan terpendek antara dua buah simpul tertentu (a pair shortest path)
b.      Lintasan terpendek antara semua pasangan simpul (all pairs shortest path)
c.       Lintasan terpendek dari simpul tertentu kesemua simpul yang lain (single source shourtest path)
d.      Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu (intermediate shortest path).

KESIMPULAN DAN SARAN

  1. KESIMPULAN
Dari hasil makalah diatas maka dapat di simpulkan bahwa:
1.      Lintasan terpendek adalah lintasan minimum yang diperlukan untuk mencapai suatu tempat dari tempat tertentu. Lintasan minimum yang dimaksud  dapat dicari dengan menggunakan graf.
2.      Graf yang digunakan adalah graf yang berbobot yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot.

  1. SARAN
Dari hasil makah ini perlu kiranya di kemukakan beberapa saran yang mungkin akan bermanfaat bagi pembaca, guru dan pihak yang ada hubungannya dengan bidang studi matematika. Adapun saran-saran yang dikemukakan adalah:
1.      Semoga dapat bermanfaat bagi para pembaca terutama kepada pembuat makalah sendiri untuk menambah wawasan bahwa dalam mencapai suatu tujuan tertentu maka dicari lintasan terpendeknya sehingga dapat menghemat waktu dan biaya.
2.      Semoga makalah ini juga dapat bermanfaat padda mahasiswa yang sedang menempuh bangku perkuliahan.
3.      Kepada guru bidang study matematika agar mengajarkan matematika tidak hanya mengajarkan rumus-rumus tetapi langsung mengarahkan pada terapan untuk untuk menambah wawsan siswa dalam mengembangkan wawsan berfikir siswa.

Tidak ada komentar:

Posting Komentar