Graf planar adalah graf yang dapat digambarkan pada bidang datar dengan sisi-sisi yang tidak saling memotong. Reprsentasi dari graf planar disebut dengan graf bidang. Sisi-sisi pada graf graf bidang membagi bidang datar menjadi beberapa wilayah atau muka.
RUMUS EULER
Rumus euler sebagai berikut:
n - e + f = 2
atau
f = e - n + 2
keterangan:
e = jumlah sisi
n = jumlah simpul
TEOREMA KURATOWSKI
Sifat graf kuratowski :
- Kedua graf kuratowski adalah graf teratur
- Kedua graf kuratowski adalah graf tidak planar
- Penghapusan sisi atau simpul dari graf kuratowski menyebabkannya menjadi graf planar
- 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
HOMEOMORFIK
adalah jika salah satu dari kedua graf dapat diperoleh dari graf yang lain dengan cara menyisipkan dan/atau membuang secara berulang-ulang simpul berderajat 2.
LINTASAN dan SIRKUIT EULER
Lintasan euler adalah lintasan yang melalui masing-masing sisi di dalam graf tepat satu kali. Jika kembali ke simpul asal membentuk lintasan tertutup disebut sirkuit euler.
Graf yang mempunyai sirkuit euler disebut graf euler. Graf yang mempunyai lintasan euler dinamakan graf semi euler.
LINTASAN dan SIRKUIT HAMILTON
Lintasan hamilton adalah lintasan yang melalui tiap simpul di dalam graf tepat satu kali. Jika kembali ke simpul asal membentuk lintasan tertutup disebut sirkuit hamilton.
Graf yang memiliki sirkuit hamilton disebut graf hamilton sedangkan graf yang hanya memiliki lintasan hamilton disbeut graf semi hamilton.
Tidak ada komentar:
Posting Komentar