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 tentang 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
- Cycle siklus ? path yang kembali melalui titik asal 2 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.
Aplikasi
Grafik adalah salah satu model yang paling mana-mana dari kedua struktur alam dan buatan manusia. Mereka dapat digunakan untuk model berbagai jenis hubungan dan dinamika proses dalam sistem fisik, biologis dan sosial. Banyak masalah kepentingan praktis dapat diwakili oleh grafik.
Dalam ilmu komputer, grafik digunakan untuk mewakili jaringan komunikasi, organisasi data, perangkat komputasi, alur perhitungan, dll Salah satu contoh praktis: Struktur link dari sebuah website dapat diwakili oleh grafik diarahkan. Simpul adalah halaman web yang tersedia di website dan keunggulan diarahkan dari halaman A ke halaman B ada jika dan hanya jika A berisi link ke B. Pendekatan yang serupa dapat diambil untuk masalah dalam perjalanan, biologi, desain chip komputer, dan banyak bidang lain. Perkembangan algoritma untuk menangani grafik Oleh karena itu kepentingan utama dalam ilmu komputer. Di sana, transformasi grafik sering formal dan diwakili oleh grafik menulis ulang sistem. Mereka baik yang secara langsung digunakan atau sifat dari menulis ulang sistem (misalnya pertemuan) dipelajari. Melengkapi sistem transformasi berfokus pada manipulasi grafik di memori aturan berbasis grafik grafik database diarahkan transaksi-aman, gigih menyimpan dan query data grafik-terstruktur.
Metode Grafik-teoritis, dalam berbagai bentuk, telah terbukti terutama berguna dalam linguistik, karena bahasa alami sering lends sendiri baik untuk struktur diskrit. Secara tradisional, sintaks dan semantik mengikuti struktur komposisi berbasis pohon, yang ekspresif kekuasaan terletak pada Prinsip Compositionality, dimodelkan dalam sebuah grafik hirarkis. Dalam semantik leksikal, terutama diterapkan pada komputer, pemodelan arti kata mudah ketika kata yang diberikan dipahami dalam hal kata-kata yang terkait; jaringan semantik karena itu penting dalam linguistik komputasi. Masih metode lain dalam fonologi (misalnya optimalitas Teori, yang menggunakan grafik kisi) dan morfologi (misalnya morfologi terbatas-negara, menggunakan transduser terbatas-negara) yang umum dalam analisis bahasa sebagai grafik. Memang, daerah ini kegunaan matematika untuk linguistik telah ditanggung organisasi seperti TextGraphs, serta proyek 'bersih' beragam, seperti WordNet, VerbNet, dan lain-lain.
Grafik teori juga digunakan untuk mempelajari molekul dalam kimia dan fisika. Dalam fisika benda terkondensasi, struktur tiga dimensi rumit struktur atom simulasi dapat dipelajari secara kuantitatif dengan mengumpulkan statistik tentang sifat grafik-teoritis yang berkaitan dengan topologi dari atom. Sebagai contoh, terpendek Franzblau's-path (SP) cincin. Dalam kimia grafik membuat model alami untuk sebuah molekul, dimana simpul mewakili atom dan obligasi tepi. Pendekatan ini terutama digunakan dalam pengolahan komputer struktur molekul, mulai dari editor kimia ke database pencarian. Dalam fisika statistik, grafik dapat mewakili koneksi lokal antara berinteraksi bagian dari suatu sistem, serta dinamika dari proses fisik pada sistem tersebut.
Grafik teori juga banyak digunakan dalam sosiologi sebagai cara, misalnya, untuk mengukur prestise aktor 'atau untuk menjelajahi mekanisme difusi, terutama melalui penggunaan perangkat lunak analisis jaringan sosial.
Demikian pula, teori graf berguna dalam upaya biologi dan konservasi di mana simpul dapat mewakili daerah dimana spesies tertentu ada (atau habitat) dan ujung-ujungnya merupakan jalur migrasi, atau gerakan antara daerah. Informasi ini penting ketika melihat pola berkembang biak atau pelacakan penyebaran penyakit, parasit atau bagaimana perubahan gerakan ini dapat mempengaruhi spesies lain.
Dalam matematika, grafik berguna dalam geometri dan bagian-bagian tertentu dari topologi, misalnya Teori Knot. Teori graph aljabar memiliki hubungan erat dengan teori grup.
Struktur graph dapat diperpanjang dengan penugasan berat untuk setiap tepi grafik. Grafik dengan bobot, atau grafik tertimbang, adalah digunakan untuk merepresentasikan struktur di mana koneksi berpasangan memiliki beberapa nilai numerik. Sebagai contoh jika suatu graf merupakan jaringan jalan, bobot bisa mewakili panjang jalan masing-masing.
Sebuah digraf dengan tepi tertimbang dalam konteks teori graph disebut jaringan. Analisis Jaringan memiliki aplikasi praktis, misalnya, untuk model dan menganalisis jaringan lalu lintas. Aplikasi analisis jaringan luas dibagi menjadi tiga kategori:
- Pertama, analisis untuk menentukan sifat struktur jaringan, seperti distribusi derajat vertex dan diameter grafik. Sejumlah besar langkah-langkah grafik ada, dan produksi yang berguna untuk berbagai domain masih merupakan bidang penelitian aktif.
- Kedua, analisis untuk menemukan kuantitas terukur dalam jaringan, misalnya, untuk jaringan transportasi, tingkat arus kendaraan bermotor dalam setiap bagian itu.
- Ketiga, analisis sifat dinamik jaringan.
Menggambar grafik
Grafik grafik dengan menggambar sebuah titik atau lingkaran untuk setiap vertex, dan menggambar sebuah busur antara dua titik jika mereka dihubungkan dengan tepi. Jika grafik diarahkan, arah yang ditunjukkan dengan gambar panah.
Sebuah gambar grafik tidak harus bingung dengan grafik itu sendiri (struktur, abstrak non-visual) karena ada beberapa cara untuk struktur gambar grafik. Yang penting adalah yang terhubung ke simpul yang lain dengan berapa banyak sisi dan bukan tata letak yang tepat. Dalam prakteknya sering sulit untuk memutuskan apakah dua gambar mewakili grafik yang sama. Tergantung pada domain beberapa masalah tata letak mungkin akan lebih cocok dan lebih mudah untuk memahami daripada yang lain.
Selengkapnya dapat dibaca di http://en.wikipedia.org/wiki/Graph_theory , semoga bermanfaat....
Tidak ada komentar:
Posting Komentar