Graf
DASAR – DASAR TEORI GRAF
• Kelahiran Teori Graf
Sejarah Graf : masalah jembatan Königsberg (tahun 1736)
Gbr 1. Masalah Jembatan Königsberg
Graf yang merepresentasikan jembatan Königsberg :
Simpul (vertex) à menyatakan daratan
Ruas (edge) à menyatakan jembatan
Bisakah melalui setiap jembatan tepat sekali dan kembali lagi ke tempat semula?
• Perjalanan Euler adalah :
Perjalanan dari suatu simpul kembali ke simpul tersebut dengan melalui setiap ruas tepat satu kali.
• Perjalanan Euler akan terjadi, jika :
- Graf terhubung.
- Banyaknya ruas yang datang pada setiap simpul adalah genap.
Sebuah graf atau graf tidak berarah G adalah sebuah pasangan G: = (V,E) yang memenuhi kondisi:
§ E adalah sebuah himpunan dari pasangan-pasangan sudut yang terpisah, yang dinamakan sisi atau garis.
Jenis-jenis graf
• Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis:
1. Graf sederhana (simple graf).
Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana.
2. Graf tak-sederhana (unsimple-graf/multigraf).
Graf yang mengandung ruas ganda atau gelung dinamakan graf tak-sederhana (unsimple graf atau multigrapf).
• Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:
1. Graf berhingga (limited graf)
Graf berhingga adalah graf yang jumlah simpulnya, n, berhingga.
2. Graf tak-berhingga (unlimited graf)
Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graf tak-berhingga.
• Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis:
1. Graf tak-berarah (undirected graf)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah.
2. Graf berarah (directed graf atau digraf)
Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah.
