Senin, 27 Februari 2012

Copas Nick Vujicik "Life Without Limits"

Sepenggalan  kata Mutiara dr Buku Nick Vujicik
“Jika kau memiliki keinginan dan hasrat untuk melakukan sesuatu, dan hal itu sejalan dengan kehendak tuhan, kau pasti kan berhasil”

Aku menemukan kebahagiaan ketika aku menyadari bahwa aku memang manusia yang tidak sempurna, tetapi aku adalah Nick Vujicic yang sempurna. Aku ini ciptaan Tuhan yang dibentuk seturut rencana-Nya atas diriku. Namun bukan berarti aku tidak bisa berkembang . Aku selalu mencoba menjadi lebih baik sehingga aku bisa melayani Tuhan dan dunia lebih baik!

Aku sungguh percaya  kehidupan tidak memiliki batas. Aku harap kau juga merasa demikian dalam kehidupanmu, apapun cobaan yang kau hadapi. Di titik awal perjalanan kita bersama, cobalah merenungkan sejenak segala batasan yang kau kenakan kehidupanmu sendiri atau sengaja yang kau terima dari orang lain. Sekarang coba bayangkan seperti apajadinya bila kau terbebas dari semua batasan itu akan menjadi seperti apa kehidupanmu jika segalanya mungkin!

Resminya aku difabel (punya keterbatasan fisik), tetapi keadaan lengan dan tungkai ku menjadikan aku syarat kemampuanku. Cobaan-cobaanku yang unik telah membuka berbagai peluang unik untuk memnggapai begitu banyak orang yang membutuhkan. Coba bayangkan apa yang bisa kau lakukan!

Sering kita meyakinkan diri bahawa tidak cukup cerdas atau menarik atau berbakat untuk mengejar cita-cita kita. Kita mempercayai apa yang dikatakan orang lain tentang kita, atau kita membangun penghalang untuk kita sendiri. yang lebih buruk lagi, ketika merasa dirimu tidak berguna, kau sebenarnya memberikan batsan bagi karya Tuhan yang bisa terwujud melaluai dirimu!

Ketika kau menyerah mengejar impianmu, kau memenjarakaan Tuhan. Biar bagaimnapun, kau adalah ciptaan-Nya. Tuhan menciptakan demi sebuah tujuan. Karena itulah kehidupanmu tidak bisa dibatasi, sama halnya cinta TUhan tidak bisa dipadamkan.

Aku memiliki pilihan. Kau memiliki pilihan. Kita memilih utk berkubang dalam kekecewaan dan kekurangan. Kita bisa memilih untuk merasa sakit hati, marah, atau sedih. Atau, ketika berhadapan dengan penderitaan orang-orang yang kejam, kita bisa memilih untuk belajar dari pengalaman itu dan melangkah maju, mengambil tanggung jawab atas kebahagian kita sendiri.

Kau adalah anak Tuhan yang elok dan berharga, lebih berharga dari semua permata dunia. Aku dan kau benar-benar sempurna untuk menjadi diri kita yang sejati! Meski begitu, sudah seharusnyalah kita bercita-cita menjadi orang yang lebih baik  dan menembus semua batasan kita dengan impian yang besar. Penyempurnaan diri mutlak diperlukan karena perjalanan kehidupan tidak selamanya mulus, tetapi selalu layak di jalani. Aku mau mengatakan bahwa seperti apa pun dirimu, selama kau bernapas, kau memiliki peran yang harus di mainkan.

Aku tak dapat menepuk pundakmu dengan tanganku untuk meyakinkanmu, tetapi aku bisa bicara dari hati ku. Sesulit apa pun kehidupanmu terasa, selalu ada harapan. Seburuk apapun rintangan yang muncul, pasti ada hari - hari yang lebih baik di depan. Seberat apapun cobaan yang datang, kau pasti dapat melaluinya. Menunggu adanya perubahan tidak akan mengubah apapun. Membulatakan tekad untuk bertindak sekarang akan mengubah segalanya!

Segala hala terjadi demi mewujudkan sesuatu yang baik. Aku meyakini hal itukarena memang itulah yang terjadi dalam kehidupanku. Apa bagusnya kehidupan tanpa lengan dan tungkai?! Dengan melihatku saja orang langsung menyadri banyak kesulitan dan penderitaan yang kuhadapi. Kaena itulah mereka mau mendengarkanku sebagai sumber inspirasi. Mereka mau meyakinkanku, untuk berkata kepada mereka bahwa mereka di cintai, dan menumbuhkan kebahagiaan mereka.

Itulah peranku. kau harus mengenali nilai dirimu sendiri, bahwa kau pun memiliki peranan yang harus dijalankan. Tidak apa-apa jika kau merasa frustasi sekarang. Kefrustasianmu menunjukkan bahwa kau menginginkan lebih bagi kehidupanmu daripada yang kau miliki sekarang. Tidak ada salahnya. Sering kali, cobaan dalam kehidupan yang menunjukkan kepada kita diri kita yang sejati kepadamu. Aku ingin kau menggapai segala kebahagiaan dan kepuasan yang di sediakan tuhan bagimu.

