# data[].attributes.body
What is graph?

Graf merupakan pokok bahasan yang sudah tua, namun memiliki banyak terapan sampai saat ini. Graf digunakan untuk
mempresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut.

Representasi visual dari graf adalah dengan menyatakan objek sebagai noktah, bulatan atau titik yang disebut simpul (verteks).

Sedangkan hubungan antara objek dinyatakan dengan garis yang disebut sisi ( edge ).

# data[].attributes.body
Masalah Jembatan Konigsberg (sekarang Kaliningrad) adalah masalah pertama tentang Graf (Tahun 1736)

Di kota Konisberg ada Sungai Pregal yang mengitari Pulau lalu bercabang menjadi 2 buah anak sungai

Ada 7 jembatan yg menghubungkan daratan yg dibelah oleh sungai tersebut.

Permasalahannya: apakah bisa melewati 7 jembatan  tepat satu kali dan kembali ke tempat semula ?

Euler memodelkan masalah ini kedalam graf, dengan daratan dinyatakan sbg titik (simpul/vertex), dan jembatan diyatakan sbg garis (edge)

Jawabanya adalah Tidak Bisa
Orang tidak mungkin melalui ketujuh jembatan itu

masing-masing satu kali dan kembali lagi ke tempat

asal keberangkatan jika derajat setiap simpul

tidak seluruhnya genap

# data[].attributes.body
Graf G didefinisikan sebagai pasangan himpunan (V,E), ditulis dengan notasi G=(V,E), yang dalam hal ini V adalah himpunan tidak kosong dari simpul-simpul (vertice atau node) dan E adalah himpunan sisi (edge atau arcs) yang menghubungkan sepasang simpul.

Dari definisi diata dapat dinyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong.

Jadi sebuah graf dimugkinkan tidak memiliki sisi satu buah pun, tetapi simpul harus ada (minimal 1). Graf yang terdiri dari 1 simpul tanpa sebuah sisi dinamakan graf trivial.

simpul dapat dinomori dengan huruf (a, b, c,..., v,w, ...) ; bilangan asli (1, 2, 3, ...) atau gabungan keduanya.

Sedangkan sisi yang menghubungkan simpul u dengan simpul v dinyatakan dengan pasangan (u,v) atau dinyatakan dengan lambang e1, e2, ... .

Atau dapat ditulis e=(u,v)

# data[].attributes.body
Graf G₁:

simpul V={1,2,3,4},

sisi E={(1,2),(1,3),(2,3),(2,4),(3,4)}

Graf G₂:

V={1,2,3,4},

E={(1,2),(1,3),(1,3),(2,3),(3,4),(3,4),(2,4)} >> himp. Ganda

Graf G₃:

V={1,2,3,4},

E={(1,2),(1,3),(1,3),(2,4),(2,3),(3,4),(3,4),(3,3)}

# data[].attributes.body
Pada G₂ sisi e₃=(1,3) dan sisi e₄=(1,3) dinamakan sisi-ganda (multiple edges atau paralel edges) karena kedua sisi ini menghubungkan dua buah simpul yang sama, yaitu simpul 1 dan simpul 3.

Pada G₃ sisi e₈=(3,3) dinamakan gelang atau kalang (loop) karena ia berawal dan berakhir pada simpul yang sama.

# data[].attributes.body
1. Graf Sederhana
>>> Tidak mengandung loop atau sisi ganda

2. Graf tak sederhana
>>> Mengandung loop atau sisi ganda

Graf ganda : mengandung sisi ganda

Graf semu : mengandung loop ataupun sisi ganda

3. Graf tak berarah
>>> Sisinya tidak punya arah
>>> Urutan simpul tidak diperhatikan , (u,v)=(v,u)

4. Graf berarah
>>> Setiap sisinya diberi arah
>>> Urutan simpul diperhatikan (u,v)≠(v,u)

# data[].attributes.body
Jumlah simpul pada graf disebut dengan Kardinalitas graf dinyatakan dengan

n=|V|

Jumlah sisi graf dinyatakan dengan

m=|E|

Contoh :
pada G1 >> n=4  ,  m=5 (lihat gambar pada contoh graf)

# data[].attributes.body
read(x);
while x<> 9999 do
begin
if x< 0 then
   Writeln(‘Masukan tdk boleh negatif’)
else
x:= x+10;
read(x);
end;
writeln(x);

Flowchart program dimodelkan dengan graf berarah = graf alir (flow graph)

Note:
Simpul = pernyataan yg dievaluasi
Busur   = aliran kendali program ke pernyataan berikutnya