teori graf

Pendahuluan

Di matematika dan ilmu komputer, teori graf adalah cabang ilmu yang mempelajari sifat-sifat graf. Secara informal, suatu graf adalah himpunan benda-benda yang disebut verteks (atau node) yang terhubung oleh edge-edge (atau arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan verteks) yang dihubungkan oleh garis-garis (melambangkan edge).

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: verteks-verteksnya adalah para pemakai Friendster dan ada edge antara A dan B jika dan hanya jika A berteman dengan B. Perkembangan algoritma untuk menangani graf akan berdampak besar bagi ilmu komputer.

Sebuah struktur graf bisa dikembangkan dengan memberi bobot pada tiap edge. 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 edgenya berarah, yang secara teknis disebut graf berarah atau digraf (directed graph). Digraf dengan edge 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).
[sunting] Sedikit lebih formal

Suatu graph G dapat dinyatakan sebagai G = < V,E > . Graph G terdiri atas himpunan V yang berisikan verteks/node pada graph tersebut dan himpunan dari E yang berisi edge pada graph tersebut. Himpunan E dinyatakan sebagai pasangan dari verteks yang ada dalam V. Sebagai contoh definisi dari graf pada gambar diatas 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

Artikel ini adalah sebuah rintisan. Anda dapat membantu Wikipedia dengan mengembangkannya.

PENGATAR ILU KIMIA

Kimia sering disebut sebagai "ilmu pusat" karena menghubungkan berbagai ilmu lain, seperti fisika, ilmu bahan, nanoteknologi, biologi, farmasi, kedokteran, bioinformatika, dan geologi [1]. Koneksi ini timbul melalui berbagai subdisiplin yang memanfaatkan konsep-konsep dari berbagai disiplin ilmu. Sebagai contoh, kimia fisik melibatkan penerapan prinsip-prinsip fisika terhadap materi pada tingkat atom dan molekul.
Kimia berhubungan dengan interaksi materi yang dapat melibatkan dua zat atau antara materi dan energi, terutama dalam hubungannya dengan hukum pertama termodinamika. Kimia tradisional melibatkan interaksi antara zat kimia dalam reaksi kimia, yang mengubah satu atau lebih zat menjadi satu atau lebih zat lain. Kadang reaksi ini digerakkan oleh pertimbangan entalpi, seperti ketika dua zat berentalpi tinggi seperti hidrogen dan oksigen elemental bereaksi membentuk air, zat dengan entalpi lebih rendah. Reaksi kimia dapat difasilitasi dengan suatu katalis, yang umumnya merupakan zat kimia lain yang terlibat dalam media reaksi tapi tidak dikonsumsi (contohnya adalah asam sulfat yang mengkatalisasi elektrolisis air) atau fenomena immaterial (seperti radiasi elektromagnet dalam reaksi fotokimia). Kimia tradisional juga menangani analisis zat kimia, baik di dalam maupun di luar suatu reaksi, seperti dalam spektroskopi.
Semua materi normal terdiri dari atom atau komponen-komponen subatom yang membentuk atom; proton, elektron, dan neutron. Atom dapat dikombinasikan untuk menghasilkan bentuk materi yang lebih kompleks seperti ion, molekul, atau kristal. Struktur dunia yang kita jalani sehari-hari dan sifat materi yang berinteraksi dengan kita ditentukan oleh sifat zat-zat kimia dan interaksi antar mereka. Baja lebih keras dari besi karena atom-atomnya terikat dalam struktur kristal yang lebih kaku. Kayu terbakar atau mengalami oksidasi cepat karena ia dapat bereaksi secara spontan dengan oksigen pada suatu reaksi kimia jika berada di atas suatu suhu tertentu.

Zat cenderung diklasifikasikan berdasarkan energi, fase, atau komposisi kimianya. Materi dapat digolongkan dalam 4 fase, urutan dari yang memiliki energi paling rendah adalah padat, cair, gas, dan plasma. Dari keempat jenis fase ini, fase plasma hanya dapat ditemui di luar angkasa yang berupa bintang, karena kebutuhan energinya yang teramat besar. Zat padat memiliki struktur tetap pada suhu kamar yang dapat melawan gravitasi atau gaya lemah lain yang mencoba merubahnya. Zat cair memiliki ikatan yang terbatas, tanpa struktur, dan akan mengalir bersama gravitasi. Gas tidak memiliki ikatan dan bertindak sebagai partikel bebas. Sementara itu, plasma hanya terdiri dari ion-ion yang bergerak bebas; pasokan energi yang berlebih mencegah ion-ion ini bersatu menjadi partikel unsur. Satu cara untuk membedakan ketiga fase pertama adalah dengan volume dan bentuknya: kasarnya, zat padat memeliki volume dan bentuk yang tetap, zat cair memiliki volume tetap tapi tanpa bentuk yang tetap, sedangkan gas tidak memiliki baik volume ataupun bentuk yang tetap.
Air yang dipanaskan akan berubah fase menjadi uap air.

Air (H2O) berbentuk cairan dalam suhu kamar karena molekul-molekulnya terikat oleh gaya antarmolekul yang disebut ikatan Hidrogen. Di sisi lain, hidrogen sulfida (H2S) berbentuk gas pada suhu kamar dan tekanan standar, karena molekul-molekulnya terikat dengan interaksi dwikutub (dipole) yang lebih lemah. Ikatan hidrogen pada air memiliki cukup energi untuk mempertahankan molekul air untuk tidak terpisah satu sama lain, tapi tidak untuk mengalir, yang menjadikannya berwujud cairan dalam suhu antara 0 °C sampai 100 °C pada permukaan laut. Menurunkan suhu atau energi lebih lanjut mengizinkan organisasi bentuk yang lebih erat, menghasilkan suatu zat padat, dan melepaskan energi. Peningkatan energi akan mencairkan es walaupun suhu tidak akan berubah sampai semua es cair. Peningkatan suhu air pada gilirannya akan menyebabkannya mendidih (lihat panas penguapan) sewaktu terdapat cukup energi untuk mengatasi gaya tarik antarmolekul dan selanjutnya memungkinkan molekul untuk bergerak menjauhi satu sama lain.

Ilmuwan yang mempelajari kimia sering disebut kimiawan. Sebagian besar kimiawan melakukan spesialisasi dalam satu atau lebih subdisiplin. Kimia yang diajarkan pada sekolah menengah sering disebut "kimia umum" dan ditujukan sebagai pengantar terhadap banyak konsep-konsep dasar dan untuk memberikan pelajar alat untuk melanjutkan ke subjek lanjutannya. Banyak konsep yang dipresentasikan pada tingkat ini sering dianggap tak lengkap dan tidak akurat secara teknis. Walaupun demikian, hal tersebut merupakan alat yang luar biasa. Kimiawan secara reguler menggunakan alat dan penjelasan yang sederhana dan elegan ini dalam karya mereka, karena terbukti mampu secara akurat membuat model reaktivitas kimia yang sangat bervariasi.