Jika kau termasuk di antara sekian banyak orang yang berjuan setiap hari, ingatlah selalu bahwa di luar perjuanganku sendiri telah menanti sebuah tujuan bagi kehidupanku. Tujuan itu terbukti amat sanag jauh lebih besar dari pada yang ku bayangkan.

Kau mungkin akan terbentur banyak kesulitan. Kau mungkin kan jatuh dan merasa tak ada lagi kekuatan dalam dirimu untuk bangkit kembali. Aku tahu bagaimana rasanya, Teman. Kita semua merasakannya. Kehidupan tidak selamanya mudah, tetapi ketika kita menaklukkan cobaan, kita menjadi lebih kuat dan lebih bisa mensyukuri kesempatan-kesempatan kita. Yang terpenting adalah kehidupan-kehidupan yang kau sentuh selama perjalananmu dan caramu menyelesaikan perjalanan itu.

Aku mencintai kehidupanku sebagaimana aku mencintai kehidupanmu. Bersama-sama, peluang kita sungguh luar biasa. Jadi bagamana tidakkah lebih baik kita coba saja, Kawan??..

Rabu, 21 Desember 2011

Teori Graph

·       Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut.

·       Gambar di bawah ini sebuah graf yang menyatakan peta jaringan jalan raya yang menghubungkan sejumlah kota di Provinsi Jawa Tengah.


·       Sejarah Graf: masalah jembatan Königsberg (tahun 1736)













Gambar 1. Masalah Jembatan Königsberg

·       Graf yang merepresentasikan jembatan Königsberg:
                                       Simpul (vertex) à menyatakan daratan
          Sisi (edge)           à menyatakan jembatan
·       Bisakah melalui setiap jembatan tepat sekali dan kembali lagi ke tempat semula?
Definisi Graf
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 }

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.


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 1 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 2 adalah graf berarah.

Tabel 1 Jenis-jenis graf [ROS99]
Contoh Terapan Graf

1. Rangkaian listrik.
2.  Isomer senyawa kimia karbon





                         metana (CH4)                  etana (C2H6)                propana (C3H8)



3.  Transaksi konkuren pada basis data terpusat
    Transaksi T0 menunggu  transaksi T1  dan T2 
    Transaksi T2 menunggu transaksi T1 
    Transaksi T1  menunggu transaksi T3 
    Transaksi T3 menunggu transaksi T2 
 4.  Pengujian program

          read(x);





   while x <> 9999 do
    begin          
      if x < 0 then
         writeln(‘Masukan tidak boleh negatif’)
      else
        x:=x+10;
           read(x);
    end;
   writeln (x);







Keterangan:   1 : read(x)                              5 : x := x + 10
                      2 : x <> 9999                                                6 : read(x)
                      3 : x < 0                                                        7 : writeln(x)
                      4 : writeln(‘Masukan tidak boleh negatif’);

5.  Terapan graf pada teori otomata [LIU85].




Mesin jaja (vending machine)

Keterangan:
       a : 0 sen dimasukkan
       b : 5 sen dimasukkan
       c : 10 sen dimasukkan
       d : 15 sen atau lebih dimasukkan

Terminologi Graf



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

          d(v) = din(v) + dout(v)    
   G4                                              

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 G1:  d(1) + d(2) + d(3) + d(4) = 2 + 3 + 3 + 2 = 10
= 2 ´ jumlah  sisi = 2 ´ 5
G1

Tinjau graf G2d(1) + d(2) + d(3) = 3 + 3 + 4 = 10
= 2 ´ jumlah sisi = 2 ´ 5
G2

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:
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


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 atas 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





11. Graf Berbobot (Weighted Graph)
Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot).

Beberapa Graf Sederhana Khusus

a. Graf Lengkap (Complete Graph)
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 (Regular Graphs)

Graf yang setiap simpulnya mempunyai derajat yang sama disebut graf teratur. Apabila derajat setiap simpul adalah r, maka graf tersebut disebut sebagai graf teratur derajat r. Jumlah sisi pada graf teratur adalah nr/2. 
d. Graf Bipartite (Bipartite Graph)
Graf G yang himpunan simpulnya dapat dipisah menjadi dua himpunan bagian V1 dan V2,  sedemikian sehingga setiap sisi pada G menghubungkan sebuah simpul di V1 ke sebuah simpul di V2 disebut graf bipartit dan dinyatakan sebagai G(V1, V2).







Graf G di bawah ini adalah graf bipartit, karena simpul-simpunya dapat dibagi menjadi V1 = {a, b, d} dan V2 = {c, e, f, g}
             graf persoalan utilitas,                 topologi bintang


Representasi Graf

1. Matriks Ketetanggaan (adjacency matrix)

A = [aij],
                                1, jika simpul i dan j bertetangga  
                     aij = {       
                                0, jika simpul i dan j tidak bertetangga   
                                     
Contoh:





Derajat tiap simpul i:
(a)  Untuk graf tak-berarah,





                                                                              

   d(vi) =