My Memory











{April 10, 2011}   Graph Theory | Oleh Septiani Kenyo Anggun

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

Sedikit lebih formal

Suatu graph G dapat dinyatakan sebagai G = < V,E > . Graph G terdiri atas himpunan V yang berisikan simpul pada graf tersebut dan himpunan dari E yang berisi sisi pada graf tersebut. Himpunan E dinyatakan sebagai pasangan dari simpul yang ada dalam V. Sebagai contoh definisi dari graf pada gambar di atas adalah : V = {1,2,3,4,5,6} dan E = {(1,2),(1,5),(2,3),(3,4),(4,5),(5,2),(4,6)}

 

Gambar dengan node yang sama dengan yang diatas, tapi merupakan digraf.

Pada digraf maka pasangan-pasangan ini merupakan pasangan terurut. Untuk menyatakan digraf (gambar kedua yang menggunakan tanda panah) kita dapat menggunakan himpunan edge sebagai berikut :

 

E = { < 1,2 > , < 1,5 > , < 2,5 > , < 3,2 > , < 4,3 > , < 5,4 > , < 4,6 > }

 

Dalam himpunan edge untuk digraf, urutan pasangan verteks menentukan arah dari edge tersebut.

 

Dalam teori graf, formalisasi ini untuk memudahkan ketika nanti harus membahas terminologi selanjutnya yang berhubungan dengan graph. Beberapa terminologi berhubungan dengan teori graf :

  • Degree atau derajat dari suatu node, jumlah edge yang dimulai atau berakhir pada node tersebut. Node 5 berderajat 3. Node 1 berderajat 2.
  • Path suatu jalur yang ada pada graph, misalnya antara 1 dan 6 ada path  b \rightarrow c \rightarrow g
  • Cycle siklus ? path yang kembali melalui titik asal 2  f \rightarrow c \rightarrow d \rightarrow e kembali ke 2.
  • Tree merupakan salah satu jenis graf yang tidak mengandung cycle. Jika edge f dan a dalam digraf diatas dihilangkan, digraf tersebut menjadi sebuah tree. Jumlah edge dalam suatu tree adalah nV – 1. Dimana nV adalah jumlah vertex
  • Graf Tak Berarah (Undirected Graph) Graf G disebut graf tak berarah (undirected graph) jika setiap sisinya tidak berarah. Dengan kata lain (vi,vj)=(vj,vi)
  • Graf Berarah (Directed Graph) Graf G disebut graf berarah (directed graph) jika setiap sisinya berarah. Titik awal dari suatu sisi disebut verteks awal (initial vertex) sedangkan titik akhir dari suatu sisi disebut verteks akhir (terminal vertex). Loop pada graf adalah sisi yang verteks awal dan verteks akhirnya sama.

 

Macam-macam pengantar Teori Graf :

1. Web Based Learning

Pada prinsipnya web based learning juga merupakan e-learning, hanya lebih dispesifikasikan pada pembelajaran dengan menggunakan internet terutama yang berupa website, web mail, mailing list dan bulletin board yang semua fasilitas tersebut masih berbasis web. Website sendiri adalah sejumlah halaman yang dapat berupa isi (content) sesuai dengan jenis website tersebut. Isi website disampaikan dengan berbagai bentuk seperti text, audio, video, bahkan teknologi streaming.

 

2. Tahapan Pengembangan Web Based Learning

Dalam pengembangan web based learning terdapat beberapa elemen yang perlu diperhatikan, seperti : interaktifitas (tutorial), pewarnaan, content, layout, dan lain-lain. Tutorial merupakan bagian dari proses pembelajaran. Tutorial merupakan satu bentuk interaksi antara pengajar (dosen/pakar) dengan mahasiswa. Interaksi dan komunikasi merupakan inti dari sebuah tutorial (Wardani, 2000).

 

3. Internet

