Graf (Graph) - Matematika Diskrit

13.16 in kuliah, matematika diskrit

Graf  (graph) adalah himpunan benda-benda yang disebut simpul (vertex atau node) yang terhubung oleh sisi (edge) atau busur (arc). Graf trival (satu titik tampa sisi satu pun)
Jenis graf antara lain :
1. Berdasarkan ada tidaknya sisi ganda
    a. graf sederhana
    b. graf tidak sederhana
        1)graf ganda (multigraf)
        2)graf semu(pseudograf) adalah graf yang mengandung gelang (loop)
           graf sedrehana --> graf ganda
           graf ganda -x-> graf sederhana

2. Berdasarkan orientasi arah
    a. Graf tak berarah (undirect graf) adalah graf yang orientasi sisinya tidak mempunyai arah
    b. Graf berarah(direct graf) adalah graf orientasi sisinya mempunyai arah
        sisi yang berarah

Terminologi dasar
-----------------------------
1. Bertetangga (adjacent) adalah 2 buah graf yang terhubung langsung dengan sebuah sisi.
2. Bersisian (insident) adalah sembarang sisi yang bersisian dengan simpul u dan v
3. Simpul terpencil (isolated vertex)  adalah simpul yang tidak bertetanggaan dengan simpul2 lainnya
4. Graf kosong (null graph or empty graph) adalah graf yang himpunan sisinya adalah himpunan kosong
5. Derajat (degree) adalah suatu simpul pada graf takberarah adalah jumlah sisi yang bersisian dengan simpul tersebut
6. Lintasan (path) adalah panjang dari simpul awal hingga akhir
7. Siklus (cycle)/ sirkuit (circuit) adalah lintasan yang berawal dan berahir pada simpul yang sama
8. Terhubung (connected) adalah dua simpul yang terhubung
9. Upagraf (subgraph) -->
   dan komplemen upagraf -->
10. Upagraf merentang (spanning subgraf)
11. Cut set
12. Graf berbobot (Weight graph) adalah graf yang setiap sisinya diberi sebuah harga (bobot)

Beberapa graf sederhanga khusus
-------------------------------------------------------
1. Graf lengkap (complete graph) adalah graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya.
2. Graph lingkaran adalah graph sederhana yang setiap simpulnya berderajat dua
3. Graph teratur (regular graph) adalah setiap simpulnya mempunyai derajat yang sama
4. Graph bipartit (bipartite graph) adalah graph yang himpunan simpulnya dapat dikelompokkan menjadi 2 himpunan

Representasi graph
-------------------------------
1. Matriks ketetanggaan (adjacency matrix)
2. Matriks bersisian (incidency matrix)
3. Senarai ketetanggaan (adjacency list)

Graph isomorfik
--------------------------
Adalah dua buah graph, G1 dan G2 terdapat korespodensi satu-satu antara simpul-simpul keduanya.

Graph planar dan graph bidang
---------------------------------------------------
Graf planar adalah graf yang dapat digambarkan pada bidang datar dengan sisi yang tidak saling memotong (berpotongan). sedangkan graf bidang adalah representasi dari graf planar

Rumus euler
n-e-f=2

e=jumlah sisi
n=jumlah simpul

Teorema kuratowski
---------------------------------
Graf g adalah tidak planar jika dan hanya jika ia mengandung upagraf yang isomorfik dg k5 atau k3,3 atau homeomorfik dengan salah satu dari keduanya.
dalam literatur dalam graf, matematikawan Polandia, Kasimir Kuratowski menemukan sifat yang unik:
1. graf lengkap yang mempunyai 5 buah simpul(K5) adalah graf tidak planar
2. graf terhubung teratur dengan 6 buah simpul dan 9 buah sisi (K3,3) adalah graf tidak planar

Sifat graf kuratowski
1. kedua graf kuratowski adalah graf teratur
2. kedua graf kuratowski adalah graf tidak planar
3. penghapusan sisi atau simpul dari graf kuratowski menyebabkan menjadi graf planar
4. graf kuratowski pertama adalah graf tidak planar dengan jumlah simpul minimum. dan graf kuratowski kedua adalah graf tidak planar dengan jumlah sisi minimum. keduanya adalah graf tidak planar paling sederhana.

Graph dual (dual graph)
--------------------------------------
Adalah graf yang terbentuk dengan cara penggambaran di titik luar dari graf yang asli

Lintasan dan sirkuit euler
-----------------------------------------
Lintasan euler adalah lintasan yang melalui masing-masing sisi di dalam graf tepat satu kali. bila lintasan tersebut kembali ke asal, sehingga membentuk lintasan tertutup maka disebut sirkuit euler.

Lintasan dan sirkuit hamilton
-----------------------------------------------
Lintasan hamilton adalah lintasan yang melalui tiap simpul didalam graf tepat satu kali. bila lintasan itu kembali ke asal membentuk lintasan tertutup(sirkuit), maka lintasan tersebut adalah sirkuit hamilton.

setiap graf lengkap adalah graf hamilton


Lintasan terpendek (shortest path)
-------------------------------------------------------
Graf yang digunakan mencari lintasan terpendek adalah graf berbobot (weighted graph).
ada beberapa macam persoalan lintasan terpendek antara lain :
1. Lintasan terpendek antara 2 buah simpul tertentu
2. Lintasan terpendek antara semua pasangan simpul
3. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain.
4. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu.