TEKNIK INFORMATIKA

LINTSAN DAN SIRKUIT HAMILTON             Lintasan Hamilton ialah lintasan yang melalui tiap simpul di dalam graf tepat satu kali.               Sirkuit Hamilton ialah sirkuit yang melalui tiap simpul di dalam graf tepat satu kali, kecuali simpul asal (sekaligus simpul akhir) yang dilalui dua kali.             Graf yang memiliki sirkuit Hamilton dinamakan graf Hamilton, sedangkan graf yang hanya memiliki lintasan Hamilton disebut graf semi-Hamilton.   TEOREMA.             Di dalam graf lengkap G dengan n buah simpul (n >= 3 dan n ganjil), terdapat (n – 1)/2 buah sirkuit Hamilton yang saling lepas (tidak ada sisi yang beririsan). Jika n genap dan n   >= 4, maka di dalam G terdapat (n – 2)/2   buah sirkuit Hamilton yang saling lepas. Contoh. Sembilan anggota sebuah klub bertemu tiap hari untuk makan siang pada sebuah meja bundar. Mereka memutuskan duduk sedemikian sehingga setiap anggota mempunyai tetangga duduk berbeda pada setiap makan siang. Berapa hari p

KOMBINATORIAL             Kombinatorial adalah cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya. Kaidah Dasar Menghitung 1.     Kaidah Perkalian ( rule of product )             Misalkan percobaan 1 mempunyai p hasil percobaan, dan percobaan 2 mempunyai q hasil, maka bila percobaan 1 dan percobaan 2 dilakukan akan terdapat p × q hasil percobaan. 2.     Kaidah Penjumlahan ( rule of sum )             Misalkan percobaan 1 mempunyai p hasil percobaan, dan percobaan 2 mempunyai q hasil, maka bila percobaan 1 atau percobaan 2 dilakukan (hanya salah satu percobaan saja yang dilakukan) akan terdapat p + q hasil percobaan. Permutasi             Permutasi adalah jumlah urutan yang berbeda dari pengaturan objek-objek. Permutasi merupakan bentuk khusus aplikasi kaidah perkalian. Misalkan jumlah objek adalah n, maka Urutan pertama dipilih dari n objek, urutan kedua dipilih dari (n – 1) objek, urutan