• Login
    View Item 
    •   Home
    • UNDERGRADUATE THESES (Koleksi Skripsi Sarjana)
    • UT-Faculty of Mathematics and Natural Sciences
    • View Item
    •   Home
    • UNDERGRADUATE THESES (Koleksi Skripsi Sarjana)
    • UT-Faculty of Mathematics and Natural Sciences
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    ANALISA NILAI KROMATIK PEWARNAAN TOTAL r−DINAMIS PADA OPERASI COMB PRODUCT DARI GRAF-GRAF KHUSUS

    Thumbnail
    View/Open
    Mira Septiana Dewi - 131810101034_1.pdf (1.011Mb)
    Date
    2017-03-21
    Author
    Dewi, Mira Septiana
    Metadata
    Show full item record
    Abstract
    Teori graf pertama kali diperkenalkan oleh seorang matematikawan berkebangsaan Swiss bernama Leonhard Euler pada tahun 1736. Salah satu teori yang dikembangkan dalam teori graf adalah pewarnaan graf (coloring). Terdapat tiga macam pewarnaan dalam teori graf, yaitu pewarnaan titik (vertex coloring), pewarnaan sisi (edge coloring), dan pewarnaan wilayah (region coloring). Selanjutnya, H. Lai dan B. Montgomery memperkenalkan konsep pewarnaan dinamis danmenuangkannyadalamsebuahartikelyangberjudulDynamicColoringofGraphs. Dari penelitian diatas mulai dikembangkan lagi tentang pewarnaan dinamis pada graf. Terdapat tiga macam pewarnaan r−dinamis dalam teori graf yaitu pewarnaan titik r−dinamis, pewarnaan sisi r−dinamis, dan pewarnaan total r−dinamis. Pewarnaan total r-dinamis pada graf G adalah pemetaan c : V (G)∪E(G) ke himpunan warna sedemikian hingga memenuhi kondisi∀v ∈ V (G),|c(N(u))|≥ min{r,d(u) + N(u)} dan ∀e = uv ∈ E(G),|c(N(e))| ≥ min{r,d(u)+ d(v)}. Bilangan kromatik dari pewarnaan total r-dinamis adalah banyaknya nilai k minimum yang dibutuhkan untuk mewarnai graf G, dan dinotasikan dengan χ”r(G). Pewarnaan total r-dinamis dapat diterapkan pada graf khusus maupun graf operasi. Operasi yang digunakan pada penelitian ini yaitu operasi Comb Product. Operasi comb product dari graf L dan H dinotasikan L ◃ H adalah operasi graf yang diperoleh dengan mengambil salinan dari graf L dan |L| salinan dari H dan merekatkan salinan ke-i dari graf H di titik cangkok o pada titik ke-i dari graf L. Adapun graf yang digunakan dalam penelitian ini yaitu graf Pn ◃ Wd3,3, Ln ◃ Pm, Pn ◃F1,3, Ln ◃S3, Pn ◃H2,2, TLn ◃C3 dan Sn ◃C3. Penelitian ini menggunakan metode deduktif dan pendeteksian pola. Tujuan penelitianiniadalahmenentukanhimpunantitikdansisipadagrafoperasidanbilangan kromatikpewarnaantotalr-dinamispadagrafPn◃Wd3,3,Ln◃Pm,Pn◃F1,3,Ln◃S3, Pn ◃ H2,2, TLn ◃ C3 dan Sn ◃ C3 sehingga dihasilkan 7 teorema baru, diantaranya adalah Penelitian ini dikategorikan sebagai penelitian eksploratif dan menggunakan metode pendeteksian pola. Tujuan penelitian ini adalah menentukan nilai kromatik total dari beberapa graf khusus dan dihasilkan 7 teorema baru, diantaranya adalah: 1. Teorema4.1Misalkan G adalah graf Pn ◃Wd3,3 dimana n ≥ 3 dan titik z sebagai titik cangkok pada graf Wd3,3. Bilangan kromatik pewarnaan total r-dinamis pada graf G adalah χ”r(G) =                            9,untuk 1 ≤ r ≤ 7 10,untuk r = 8 12,untuk 9 ≤ r ≤ 10 r + 2,untuk 11 ≤ r ≤ 13 16,untuk 14 ≤ r ≤ 15 17,untuk r ≥ 16 2. Teorema 4.2 Misalkan G adalah graf Ln ◃ Pm dimana n ≥ 2, m ≥ 3 dan titik y1 sebagai titik cangkok pada graf Pm. Bilangan kromatik pewarnaan total r-dinamis pada graf G adalah χ”r(G) = 5,untuk 1 ≤ r ≤ 3 8,untuk r = 4 10,untuk r = 5 13,untuk 6 ≤ r ≤ 7 15,untuk r ≥ 8 3. Teorema 4.3 Misalkan G adalah graf Pn ◃F1,3 dimana n ≥ 3 dan titik y3 sebagai titikcangkokpadagrafF1,3. Bilangankromatikpewarnaantotalr-dinamispadagraf G adalah χ”r(G) = 5,untuk 1 ≤ r ≤ 3 6,untuk r = 4 8,untuk r = 5 10,untuk 6 ≤ r ≤ 7 11,untuk r ≥ 8 4. Teorema 4.4 Misalkan G adalah graf Ln ◃ S3 dimana n ≥ 2 dan titik z3 sebagai titik cangkok pada graf S3. Bilangan kromatik pewarnaan total r-dinamis pada graf G adalah χ”r(G) = 5,untuk 1 ≤ r ≤ 3 6,untuk r = 4 8,untuk r = 5 10,untuk r = 6 12,untuk r = 7 dan r ≥ 8 5. Teorema 4.5 Misalkan G adalah graf TLn ◃C3 dimana n ≥ 3 dan titik y3 sebagai titik cangkok pada graf C3. Bilangan kromatik pewarnaan total r-dinamis pada graf G adalah χ”r(G) =                                  7,untuk 1 ≤ r ≤ 4 8,untuk 5 ≤ r ≤ 6 9,untuk r = 7 r + 3,untuk 8 ≤ r ≤ 9 15,untuk r = 10 18,untuk r = 11 20,untuk r ≥ 12 6. Teorema 4.6 Misalkan G adalah graf Pn ◃H2,2 dimana n ≥ 3 dan titik y4 sebagai ix titik cangkok pada graf H2,2. Bilangan kromatik pewarnaan total r-dinamis pada graf G adalah χ”r(G) = 5,untuk 1 ≤ r ≤ 3 8,untuk r = 4 9,untuk 5 ≤ r ≤ 7 10,untuk r ≥ 8 7. Teorema 4.7 Misalkan G adalah graf Sn ◃ C3 dimana n ≥ 4 dan titik z3 sebagai titik cangkok pada graf C3. Bilangan kromatik pewarnaan total r-dinamis pada graf G adalah χ”r(G) = n + 3,untuk 1 ≤ r ≤ n + 2 n + 4,untuk r = n + 3 n + 6,untuk n + 4 ≤ r ≤ n + 5 r + 1,untuk n + 6 ≤ r ≤ 2n + 3 2n + 5,untuk r ≥ 2n + 4
    URI
    http://repository.unej.ac.id/handle/123456789/79742
    Collections
    • UT-Faculty of Mathematics and Natural Sciences [3447]

    UPA-TIK Copyright © 2024  Library University of Jember
    Contact Us | Send Feedback

    Indonesia DSpace Group :

    University of Jember Repository
    IPB University Scientific Repository
    UIN Syarif Hidayatullah Institutional Repository
     

     

    Browse

    All of RepositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    Context

    Edit this item

    UPA-TIK Copyright © 2024  Library University of Jember
    Contact Us | Send Feedback

    Indonesia DSpace Group :

    University of Jember Repository
    IPB University Scientific Repository
    UIN Syarif Hidayatullah Institutional Repository