koding day's

hari ini kami mempelajari graph. graph itu salah satu materi di struktur data. kalo ngga ngerti list kayanya susah deh buat memahami graph. karena sumber graph itu sebenarnya list, dan selama belajar struktur data sebenarnya yang harus dipahami pertama kali itu konsep list. sebelim masuk ke graph mari kita kenali dulu graph lebih dalam lewat sejarahnya !!! ^_^

sekilas sejarah tentang graph, teori graph itu sendiri pertama kali diperkenalkan leonhard euleur 1736 lewat tulisannya yang berisi tentang upaya pemecahan jembatan konigsberg yang sangat terkenal di eropa.

yang sekarang bernama kota Kaliningrad, terdapat sungai Pregal yg mengalir mengintari pulau Kneiphof lalu bercabang menjadi dua buah anak sungai. Ada 7 buah jembatan yg menghubungkan daratan yg dibelah oleh sungai tersebut. Sejarah Graf : masalah jembatan Königsberg (tahun 1736)

Graf yang merepresentasikan jembatan Königsberg:

               Simpul (vertex)  menyatakan daratan

              Sisi (edge)  menyatakan jembatan

 tahun 1847 G.R Kirchoff  berhasil mengembangkan teori tree yang dipakai dalam permasalahan jaringan listrik sepuluh tahun selanjutnya juga A coyley mengunakan teori tree untuk menjelaskan permasalahan kimia yaitu hidrokarbon. 

Salah satu masalah yang cukup terkenal dalam teori graf yaitu Konjektur EmpatWarna (The Four Color Conjecture) yang diajukan oleh Prancis Guthrie sekitar tahun1850.Masalah dalam Konjektur Empat Warna (The Four Color Conjecture) adalah mewarnai sebuah peta dengan empat macam warna sedemikian hingga tiap Negara yang berbatasanmemiliki warna yang berbeda.Para ahli teori graph berkeyakinan bahwa orang yang pertama kali mengemukakanmasalah empat warna adalah A.F. Mobius (1790 ± 1868) dalam salah satu kuliahnya di Tahun1840. Sepuluh tahun kemudian, A. De Morgan (1806 ± 1871) kembali membahas masalah inibersama ahli-ahli matematika lainnya di kota London. Dengan demikian tulisan De Morgandianggap sebagai referensi pertama berkenaan dengan masalah empat warna.

itu tadi sejarah singkat tentang graph, sejarah singkat lebih tepatnya. graph juga memiliki beberapa komponen :

Alur adalah setiap lintasan yang semua titik simpul berbeda satu sama lain kecuali titik awal dan titik akhirnya.

 Panjang adalah banyak sisi / lintasan yang ditempuh.

 Derajat adalah jumlah rusuk atau sisi yang menuju satu titik simpul.

Titik terasing adalah titik yang tidak memiliki garis penghubung / jalan.

 Jalan tapak adalah suatu lintasan yang tidak memiliki dua rusuk yang sama.

 Ketetanggan adalah dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.

Simpul terpencil adalah simpul yang tidak mempunyai sisi yang bersisian dengannya. 

Graf  Kosong adalah graf yang himpunan sisinya merupakan himpunan kosong (Nn). 

Siklus atau sirkuit adalah lintasan yang berawal dan berakhir pada simpul yang sama.

Panjang sirkuit adalah jumlah sisi dalam sirkuit tersebut. 

Terhubung adalah dua buah simpul v1 dan simpul v2 disebut terhubung jika terdapat lintasan dari v1. Graf berarah G dikatakan terhubung jika graf tidak berarahnya terhubung (graf tidak berarah dari Gdiperoleh dengan menghilangkan arahnya).

Dua simpul, u dan v, pada graf berarah G disebut terhubung kuat (strongly connected) jika terdapat lintasan berarah dari u ke v dan juga lintasan berarah dari v ke u. Jika u dan v tidak terhubung kuat tetapi terhubung pada graf tidak berarahnya, maka u dan v dikatakan terhubung lemah (weakly coonected).

Graf berarah G disebut graf terhubung kuat (strongly connected graph) apabila untuk setiap pasang simpul sembarang u dan v di G, terhubung kuat. Kalau tidak, G disebut graf terhubung lemah.

itu tadi seklias tentang graph, untuk kodingannya nanti kita lanjut lagi ya,,,, sabar sabar