Please use this identifier to cite or link to this item: https://repository.unej.ac.id/xmlui/handle/123456789/84214
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorDAFIK-
dc.contributor.advisorPRIHANDOKO, Antonius Cahya-
dc.contributor.authorFATIHAH, Novian Nur-
dc.date.accessioned2018-02-09T02:01:10Z-
dc.date.available2018-02-09T02:01:10Z-
dc.date.issued2018-02-09-
dc.identifier.nimNIM151820101008-
dc.identifier.urihttp://repository.unej.ac.id/handle/123456789/84214-
dc.description.abstractPewarnaan merupakan salah satu topik penelitian yang banyak diminati dalam teori graf. Pewarnaan graf, merupakan kasus khusus dari pelabelan graf yang memiliki tiga macam aspek yaitu pewarnaan titik (vertex coloring ), pe- warnaan sisi (edge coloring ), dan pewarnaan wilayah (region coloring ). Pewar- naan r-dinamis merupakan pengembangan dari pewarnaan k-warna dinamis yang diperkenalkan oleh Montgomery pada tahun 2002. Pewarnaan k-warna dinamis pada graf G merupakan pewarnaan titik pada graf G sebanyak k warna sedemikian hingga setiap titik berderajat minimum dua pada G setidaknya memiliki 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 χ(G). Penelitian ini meneliti tentang pewarnaan titik r-dinamis pada graf hasil operasi comb sisi serta pengembangannya pada pewarnaan sisi r-dinamis. Graf hasil operasi comb sisi yaitu salah satu operasi graf yang menerapkan definisi perpangkatan. Graf hasil operasi comb sisi dapat diartikan dengan menempelkan sisi pada suatu graf dengan salah satu sisi pada graf lain yang dilambangkan dengan G H, dimana G dan H merupakan sebarang graf. Adapun graf-graf khusus yang dimaksud dalam pewarnaan r-dinamis diantaranya adalah graf lin- tasan (path), graf lingkaran (cycle), graf buku segitiga (triangular book), dan graf bintang (star). Hasil penelitian ini adalah pewarnaan titik r-dinamis dan pe- warnaan sisi r-dinamis dari hasil operasi comb sisi graf G H dengan graf G merupakan graf lingkaran dan graf H merupakan semua graf khusus. Metode yang digunakan dalam penelitian ini adalah metode deduktif ak- siomatik, yang diawali dengan istilah yang tidak didefinisikan dan istilah yang didefinisikan, kemudian dapat disusun pernyataan pangkal yang biasa disebut aksioma atau postulat. Setelah itu, disusun teorema-teorema ataupun definisi- definisi. 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 hasil operasi comb sisi Cn H. Dari penelitian ini didapatkan Observasi, Teorema, Lemma, dan Dugaan yang di- hasilkan sebagai berikut: a. Misalkan G merupakan graf Cn H, maka ∆(G) ≥ ∆(H). Yang telah dibuktikan pada Observasi 4.1.1; b. Misalkan G merupakan graf Cn H, maka ∆(G) ≥ ∆(H) + 1. Yang telah dibuktikan pada Observasi 4.1.2; c. Misalkan G merupakan graf Cn Pm untuk n ≥ 3, m ≥ 3 dan sisi y1y2 sebagai sisi cangkok pada graf Pm. Bilangan kromatik r-dinamis pewarnaan titik pada Cn Pm dapat ditulis sebagai berikut:  χr (Cn Pm) =  3 ; 1 ≤ r ≤ 2 4 ; r ≥ 3 5 ; r ≥ 3 dan n ≡ 0(mod 5) yang telah dibuktikan pada Teorema 4.1.1; d. Misalkan G merupakan graf Cn Pm untuk n ≥ 3, m ≥ 4 dan sisi yiyi+1 sebagai sisi cangkok pada graf Pm dengan 2 ≤ i ≤ m−1. Bilangan kromatik r-dinamis pewarnaan titik pada Cn Pm dapat ditulis sebagai berikut:  χr (Cn Pm) =  3 ; 1 ≤ r ≤ 2 4 ; r = 3 5 ; r ≥ 4 yang telah dibuktikan pada Teorema 4.1.2; e. Misalkan G merupakan graf Cn Cm untuk n ≥ 3 dan m ≥ 3 dan sisi cangkok pada graf Cm. Bilangan kromatik r-dinamis pewarnaan titik pada Cn Cm dapat ditulis sebagai berikut:  χr (Cn Cm) =  3 ; 1 ≤ r ≤ 2 4 ; r = 3 5 ; r ≥ 3 yang telah dibuktikan pada Teorema 4.1.3; f. Misalkan G merupakan graf Cn Sm untuk n ≥ 3 dan m ≥ 3 dan sisi cangkok pada graf Sm. Bilangan kromatik r-dinamis pewarnaan titik pada Cn Sm dapat ditulis sebagai berikut:  χr (Cn Sm) =  3 ; 1 ≤ r ≤ δ + 1 r + 1 ; δ + 2 ≤ r ≤ ∆ ∆ + 1 ; r ≥ ∆ yang telah dibuktikan pada Teorema 4.1.4; f. Misalkan G merupakan graf Cn Amal(C3, P2, m) untuk n ≥ 3 dimana sisi cangkok p2 pada m. Bilangan kromatik r-dinamis pewarnaan titik pada Cn Amal(C3, P2, m) dapat ditulis sebagai berikut:  χr (Cn Amal(C3, P2, m)) =  3 ; 1 ≤ r ≤ δ r + 1 ; δ + 1 ≤ r ≤ ∆ − 1 ∆ + 1 ; r ≥ ∆ yang telah dibuktikan pada Teorema 4.1.5; g. Misalkan G merupakan graf Cn Pm untuk n ≥ 3, m ≥ 3 dan sisi y1y2 sebagai sisi cangkok pada graf Pm. Bilangan kromatik r-dinamis pewarnaan sisi pada Cn Pm dapat ditulis sebagai berikut:  λr =  3 ; untuk 1 ≤ r ≤ 2 5 ; untuk n ≡ 0(mod 5), r ≥ 3 6 ; untuk n /= 0(mod 5), r ≥ 3 yang telah dibuktikan pada Teorema 4.2.1; h. Misalkan G merupakan graf Cn Pm untuk n ≥ 3, m ≥ 4 dan sisi yiyi+1 sebagai sisi cangkok pada graf Pm dengan 2 ≤ i ≤ m−1. Bilangan kromatik r-dinamis pewarnaan sisi pada Cn Pm dapat ditulis sebagai berikut:   λr =   4 ; untuk 1 ≤ r ≤ 3 5 ; untuk r = 4 8 ; untuk i = genap, r ≥ 5 9 ; untuk i = ganjil, r ≥ 5 yang telah dibuktikan pada Teorema 4.2.2; i. Misalkan G merupakan graf Cn Cm untuk n ≥ 3 dan m ≥ 3 dan sisi cangkok pada graf Cm. Bilangan kromatik r-dinamis pewarnaan sisi pada Cn Cm dapat ditulis sebagai berikut:       λr =       4 ; untuk 1 ≤ r ≤ 3 6 ; m /= 4 untuk semua n dan m /= 5 untuk n ≡ 1(mod 3); 4 ≤ r ≤ 5 7 ; m = 4 untuk semua n dan m = 5 untuk n ≡ 1(mod 3); 4 ≤ r ≤ 5 8 ; n ≡ 1(mod 3) dan n ≡ 2(mod 3); r ≥ 6 9 ; n ≡ 0(mod 3); r ≥ 6 yang telah dibuktikan pada Teorema 4.2.3; j. Misalkan G merupakan graf Cn Sm untuk n ≥ 3 dan m ≥ 3 dan sisi cangkok pada graf Sm. Bilangan kromatik r-dinamis pewarnaan sisi pada Cn Sm dapat ditulis sebagai berikut:  λr =  ∆ ; 1 ≤ r ≤ ∆ − 1 2∆ ; ∆ ≤ r ≤ ∆ + 2 2∆ + 1 ; r ≥ ∆ + 3en_US
dc.language.isoiden_US
dc.relation.ispartofseries151820101008;-
dc.subjectPEWARNAAN TITIKen_US
dc.subjectSISI r-DINAMISen_US
dc.subjectGRAF HASIL OPERASI COMB SISI Cn D Hen_US
dc.titleANALISIS PEWARNAAN TITIK DAN SISI r-DINAMIS PADA GRAF HASIL OPERASI COMB SISI Cn Hen_US
dc.typeUndergraduat Thesisen_US
Appears in Collections:UT-Faculty of Mathematics and Natural Sciences

Files in This Item:
File Description SizeFormat 
Novian Nur Fatihah 151820101008_.pdf566.55 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Admin Tools