Langsung ke konten utama

Teori graf

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 di atas, 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 di atas 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.

Komentar

Postingan populer dari blog ini

Memperbaiki Microphone Headset Yang Tidak Mengeluarkan Suara

Internet merupakan sarana komunikasi yang murah dengan menggunakan microphone dan juga aplikasi seperti Skype, YM, dsb. Pernahkah pada suatu ketika anda mengalami microphone / headset yang tidak mengeluarkan suara meskipun kabel jack terhubung dengan baik? Atau mungkin microphone yang justrumengeluarkan suara ketika dihubungkan dengan komputer lain. Pada tulisan kali ini akan menjelaskan beberapa cara untuk mendeteksi penyebabnya. Memperbaiki Microphone Headset Yang Tidak Mengeluarkan Suara Langkah pertama untuk mengatasi permasalahan headset,atau microphone yang tidak mengeluarkan suara adalah memastikan bahwa perangkat tersebut masih berfungsi dengan baik (tidak rusak). Untuk memastikan, anda dapat mencobanya pada beberapa komputer yang berlainan. Bila headset dalam keadaan baik maka anda dapat beralih pada beberapa settingan di komputer anda agar memastikan bahwa ketiga poin dibawah ini ter-setting dalam keadaan benar: Port penghubung Microphone / HeadsetDriver & Settingan Mic…

Siswi SMP ciuman didepan Gurunya

. Dunia Pendidikan Lagi2 Tercoreng, Siswi SMP Ciuman depan Guru
Entah apa yang terjadi, jika semua dilakukan tanpa etika dan Norma, Apalagi jika dilakukan oleh anak – anak / mereka yang nota bene adalah pelajar. Jika yang terpelajar saja tak enggan melakukan hal – hal asusila didepan sang guru, lalu apa yang ada dibenak mereka tentang gurunya. masih berlakukah kalimat bijak “Guru Kencing berdiri, Murid Kencing Berlari” sungguh ironis dan sangat menyedihkan nasib negeri ini selanjutnya.

Mau diapakan pendidikan di negeri ini. seolah – olah tak perlu lagi adanya etika di era yang konon dianggap modern, hingga semuanya menjadi normal – normal saja. Tak ada lagi batasan – batasan yang mampu mencegah nurani untuk sekedar menghambat nafsu birahi. Mungkin hanya kesenangan belaka yang didapat, namun apa akibat yang di timbulkan.

Semuanya seolah tak peduli lagi dengan etika, hancurnya negeri bukanlah karena kemiskinan dan ketidak adilan belaka, namun lebih berdampak mengerikan jika kehancuran …

Anda ingin membuat tulisan atau nama anda sendiri dibuat dalam berbagai bentuk.

Anda ingin membuat tulisan atau nama anda sendiri dibuat dalam berbagai bentuk.
Ketik beberapa kata, pisahkan kata-kata tersebut dengan koma dan tekan tombol “Enter”. Anda dapat juga memilih satu s/d 3 kata atau merubahnya setiap warna pada kata tersebut. Menarik bukan?  Apabila anda ingin mencobanya silakan Klik Disini