Diskusi Soal Graph

Diskusi Soal Graph. Dosen Pengampu : Ary Zanuwar , M. KOM Oleh: Abdurrahman Ahdiat Taufiq (21.04.008) Ilham Fauzi (21.04.008).

Pengertian Graph. Menurut catatan sejarah, masalah jembatan Konigsberg adalah masalah yang pertama kali mengggunakan graf (tahun 1736). Di kota Konigsberg (sebelah timur negara bagian Prussia , Jerman), sekarang bernama kota Kaliningrad , terdapat sungai Pregal yang mengalir mengitari pulau Kneiphof lalu bercabang menjadi dua buah anak sungai. Ada tujuh buah jembatan yang menghubungkan daratan yang dibelah oleh sungai tersebut. Masalahnya adalah apakah mungkin melalui ketujuh buah jembatan itu masing-masing tepat satu kali, dan kembali lagi ke tempat semula? Tahun 1736, seorang matematikawan Swiss, L.Euler , adalah orang pertama yang berhasil menemukan jawaban masalah itu dengan pembuktian yang sedrhana . Ia memodelkan masalah ini ke dalam graf. Daratan (titik-titik yang dihubungkan oleh jembatan) dinyatakannya sebagai titik(noktah) – yang disebut simpul( vertex )- dan jembatan dinyatakan sebagai garis yang disebut( edge ). Karena tidak semua simpul berderajat genap, maka tidak mungkin dilakukan perjalanan beberapa sirkuit(yang dinamakan sirkuit Euler ) pada graf tersebut..

Pengertian Graph. Graph adalah kumpulan node (simpul) di dalam bidang dua dimensi yang dihubungkan dengan sekumpulan garis (sisi). Graph dapat digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graph adalah dengan menyatakan objek sebagai node , bulatan atau titik ( Vertex ), sedangkan hubungan antara objek dinyatakan dengan garis ( Edge ). G = (V, E) Dimana : G = Graph V = Simpul atau Vertex , atau Node , atau Titik E = Busur atau Edge , atau arc Jalur pada graph dinotasikan sebagai P = (V0, V1, …, Vn ) Dimana : P : jalur V i : titik jalur n : jumlah titik jalur.

Pengertian Graph. Graph merupakan suatu cabang ilmu yang memiliki banyak terapan. Banyak sekali struktur yang bisa direpresentasikan dengan graph , dan banyak masalah yang bisa diselesaikan dengan bantuan graph . Seringkali graph digunakan untuk merepresentasikan suaru jaringan. Misalkan jaringan jalan raya dimodelkan graph dengan kota sebagai simpul ( vertex / node ) dan jalan yang menghubungkan setiap kotanya sebagai sisi ( edge ) yang bobotnya ( weight ) adalah panjang dari jalan tersebut. Ada beberapa cara untuk menyimpan graph di dalam sistem komputer. Struktur data bergantung pada struktur graph dan algoritma yang digunakan untuk memanipulasi graph . Secara teori salah satu dari keduanya dapat dibedakan antara struktur linked list dan matriks ( array dimensi 2), tetapi dalam penggunaannya struktur terbaik yang sering digunakan adalah kombinasi keduanya..

Istilah Dalam Graph. Ada beberapa istilah di dalam graph Vertex Adalah himpunan node / titik pada sebuah graph . Edge Adalah himpunan garis yang menghubungkan tiap node / vertex . Adjacent Adalah dua buah titik dikatakan berdekatan ( adjacent ) jika dua buah titik tersebut terhubung dengan sebuah sisi. Adalah Sisi e3 = v2v3 insident dengan titik v2 dan titik v3 tetapi sisi e3 = v2v3 tidak insident dengan titik v1 dan titik v4. Titik v1 adjacent dengan titik v2 dan titik v3, tetapi titik v1 tidak adjacent dengan titik v4..

Istilah Dalam Graph. Weight Adalah Sebuah graph G = (V, E) disebut sebuah graph berbobot ( weight graph ), apabila terdapat sebuah fungsi bobot bernilai real W pada himpunan E, W : E → R (14.3) nilai W(e) disebut bobot untuk sisi e, ∀ e ∈ E. Graf berbobot tersebut dinyatakan pula sebagai G = (V, E, W). Graf berbobot G = (V, E, W) dapat menyatakan : suatu sistem perhubungan udara, di mana : V = himpunan kota-kota E = himpunan penerbangan langsung dari satu kota ke kota lain W = fungsi bernilai real pada E yang menyatakan jarak atau ongkos atau waktu suatu sistem jaringan komputer, di mana : V = himpunan komputer E = himpunan jalur komunikasi langsung antar dua komputer W = fungsi bernilai real pada E yang menyatakan jarak atau ongkos atau waktu Path Adalah jalur dengan setiap vertex berbeda. Contoh, P = D5B4C2A Sebuah jalur (W) didefinisikan sebagai urutan (tidak nol) vertex dan edge . Diawali origin vertex ( vertex awal) dan diakhiri terminus vertex ( vertex akhir). Dan setiap 2 garis berurutan adalah series . Contoh, W = A1B3C4B1A2. Cycle Adalah Siklus ( Cycle ) atau Sirkuit ( Circuit ) yaitu lintasan yang berawal dan berakhir pada simpul yang sama..

Jenis-jenis Graph. Graph tak berarah ( undirected graph atau non- directed graph ) dimana urutan simpul dalam sebuah busur tidak dipentingkan. Misal busur e 1 dapat disebut busur AB atau BA. Graph berarah ( directed graph ) dimana urutan simpul mempunyai arti. Misal busur AB adalah e 1 sedangkan busur BA adalah e 8 ..

Jenis-Jenis Graph. Graph Berbobot ( Weighted Graph ) Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan memiliki bobot. Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, dll..

Pendeklarasian Graph. Operasi dasar pada graph adalah : Add vertex: menambahkan sebuah node/ titik ke dalam graph Add edge: menambahkan sebuah garis diantara dua node/ titik di dalam graph Display vertex: menampilkan node dari graph Beberapa kemungkinan dalam sebuah graph: Sebuah graph mungkin hanya terdiri dari satu node Sebuah graph belum tentu semua nodenya terhubung dengan busur Sebuah graph mungkin mempunyai node yang tak terhubung dengan node lainnya Sebuah graph mungkin semua nodenya saling berhubungan satu sama lain.

Contoh Graph. Graph dalam Matriks. nøanø anana perce.

Contoh Graph. Graf merepresentasikan Rangkaian Listrik Graf merepresentasikan Interaksi Protein RRP43 RRP42 PWSci2 Isorner senyavva Kimia karbon metana (CH4) etana (C2H6) propana (C3H8).