> ## Documentation Index
> Fetch the complete documentation index at: https://v1-learn.neoartd.my.id/llms.txt
> Use this file to discover all available pages before exploring further.
# Pengantar Teori Graf
# Pengenalan Teori Graf
## Pendahuluan
Graf digunakan untuk merepresentasikan objek-objek diskrit
dan hubungan antara objek-objek tersebut.
## Sejarah Graf
Masalah jembatan Königsberg (tahun 1736) ditemukan oleh Euler
* Graf yang merepresentasikan jembatan Königsberg:
Simpul (vertex) → menyatakan daratan\
Sisi (edge) → menyatakan jembatan
* Bisakah melalui setiap jembatan tepat sekali?
## Problem dan Model Graph
### Problem 1
* Seorang pengantar pizza memiliki 5 alamat pemesan yang
harus diantarkan dengan sekali berangkat. Pengantar pizza
tersebut tidak boleh kembali sebelum semua pesanan
diantarkan. Permasalahannya adalah bagaimana pengantar
itu memilih rute yang paling cepat untuk mengunjungi ke 5
alamat itu supaya waktu yang ada lebih singkat dan setelah
semuanya dikunjungi maka ia akan kembali ke toko pizza
tempatnya ia bekerja lagi.
### Problem 2
* Rute perjalanan dari kota A ke P dapat dilakukan dengan
berbagai macam alternatif. Dari sekian banyak alternatif yang
ada maka tentukanlah rute yang paling minimal untuk
ditempuh (misalkan minimal dalam hal jarak tempuh/waktu
tempuh) ?
### Model Graph
Jika kita lakukan analisis terhadap problem tadi, maka kita
akan buatkan model persoalannya ke dalam model Graph.
* `Problem 1` pada model Graph dikenal dengan problem
Travelling Salesman.
* `Problem 2` pada model Graph dikenal dengan problem
Shortest Path.
## Definisi Graf
Graf $G = (V, E)$, yang dalam hal ini:\
$~~~~~V = \text{himpunan simpul (*vertices*)}$\
$~~~~~~~~~= \{v_1, v_2, \dots, v_n\}$\
$~~~~~E = \text{himpunan sisi (*edges*) yang menghubungkan sepasang simpul}$\
$~~~~~~~~~= \{e_1, e_2, \dots, e_n\}$
### Contoh
* $V = \{1, 2, 3, 4, 5, 6\}$
* $E = \{\{1,2\},\{1,5\},\{2,3\},\{2,5\},\{3,4\},\{4,5\},\{4,6\}\}$
### Contoh Terapan Graf
#### Rangkaian listrik
#### Isomer Senyawa Kimia Karbon
#### Transportation System
#### Social Network
