ANALISIS PEWARNAAN r-DINAMIS PADA GRAF-GRAF KHUSUS

Abstract

Pewarnaan graf merupakan salah satu topik kajian pada teori graf. Pe- warnaan r-dinamis merupakan pengembangan dari pewarnaan k-warna dinamis yang diperkenalkan oleh Montgomery pada tahun 2002. Pewarnaan k-warna di- namis pada graf G merupakan pewarnaan titik pada graf G sebanyak k warna sedemikian hingga setiap titik berderajat minimum dua pada G setidaknya memi- liki dua warna berbeda dengan titik-titik ketetanggaannya. Nilai k terkecil dimana graf G memiliki pewarnaan k-warna dinamis disebut sebagai bilangan kromatik dinamis, disimbolkan dengan Âd(G). Graf-graf khusus yang digunakan dalam penelitian ini adalah graf Prisma, graf Circulant, graf Lintasan, graf Sikel, graf Roda, graf Bintang, graf Tangga, dan graf Friendship. Metode yang digunakan dalam penelitian ini adalah metode deduktif aksiomatik, yang diawali dengan istilah yang tidak dide¯nisikan dan istilah yang dide¯nisikan, kemudian dapat disusun pernyataan pangkal yang biasa disebut aksioma atau postulat. Setelah itu, disusun teorema-teorema ataupun de¯nisi-de¯nisi. Adapun teorema yang disusun harus dibuktikan melalui proses deduktif sehingga kebenarannya berlaku secara umum dalam ruang lingkupnya. Hasil penelitian ini berupa teorema baru mengenai pewarnaan titik r-dinamis dan pewarnaan sisi r-dinamis pada graf-graf khusus. Teorema yang dihasilkan adalah: a. Bilangan kromatik r-dinamis pewarnaan titik r-dinamis pada graf Prisma, Pn, dapat ditulis sebagai berikut: Â(Pn) = ( 2; untuk n genap 3; untuk n ganjil Âd(Pn) = ( 3; untuk n = 3k; k 2 N 4; untuk n lainnya Âr¸3(Pn) = 8>>< >>: 4; untuk n = 4k; k 2 N 6; untuk n = 3; 7; 11 5; untuk n lainnya ix yang telah dibuktikan pada Teorema 4.1.1; b. Misalkan G merupakan graf Circulant, yakni Cn(1; n 2 ), dimana n ¸ 4 dan n genap. Bilangan kromatik dinamis pewarnaan titik r-dinamis pada graf Circulant, Cn(1; n 2 ), dapat ditulis sebagai berikut: Â(Cn(1; n 2 )) = 8>>< >>: 4; untuk n = 4 2; untuk n = 4k + 2; k 2 N 3; untuk n = 4k + 4; k 2 N Âd(Cn(1; n 2 )) = 4 Âr¸3(Cn(1; n 2 )) = 8>>>>< >>>>: n; untuk n = 4; 6; 8 4; untuk n = 8k + 4; k 2 N 5; untuk n = 8k + 6; k 2 N 6; untuk n lainnya yang telah dibuktikan melalui pembuktian Teorema 4.1.2; c. Misalkan G merupakan graf Circulant, yakni Cn(1; 2), dimana n ¸ 5. Bi- langan kromatik dinamis pewarnaan titik r-dinamis pada graf Circulant, Cn(1; 2), dapat ditulis sebagai berikut: Â(Cn(1; 2)) = Â2(Cn(1; 2)) = 8>>< >>: 5; untuk n = 5 3; untuk n = 3k; k 2 A 4; untuk n lainnya Â3(Cn(1; 2)) = ( 4; untuk n = 4k; k 2 A 5; untuk n lainnya Âr¸4(Cn(1; 2)) = 8>>>>< >>>>: n; untuk 5 · n · 9 5; untuk n = 5k + 5; k 2 A 6; untuk n = 5k + 6; 5k + 7; k 2 A 7; untuk n = 5k + 8; 5k + 9; k 2 A yang telah dibuktikan pada Teorema ??; d. Jika G merupakan graf hasil operasi join antara Pn dan Cm, dinotasikan dengan Pn + Cm maka bilangan kromatik r-dinamis graf G adalah sebagai x berikut: Â4(Pn + Cm) = ( 5; untuk m = 3k; k 2 A 6; untuk m lainnya Â5(Pn + Cm) = 8>>< >>: 6; untuk m = 3 8; untuk m = 5 7; untuk m lainnya Âr¸6(Pn+Cm) = ( r + m ¡ 2; untuk 3 · m · r ¡ 2;m ¸ r ¡ 1; n ¸ m ¡ 1 2r ¡ 3; untuk m lainnya; n ¸ r ¡ 1 yang telah dibuktikan pada Teorema 4.1.4; e. Misalkan G merupakan graf hasil operasi korona antara Pn dan Cm, yaitu Cm ¯ Pn. Jika n ¸ 2, m ¸ 3, and r ¸ 4 maka bilangan kromatik r-dinamis graf G adalah sebagai berikut: Âr¸4(Cm ¯ Pn) = 8>>>>< >>>>: 4; untuk m 6= 5; n = 1; 5; untuk n = 2 dan m = 5; n = 1; n + 3; untuk 3 · n · r ¡ 3; r + 1; untuk n lainnya; yang telah dibuktikan pada Teorema 4.1.5; f. Misalkan G merupakan graf hasil operasi korona antara Pn dan Cm, yaitu Pn ¯ Cm. Jika n ¸ 2, m ¸ 3, dan r ¸ 6 maka bilangan kromatik r-dinamis graf G adalah sebagai berikut: Âr¸6(Pn ¯ Cm) = ( m + 3; untuk 3 · m · r ¡ 3; r + 1; untuk m lainnya; yang telah dibuktikan pada Teorema 4.1.6; g. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Lintasan, Pn, dapat ditulis sebagai berikut: ¸(Pn) = 2; n ¸ 2 ¸2(Pn) = ¸r(Pn) = 3; n ¸ 2; r ¸ 2 yang telah dibuktikan pada Teorema 4.2.1; h. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Sikel, Cn; n ¸ 3, dapat ditulis sebagai berikut: ¸(Cn) = ( 2; untuk n genap 3; untuk n ganjil ¸r¸2(Cn) = 8>>< >>: 3; untuk n = 3k; k 2 N 4; untuk n = 3k + 1; k 2 N 5; untuk n = 3k + 2; k 2 N yang telah dibuktikan pada Teorema 4.2.2; i. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Bintang, Sn; n ¸ 3, dapat ditulis sebagai berikut: ¸r¸1(Sn) = n yang telah dibuktikan pada Teorema 4.2.3; j. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Roda, Wn; n ¸ 5, dapat ditulis sebagai berikut: ¸r·n¡1(Wn) = n; untuk 1 · r · n ¡ 1 ¸r¸n(Wn) = 8>>< >>: 10; untuk n = 5; r ¸ n n + 3; untuk untukn = 3k + 3; k 2 N; r ¸ n n + 4; untuk n lainnya; r ¸ n yang telah dibuktikan pada Teorema 4.2.4; k. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Prisma, Pn, dapat ditulis sebagai berikut: ¸(Pn) = ¸2(Pn) = ( 2; untuk n genap 3; untuk n ganjil ¸3(Pn) = ( 4; untuk n = 3 5; untuk n lainnya ¸r¸4(Pn) = 8>>>>< >>>>: 9; untuk n = 3 6; untuk n = 4k; k 2 N 8; untuk n = 5; 6; 4k + 7; k 2 N 7; untuk n lainnya yang telah dibuktikan pada Teorema 4.2.5; l. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Tangga, Ln; n ¸ 3, adalah: ¸(Ln) = ¸2(Ln) = 3 ¸3(Ln) = 5 ¸4(Ln) = ¸r(Ln) = 6 yang telah dibuktikan pada Teorema 4.2.6; h. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Sikel, Cn; n ¸ 3, dapat ditulis sebagai berikut: ¸(Cn) = ( 2; untuk n genap 3; untuk n ganjil ¸r¸2(Cn) = 8>>< >>: 3; untuk n = 3k; k 2 N 4; untuk n = 3k + 1; k 2 N 5; untuk n = 3k + 2; k 2 N yang telah dibuktikan pada Teorema 4.2.2; m. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Friendship, Fn, adalah: ¸r·2n¡1(Fn) = 2n ¸r¸2n(Fn) = 2n + 1 yang telah dibuktikan pada Teorema 4.2.7; n. Misalkan G adalah graf hasil operasi amalgamasi dari graf Lintasan Pn, dinotasikan G = amal(Pn; v;m); n ¸ 2;m ¸ 3, maka bilangan kromatik sisi r-dinamis pada graf G adalah: ¸(amal(Pn; v;m)) = ¸2(amal(Pn; v;m)) = m ¸r¸3(amal(Pn; v;m)) = m + 1 yang telah dibuktikan pada Teorema 4.2.8; o. Jika T adalah graf Pohon, maka berlaku: Â(Cn + T) = Â2(Cn + T) = Â3(Cn + T) = ( 4; untuk n genap 5; untuk n ganjil yang telah dibuktikan pada Teorema 4.3.1; p. Misalkan G adalah graf yang merupakan hasil operasi join graf G1 dan G2, maka pada graf G berlaku pewarnaan titik r-dinamis sebagai berikut: Â(G1 + G2) = Â2(G1 + G2) = ¢ ¢ ¢ = Âr(G1 + G2) = Â(G1) + Â(G2) dimana r = minfjc(N(v(G1)))j; jc(N(v(G2)))jg+minfÂG1 ; ÂG2g, yang telah dibuktikan pada Teorema 4.3.2; q. Jika G merupakan graf Pohon maka ¸r(G) = minfr; maxfd(u)+d(v)¡2gg+ 1, dimana r ¸ maxfd(u)+d(v)¡2gg, yang telah dibuktikan pada Teorema 4.3.3. Dari penelitian juga terdapat dugaan mengenai pewarnaan titik r-dinamis pada graf Pn + Cm sebagaimana tertulis pada Dugaan 4.3.1: Misalkan G adalah graf yang merupakan hasil operasi join graf G1 dan G2, maka Âr(G1 + G2) ¸ Âr(G1) + Âr(G2).