KAJIAN MENGENAI SYARAT CUKUP POLYNOMIAL KROMATIK GRAF TERHUBUNG MEMILIKI AKAR-AKAR KOMPLEKS STUDY ON SUFFICIENT CONDITION FOR THE CHROMATIC POLYNOMIAL OF CONNECTED GRAPH HAS COMPLEX ROOTS Yuni Dewi Purnama Sari (1208 100 051) Dosen Pembimbing: Dr. Darmaji, S. Si, M. ST dan Soleha, S.Si, M.Si Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Teknologi Sepuluh Nopember Surabaya
2014
PENDAHULUAN
Latar Belakang GRAF
PEWARNAAN GRAF
POLYNOMIAL KROMATIK
definisi Masalah pewarnaan pertama kali muncul pada lebih dari 150 tahun yang lalu, yaitu mengenai Penetapan warna pada simpul masalah empat-warna, yang mempertanyakan apakah sedemikian hingga dua simpul yangsebarang peta dapatbertetangga diwarnai dengan tidakwarna lebih yang dari 4 warna. menerima berbeda
akan dikaji syarat cukup polinomial kromatik suatu graf terhubung sehingga memiliki akar yang bernilai kompleks berdasarkan [4]
Polinomial kromatik menghitung banyaknya cara suatu graf dapat diwarnai dengan menggunakan bilangan yang telah diberikan.
Akar polinomial kromatik yang disebut juga dengan akar kromatik dapat bernilai real maupun kompleks Letak akar kromatik kompleks terpadatkan pada seluruh bidang kompleks
Rumusan Masalah
Apa saja syarat cukup supaya polinomial kromatik dari graf terhubung memiliki akar-akar yang bernilai kompleks?
Batasan Masalah Syarat cukup yang akan dikaji terbatas pada: Subgraf segitiga Subgraf quadilateral murni Subgraf graf lengkap K4
Tujuan
Mengaji syarat cukup supaya suatu polinomial kromatik dari graf terhubung memiliki akar yang bernilai kompleks
Manfaat
menambah pengetahuan mengenai apa saja syarat cukup supaya polynomial kromatik suatu graf terhubung dapat memiliki akar yang bernilai kompleks
TINJAUAN PUSTAKA
Istilah dan Notasi dalam Graf Bertetangga
Terkait
Order
Jika u dan v adalah simpul dari graf G, u disebut bertetangga dengan v jika terdapat sebuah sisi yang menghubungkan u dan v suatu simpul u dikatakan terkait dengan sisi e jika u adalah titik ujung dari e. Dalam hal ini, dapat juga dikatakan e terkait dengan u jika u menjadi titik ujung dari e. Banyaknya simpul dalam graf G disebut order G
Ukuran
Banyaknya sisi dalam graf G disebut ukuran (size) G
Derajat
Derajat dari sebuah simpul v adalah banyaknya sisi yang terkait dengan v
Istilah dan Notasi dalam Graf Subgraf Subgraf dari suatu graf G adalah sebuah graf yang setiap simpulnya merupakan simpul di G, dan setiap sisinya juga merupakan sisi di G.
Isomorfik Dua buah graf G1 dan G2 disebut dengan isomorf jika dapat dibentuk pemetaan f:V(G1 )→V(G2) sedemikian hingga ketetanggaan di G1 dipertahankan di G2
Istilah dan Notasi dalam Graf Graf Terhubung
Graf Sikel
Graf Segitiga
Istilah dan Notasi dalam Graf Graf Quadilateral
Graf Lengkap
Istilah dan Notasi dalam Graf Graf Pohon
Graf Roda
Istilah dan Notasi dalam Graf Graf Garis ( Line Graph) Graf garis dari G yang dinotasikan dengan L(G) didefinisikan sebagai suatu graf yang masingmasing simpul L(G) mewakili sisi G, dan dua simpul L(G) adalah bertetangga jika dan hanya jika kedua sisi G yang diwakili tersebut terkait.
Graf Lengkap K4
Graf garis L(K4)
Polinomial
Polinomial
Polinomial
Polinomial
Polinomial
Polinomial
Polinomial
Polinomial
Polinomial
Polynomial Kromatik Graf Kosong dengan order n
Graf Lengkap dengan order n
Pohon dengan order n
Graf Sikel dengan order n
Graf Roda dengan order n
Koefisien Polynomial Kromatik
Koefisien Polynomial Kromatik
Koefisien Polynomial Kromatik
Metode Penelitian
1. Studi literatur
2. Mengaji Teorema dan Teori Dasar yang Digunakan untuk Membuktikan setiap Syarat Cukup
3. Membuktikan bahwa Syarat Cukup Terpenuhi
4. Penarikan Kesimpulan
Pembahasan
Teorema 4.1
Bukti Teorema 4.1
Bukti Teorema 4.1
Bukti Teorema 4.1
Bukti Teorema 4.1
Bukti Teorema 4.1
Bukti Teorema 4.1
Contoh Teorema 4.1
Contoh Teorema 4.1
Contoh Teorema 4.1
Preposisi 4.2
Teorema 4.3
Teorema 4.3
Contoh Teorema 4.3
Preposisi 4.4
Contoh Preposisi 4.4
Contoh Preposisi 4.4
Penutup
Kesimpulan
Saran
Daftar Pustaka
Daftar Pustaka