Secara teknis, internet adalah suatu jaringan komputer global yang terbentuk dari jaringan-jaringan komputer lokal dan regional, memungkinkan komunikasi data antar komputer-komputer yang terhubung ke jaringan tersebut. Dari segi ilmu pengetahuan, internet merupakan sebuah perpustakaan besar yang didalamnya terdapat jutaan (bahkan milyaran) informasi atau data yang dapat berupa teks, grafik, suara maupun animasi dan lain–lain dalam bentuk media elektronik. Setiap orang dapat mengunjungi perpustakaan tersebut kapan saja dan dimana saja. Sedangkan dari segi komunikasi, internet adalah sarana yang sangat efisien dan efektif untuk melakukan pertukaran informasi jarak jauh maupun di dalam lingkungan tertentu.

 

4. Joomla

Joomla merupakan web berbasis Content Management System (CMS) dan bersifat opensource yang dapat digunakan oleh siapa saja untuk keperluan pembuatan website yang sangat kompleks. Para pengembang joomla fokus pada prinsip aplikasi gratis dan tidak ingin membuat sesuatu yang bersifat komersial. Kata joomla sendiri berasal dari bahasa swahili yang berarti “all together” atau ”as a whole” atau “bersama-sama”.

 

5. Macromedia Flash 8

Macromedia Flash merupakan aplikasi yang banyak digunakan oleh para profesional desain ataupun animator karena kelebihannya dalam menampilkan multimedia, gabungan antara grafis, animasi, suara, serta interaktivitas bagi user
(Dhani Yudhiantoro : 2003). Macromedia Flash 8 adalah versi terbaru dari Flash Sejak diakuisisi oleh Adobe, kemampuan dan fitur-fiturnya menjadi sangat dahsyat dan lengkap sehingga dapat digunakan untuk membuat berbagai macam aplikasi seperti animasi web kartun, multimedia interaktif sampai aplikasi untuk ponsel. Selain itu Flash 8 juga kompatible dengan software-software desain dan animasi lainnya.

 

6. Unified Modelling Language (UML)

UML (Unified Modeling Language) adalah sebuah bahasa standard yang digunakan untuk menspesifikasikan, memvisualisasikan, membangun, dan mendokumentasikan objek-objek dari sistem software, untuk urusan pemodelan dan sistem non-software. Bahasa permodelan ini digunakan untuk memahami, mendesain, menkonfigurasikan, memelihara dan mengontrol informasi yang terdapat dalam sebuah sistem. UML menggambarkan struktur yang statis (static structure) dan kelakuan yang dinamis (dynamic behavior) dari sebuah sistem. Sebuah sistem dalam UML digambarkan sebagai kumpulan objek diskrit yang saling berinteraksi untuk mencapai suatu tujuan yang berguna bagi pengguna. Dalam struktur yang statis, UML mendefinisikan objek-objek penting yang terdapat dalam system
dan implementasinya, dan menggambarkan interaksi antara objek-objek tersebut. Sedangkan dalam kelakuan yang dinamis, UML mendefinisikan sejarah suatu objek dan dan komunikasi antar objek tersebut untuk mencapai suatu tujuan.

 

7. Mengenal StartUML

StarUML adalah software permodelan yang mendukung UML (Unified Modeling Language). Berdasarkan pada UML version 1.4 dan dilengkapi 11 macam diagram yang berbeda, mendukung notasi UML 2.0 dan juga mendukung pendekatan MDA (Model Driven Architecture) dengan dukungan konsep UML. StarUML dapat memaksimalkan pruduktivitas dan kualitas dari suatu software project.

 

8. Struktur Navigasi

Struktur navigasi adalah struktur alur cerita dari sebuah program sebelum menyatukan elemen-elemen yang digunakan dalam aplikasi multimedia, sebaiknya kita mendefinisikan objek-objek dan merancang tampilan. Agar semua objek yang termasuk di dalam aplikasi tersebut tidak mengalami kerancuan informasi, dengan kata lain semua tampilan harus dapat memberikan informasi yang bulat dan utuh, sehingga dapat tercapai suatu pembentukan aplikasi multimedia. Dalam pembuatan aplikasi multimedia ada empat macam struktur navigasi yang dapat digunakan.

 

Sumber : http://www.wikipedia.com



Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

et cetera
%d blogger menyukai ini: