pewarnaan total pada graf outerplanar - total coloring of...

Pewarnaan Total Pada Graf OuterplanarTotal Coloring of Outerplanar Graph

Bima Prihasto (1209100053)

Dosen Pembimbing : Drs. Sumarno, DEA

Jurusan MatematikaFakultas Matematika dan Ilmu Pengetahuan Alam

Institut Teknologi Sepuluh NopemberSurabaya

August 4, 2013

Pendahuluan

Tinjauan PustakaPengertian Graf

Planarity

Pewarnaan

Metodologi

Analisis danPembahasanGraf Outerplanar ∆ = 1

Lemma 4.1.1

Graf Outerplanar ∆ = 2

Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3


Kondisi awal pada Cn

Kondisi pada m − chord

Contoh dan Kesimpulan

Block saling terhubung

Pola yang terbentuk


Simpulan

Abstrak

Pada tugas akhir ini dilakukan konstruksi teorema padapewarnaan total graf outerplanar, yang sebelumnya ide di-dapat dari teorema yang telah dikemukakan oleh Zhang Z,Zhang J, dan Wang J dengan membuktikan untuk semua grafouterplanar, pada ∆(G) ≥ 4 maka χT (G) = ∆(G) + 1 [5],Dengan mencoba derajat maksimum ∆(G) = 3, Maka den-gan pendekatan induksi, akan dibentuk potongan lemma gunamendukung teorema yang dikonstruksi, Dari konstruksi teo-rema didapatkan beberapa hasil lemma dan teorema sehinggamembuktikan bahwa berlaku untuk semua graf outerplanar,pada ∆(G) ≥ 3 maka χT (G) = ∆(G) + 1.Kata-kunci: Pewarnaan Total, Graf Planar, Graf Outerpla-nar, Derajat Maksimum.

Bima Prihasto (1209100053) Pewarnaan Total Pada Graf Outerplanar August 4, 2013 2/55

Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Pendahuluan

1852Francis Guthrie memperkenalkan pewarnaan graf pertama kali denganmencoba mewarnai sebuah peta Inggris

1941Brooks pertama kali mempublikasikan tentang pewarnaan simpul

1964Vizing pertama kali mempublikasikan tentang pewarnaan sisi

1965Behzad pertama kali mempublikasikan pewarnaan total

1988Zhang Z, Zhang J, dan Wang J telah membuktikan bahwa untuk semuagraf outerplanar dengan ∆(G) = 4 maka χT (G) = ∆(G) + 1


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Pendahuluan

Rumusan MasalahBagaimana membuktikan bahwa untuk semua graf outerplanar, dengan∆(G) = 3 sehingga didapat χT (G) = 4

Batasan MasalahPada penulisan Tugas Akhir ini, jenis graf yang akan diteliti adalah grafouterplanar dengan memiliki ∆ = 3

TujuanMembuktikan bahwa untuk semua graf outerplanar, dengan ∆(G) = 3sehingga didapatkan χT (G) = 4

ManfaatDapat memberikan kontribusi penelitian dalam bidang teori graf,khususnya pada pewarnaan total pada graf outerplanar


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan


Figure : Sebuah Graf

Bertetangga (Adjacent)

Melekat (Incident)

Derajat (Degree)

Derajat Maksimum ∆ (Maximum degree)


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan


Figure : Sebuah Graf dibagi menjadi beberapa block

Jalan (Walk )Lintasan (Path)Siklus (Cycle)Ekor (Chord)Cut-PointBlock


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan



Jalan (Walk )

Lintasan (Path)Siklus (Cycle)Ekor (Chord)Cut-PointBlock


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan



Jalan (Walk )Lintasan (Path)

Siklus (Cycle)Ekor (Chord)Cut-PointBlock


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan



Jalan (Walk )Lintasan (Path)Siklus (Cycle)

Ekor (Chord)Cut-PointBlock


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan



Jalan (Walk )Lintasan (Path)Siklus (Cycle)Ekor (Chord)

Cut-PointBlock


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan



Jalan (Walk )Lintasan (Path)Siklus (Cycle)Ekor (Chord)Cut-Point

Block


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan



Jalan (Walk )Lintasan (Path)Siklus (Cycle)Ekor (Chord)Cut-PointBlock


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan


Figure : Subgraf dan Isomorfik

Subgraf (Subgraph)

Isomorfik (Isomorphic)


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Tinjauan PustakaPlanarity

Figure : Graf Planar dan Graf Bidang

Graf Planar (Planar Graph)

Graf Bidang (Plane Graph)


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan


Figure : Contoh graf planar dan bukan graf planar


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan


Figure : Graf Outerplanar

Graf Outerplanar (Outerplanar Graph)


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan


Figure : Contoh graf outerplanar dan bukan graf outerplanar


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Tinjauan PustakaPewarnaan

Figure : Pewarnaan Simpul, Pewarnaan Sisi, dan Pewarnaan Total

Pewarnaan Simpul (Vertex Coloring)Bilangan Kromatik (Chromatic Number ) χ = 2

Pewarnaan Sisi (Edge Coloring)Indeks Kromatik (Chromatic Index) χ′ = 2

Pewarnaan Total (Total Coloring)Bilangan Kromatik Total (Total Chromatic Number ) χT = 4


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan


Figure : Permasalahan Pewarnaan Total


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Metodologi

Observasi

Dugaan Awal

Konstruksi

Evaluasi


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Analisis dan PembahasanLemma 4.1.1

Lemma 4.1.1Untuk setiap graf Outerplanar pada ∆ = 1, maka χT = 3


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan


Figure : Graf Outerplanar ∆ = 1


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan


Lemma 4.2.1Untuk semua graf Outerplanar berbentuk C3n dengan ∆ = 2, makaχT = 3


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan


Figure : Graf Outerplanar berbentuk C3n dengan ∆ = 2


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan


Lemma 4.2.2Untuk semua graf Outerplanar berbentuk C3n+1 dengan ∆ = 2, makaχT = 4


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan


Figure : Graf Outerplanar berbentuk C3n+1 dengan ∆ = 2 untuk nganjil


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan


Figure : Graf Outerplanar berbentuk C3n+1 dengan ∆ = 2 untuk ngenap


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan


Lemma 4.2.3Untuk setiap graf Outerplanar berbentuk C3n+2 dengan ∆ = 2, makaχT = 4


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan


Figure : Graf Outerplanar berbentuk C3n+2 dengan ∆ = 2


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Analisis dan PembahasanKondisi awal Cn

Figure : Kondisi awal pada Cn


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Analisis dan PembahasanIlustrasi algoritma pembentukan Cn untuk m − chord

Figure : Ilustrasi algoritma pembentukan Cn untuk m − chord


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Analisis dan PembahasanContoh Graf C4 dan C6

Figure : Contoh Graf C4 dan C6 masing - masing untuk m − chord


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Analisis dan PembahasanContoh Graf C8

Figure : Contoh Graf C8 untuk m − chord


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Analisis dan PembahasanPola pewarnaan Cn

Figure : Pola pewarnaan Cn


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Analisis dan PembahasanKondisi pada m − chord

Untuk c(vi) 6= c(vl)

Kondisi (1). c(eh, vi , vj ) = c(ek , vl , em)Kondisi (2). c(eh, vi , vj ) 6= c(ek , vl , em) sehingga|c(eh, vi ) ∩ c(ek , el )|= 1Kondisi (3). c(eh, vi , vj ) 6= c(ek , vl , em) sehingga|c(eh, vi ) ∩ c(ek , el )|= 0

Untuk c(vi) = c(vl)

Kondisi (4). c(vh) 6= c(vk )Kondisi (5). c(vh) = c(vk )


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Analisis dan PembahasanKondisi 1

Figure : Kondisi (1): c(eh, vi , vj ) = c(ek , vl , em)


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan


Figure : Kondisi (2): c(eh, vi , vj ) 6= c(ek , vl , em) sehingga|c(eh, vi ) ∩ c(ek , el )|= 1


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan


