Struktur Data || Graph

Asalamualaikum Wr Wb

pada kesempatan kali ini kita akan membahas Graph. dan Tugas Saya

sebelum kesoal kita bahas ulu apa itu Graph, berapa banyak macamnya.

Graf adalah kumpulan noktah (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 noktah, bulatan atau titik (Vertex), sedangkan hubungan antara objek dinyatakan dengan garis (Edge).

jadi intinya Graph adalah titik atau objek yang saling berhubungan.

Ada terdapat beberapa macam  graf yang bisa kita gunakan, yaitu beberapa diantaranya adalah sebagai berikut :

1. Graf  Directed (Berarah) : adalah graf yang edge-nya memiliki arah, Urutan arah sangat penting dan biasanya arah tujuan memakai tanda panah, sebagai contoh edge AB menghubungkan vertex A ke B, dimana hubungan vertex B ke A, harus diperoleh 2 dari edge lain, yaitu edge BA, dan jika edge BA tidak ada, maka vertex B ke A tidak memiliki hubungan, meski vertex A ke B memiliki hubungan.

2. Graf Undirected (Tak Berarah) : adalah graf yang edge-nya tidak memiliki arah, sehingga jika edge AB menghubungkan vertex A ke B, maka secara otomatis juga menghubungkan vertex B ke A.

3. Graf Weighted (Berbobot) : adalah suatu graf dimana edge dari graf tersebut memiliki bobot atau nilai tertentu.

B. Istilah-istilah dalam graph

Kemudian terdapat istilah-istilah yang berkaitan dengan graph yaitu: 

1. Vertex : himpunan node / titik pada sebuah graph. 

2. Edge : himpunan garis yang menghubungkan tiap node / vertex. 

3. Adjacent : hubungan lansung antara 2 vertex.

4. Path : jalur dari suatu vertex ke vertex kevertex lainnya.

5. Incident : edge yang bersentuhan dengan suatu vertex.

6. Degree : Jumlah edge yang incident dengan dengan suatu vertex.

7. Indegree : jumlah edge yang mengarah kesuatu vertex.

8. Outdegree : jumlah edge yang berasal dari suatu vertex.

9. Sucessor : node yang berada dibawah node tertentu atau sebagai penerus.

10. Predecessor : node yang berada diatas node tertentu atau asal.

oke setelah kita mengenal apa itu graph 

kita akan mengerjakan sebuah soal 

Buatlah sebuah graph berbobot (weighted Graph) dari data yang ada dalam tabel dibawah ini :

kelompok 5 :

1. Tentukan Path dari Jakarta ke madiun. (tuliskan semua jalur yang bisa dilalui)
2. Berapakah jarak yang ditempuh untuk masing-masing path?
3. Path mana dan berapa jarak terpendek yang dapat ditempuh dari kedua kota itu?
4. Path mana dan berapa jarak terjauh yang harus ditempuh dari kedua kota itu?

Nb : pada soal ini diperbolehkan bolak balik

Path Kota Jakarta menuju Kota Madiun

1.  Jakarta – Malang – Madiun

     800+200 = 1000 Km

 2. Jakarta – Semarang – Yogya – Malang – Madiun

     400 + 100 + 250 + 200 = 950 Km

 3. Jakarta – Yogya – Malang – Madiun

     600 + 250 + 200 = 1050 Km

  4. Jakarta – Semarang – Banyuwangi – Blitar - Malang – Madiun

      400 + 800 + 450 + 120 + 200 = 1970 Km

 5. Jakarta – Yogya – Semarang – Banyuwangi - Malang – Madiun

     600 + 100 + 800 + 300 + 200 = 2000 Km

 6.  Jakarta – Malang – Blitar – Banyuwangi – Semarang –Yogya – malang – madiun

     800 + 120 + 450 + 800 + 100 + 250 + 200 = 2720 Km

 7. Jakarta – Semarang – Yogya – Malang – Belitar – Banyuwangi – Malang – Madiun

    400 + 100 + 250 + 120 + 450 + 300 + 200 = 1820 Km

 8. Jakarta – Yogya – Malang – Blitar – Banyuwangi – Semarang – Yogya - Malang – Madiun

     600 + 250 + 120 + 450 + 800 + 100 + 250 + 200 = 2770 Km

 9. Jakarta – Malang – Yogya – Semarang – Banyuwangi - Malang – Madiun

    800 + 250 + 100 + 800 + 300 + 200 = 2450 Km

10. Jakarta – Semarang – Yogya – Malang – Blitar – Banyuwangi Semarang – Yogya – Malang –         Belitar

   400 + 100 + 250 + 120 + 450 + 800 + 100 + 250 + 200 = 2620 Km

11. Jakarta – Yogya – Semarang – Banyuwangi – Belitar - Malang – Madiun

      600 + 100 + 800 + 450 + 120 + 200 = 2270 Km

12. Jakarta – Malang – Yogya – Semarang – Banyuwangi – Belitar - Malang – Madiun

      800 + 250 + 100 + 800 + 450 + 120 + 200 = 2620 Km

C. Rute jalur Terpendek dari Jakarta ke Madiun adalah No 2 dengan 950 km

    yaitu =  Jakarta – Semarang – Yogya – Malang – Madiun

     400 + 100 + 250 + 200 = 950 Km

D  Rute jarak Terjauh dari Jakarta ke Madiun adalah No 8 dengan jarak tempuh 2270 Km

     yaitu dengan jalur = Jakarta – Yogya – Malang – Blitar – Banyuwangi – Semarang – Yogya -

     Malang – Madiun

     600 + 250 + 120 + 450 + 800 + 100 + 250 + 200 = 2770 Km

Trimakasih sekian dulu apa yang saya sampaikan 

kurang lebihnya mohon maaf

Wassalamualaikum Wr Wb.................