Langsung ke konten utama

TI POLITALA MATDIS 1C


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 pengaturan tersebut dapat dilaksanakan?

Jawaban: Jumlah pengaturan tempat duduk yang berbeda adalah (9 – 1)/2 = 4.

Beberapa graf dapat mengandung sirkuit Euler dan sirkuit Hamilton sekaligus, mengandung sirkuit Euler tetapi tidak mengandung sirkuit Hamilton, dan sebagainya.

PEWARNAAN GRAF
-Ada dua macam: pewarnaan simpul, dan pewarnaan sisi Hanya dibahas perwarnaan simpul
-Pewarnaan simpul: memberi warna pada simpul-simpul graf sedemikian sehingga dua simpul bertetangga mempunyai warna berbeda

-Aplikasi pewarnaan graf: mewarnai peta.
-Peta terdiri atas sejumlah wilayah.
-Wilayah dapat menyatakan kecamatan, kabupaten, provinsi, atau negara.
-Peta diwarnai sedemikian sehingga dua wilayah bertetangga mempunyai warna berbeda.

Graf kosong
            Karena semua simpul tidak terhubung, jadi untuk mewarnai semua simpul cukup dibutuhkan satu warna saja.
                                               

Graf lengkap
Semua simpul saling terhubung sehingga diperlukan n buah warna.


Graf bipartit
Kmn mempunyai x( G ) = 2, satu untuk simpul-simpul di himpunan V 1 dan satu lagi untuk simpul-simpul di V 2.

Untuk graf-graf yang lain tidak dapat dinyatakan secara umum bilangan kromatiknya.


Materi lainnya:
  • Graf Planar dan Graf Bidang
https://cucusulaiman.blogspot.com/2018/12/graf-planar-planar-graph-dan-grafbidang.html
  • Reprentasi Graf dan Graf Isomorfik
https://anggrainidians.blogspot.com/2018/12/representasi-graf-matriksketetanggaan.html
  • Definisi Graf dan  Graf Bipartite
https://maysarahhmay.blogspot.com/2018/12/matdis-graf.html

Komentar

Posting Komentar

Postingan populer dari blog ini

IDE.Visual Basic.Net

IDE Visual Basic .NET     1.1    Pengertian Visual Basic Visual Basic merupakan bahasa pemrograman yang sangat mudah dipelajari, dengan teknik pemrograman visual yang memungkinkan penggunanya untuk berkreasi lebih baik dalam menghasilkan suatu program aplikasi   1.2    Pengenalan Visual Basic 1.        Visual Basic adalah salah satu bahasa pemrograman. 2.        Bahasa pemrograman adalah perintah-perintah yang dimengerti oleh komputer untuk melakukan tugas-tugas tertentu. 3.        Dikembangkan oleh Microsoft pada tahun 1991 4.        Merupakan pengembangan dari pendahulunya yaitu bahasa pemrograman BASIC (Beginner’s All-purpose Symbolic Instruction Code) 5.        Bahasa BASIC diciptakan oleh Professor John Kemeny dan Thomas Kurtz dari Kampus Darmouth pada pertengahan tahun 1960-an (Deitel&Deitel, 1999)   Apa itu Visual? 1.        VISUAL adalah cara yang digunakan untuk membuat Graphical User Interface (GUI) 2.        Tidak perlu menuliskan intruksi pemrograman dalam kode
Posting Komentar
Baca selengkapnya

REMASTERING LINUX UBUNTU

SEJARAH SISTEM OPERASI LINUX Pada tahun 1969, Ken Thompson dan Dennis Ritchie (juga adalah developer bahasa C), para peneliti di AT&T Bell Laboratorium Amerika, membuat sistem operasi UNIX, cikal bakal dari Linux. UNIX mendapatkan perhatian besar karena merupakan sistem operasi pertama yang dibuat bukan oleh hardware maker. Selain itu juga karena seluruh source code-nya dibuat dengan bahasa C, sehingga mempermudah pemindahannya ke berbagai platform. Dalam waktu singkat UNIX berkembang dalam dua jalur : UNIX yang dikembangkan oleh Universitas Berkeley dan yang dikembangkan oleh AT&T. Setelah itu mulai banyak perusahaan yang melibatkan diri, dan terjadilah persaingan yang melibatkan banyak perusahaan untuk memegang kontrol dalam bidang sistem operasi. Persaingan ini menyebabkan perlu adanya standarisasi. Dari sini lahirlah proyek POSIX yang dimotori oleh IEEE (The Institute of Electrical and Electronics Engineers) yang bertujuan untuk menetapkan spesifikasi standar
Posting Komentar
Baca selengkapnya

PERCABANGAN

Statemen ini digunakan untuk melakukan aksi setelah melakukan pengujian terhadap suatu kondisi. Pernyataan dalam blok statemen hanya akan dilaksanakan ketika kondisi pengetesan/pengujian bernilai benar. Statement If...Then memiliki beberapa sintaks/cara penulisan sesuai dengan jumlah pernyataan yang akan dieksekusi. 1.        If...Then dengan Kondisi dan Pernyataan Tunggal Text Box: If <kondisi> Then <Pernyataan> Contoh :If Nilai >= 60 Then Keterangan = “Lulus”  2.        If...Then dengan Pernyataan Jamak Text Box: If <Kondisi> Then<Pernyataan_1><Pernyataan_2>..<Pernyataan_n> End If Contoh :If Nilai >= 60 Then Keterangan = “Lulus” Ucapan = “Selamat”End If 3.        If...Then dengan 2 kondisi Text Box: <Pernyataan_Jika_Kondisi_Benar> Else<Pernyataan_Jika_Kondisi_Salah> End If Contoh:If Nilai >= 60 Then Keterangan = “Lulus” Ucapan = “Selamat”ElseKeterangan
Posting Komentar
Baca selengkapnya