Figure : Kondisi (3): c(eh, vi , vj ) 6= c(ek , vl , em) sehingga|c(eh, vi ) ∩ c(ek , el )|= 0


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan


Figure : Kondisi (4): c(vh) 6= c(vk )


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan


Figure : Kondisi (5): c(vh) = c(vk )


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Analisis dan Pembahasan1 − chord

Figure : C4 dengan 1− chord


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan




Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Analisis dan PembahasanCorrolary

Corollary 4.3.1Untuk setiap graf outerplanar berbentuk Cn dengan ∆ = 3 mempunyain − chord, maka χT = 4


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Analisis dan Pembahasan∆ = 1 dengan ∆ = 1

Figure : Dua block ∆ = 1 dan ∆ = 1, tanpa n - siklus


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Analisis dan Pembahasan∆ = 1 dan ∆ = 2 berbentuk C3n

Figure : Dua block ∆ = 1 dan ∆ = 2 berbentuk C3n


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Analisis dan Pembahasan∆ = 1 dan ∆ = 2 berbentuk C3n+1

Figure : Dua block ∆ = 1 dan ∆ = 2 berbentuk C3n+1


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Analisis dan Pembahasan∆ = 1 dan ∆ = 2 berbentuk C3n+2

Figure : Dua block ∆ = 1 dan ∆ = 2 berbentuk C3n+2


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Analisis dan Pembahasan∆ = 1 dan ∆ = 3 berbentuk Cn memiliki n - chord

Figure : Dua block ∆ = 1 dan ∆ = 3 berbentuk Cn memiliki n -chord


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Analisis dan PembahasanAplikasi pewarnaan total dari tiga block saling berhubungan

Figure : Contoh aplikasi pewarnaan total dari tiga block salingberhubungan


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Analisis dan PembahasanCorrolary

Corollary 4.4.1Jika B merupakan block dari graf outerplanar G, Maka χT (B) ⊆ χT (G)


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Analisis dan PembahasanSembarang graf outerplanar ∆ = 3

Figure : Contoh sembarang graf outerplanar ∆ = 3


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Analisis dan PembahasanContoh sembarang graf outerplanar ∆ = 3

Figure : Contoh sembarang graf outerplanar ∆ = 3


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Analisis dan PembahasanAplikasi

Figure : Graf Planar ∆ = 3 yang tidak berlaku untuk χT = 4


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Simpulan

a. Untuk setiap Graf Outerplanar G dengan ∆ = 1, makaχT (G) = 3.

b. Untuk setiap Graf Outerplanar G berbentuk C3n dengan∆ = 2, maka χT (G) = 3.

c. Untuk setiap Graf Outerplanar G berbentuk C3n+1 dengan∆ = 2, maka χT (G) = 4.

d. Untuk setiap Graf Outerplanar G berbentuk C3n+2 dengan∆ = 2, maka χT (G) = 4.

e. Untuk setiap Graf Outerplanar G berbentuk Cn dengan∆ = 3 memiliki n - chord, maka didapat χT (G) = 4.

f. Untuk setiap block B yang saling terhubung dari sebuahGraf Outerplanar G dengan ∆ = 3, maka didapat χT (G) =4.


Pendahuluan


Planarity

Pewarnaan

Metodologi


Lemma 4.1.1


Lemma 4.2.1

Lemma 4.2.2

Lemma 4.2.3






Pola yang terbentuk


Simpulan

Daftar Pustaka

G Chartrand, L. L. 1996.Graph And Diagraph Third Edition.Chapman And Hull UK.

G Chartrand, P. Z. 2009.Chromatic Graph Theory, Discrete Mathematics And Its Applications.CRC Press USA

Harary, F. 1969.Graph Theory.Wesley Publishing Company, Inc

Diestel, R. 2005.Graduate Texts in Mathematics Graph Theory.Springer - Verlag Heidelberg New York.

Yap, H, P. 1996.Total Colouring of Graph.Springer - Verlag Heidelberg Germany.


pewarnaan total pada graf outerplanar - total coloring of...

Documents