JURNAL TEKNIK POMITS Vol. 1, No. 1, (2013) 1-6
1
Pewarnaan Total Pada Graf Outerplanar Prihasto.B dan Sumarno Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Teknologi Sepuluh Nopember (ITS) Jl. Arief Rahman Hakim, Surabaya 60111 E-mail:
[email protected] Abstrak—Pada paper ini dilakukan konstruksi teorema pada pewarnaan total graf outerplanar, yang sebelumnya ide didapat dari teorema yang telah dikemukakan oleh Zhang Z, Zhang J, dan Wang J dengan membuktikan untuk semua graf ( ) outerplanar, pada ( ) maka ( ) [5], Dengan ( ) mencoba derajat maksimum , Maka dengan pendekatan induksi, akan dibentuk beberapa proporsisi guna mendukung teorema yang dikonstruksi, Dari konstruksi teorema didapatkan beberapa hasil lemma dan teorema sehingga membuktikan bahwa berlaku untuk semua graf outerplanar, pada ( ) maka ( ) Kata Kunci—Pewarnaan Total, Graf Outerplanar, Derajat Maksimum
I. PENDAHULUAN Pewarnaan graf pertama kali diterapkan pada sebuah peta Inggris. Pada saat itu Francis Guthrine mencoba untuk mewarnai peta Inggris dengan hanya menggukan empat warna untuk tiap daerah bagian di Inggris sehingga antar daerah yang berdekatan mempunyai warna yang berbeda[2]. Pada 1996, H. P. Yap pada bukunya dengan judul ”Total colorings of graphs”. yang telah membahas beberapa kondisi tertentu mengenai pewarnaan total pada graf planar. Salah satunya berisi teorema yang telah dikemukakan oleh Zhang Z, Zhang J, dan Wang J dengan membuktikan untuk semua graf outerplanar, pada ( ) maka ( ) ( ) . [5]. Pada tugas akhir ini dilakukan perubahan batas atas dan batas bawah, Dengan mencoba membuktikan bahwa untuk semua graf outerplanar, pada ( ) sedemikian hingga tetap berlaku untuk ( ) . Permasalahan yang akan dibahas dibatasi ruang lingkup pembahasannya yakni Graf Outerplanar dengan ( ) . II. TINJAUAN PUSTAKA A. Pengertian Graf Sebuah graf didefinisikan sebagai pasangan dari himpunan ( ( ) ( )) dimana tidak boleh kosong, dan pasangan himpunan tak terurut dari anggota . Anggota dari adalah simpul dari dan anggota dari adalah sisi dari , Sehingga dapat ditulis ( ) untuk simpul dari dan ( ) untuk sisi dari . Untuk menunjukkan jumlah banyaknya simpul dan sisi dari pada ( ) dan ( ), maka secara berturut-turut dapat dikatakan order (order p) dan ukuran (size q) dari . [2].
Gambar 1 : Sebuah Graf Jika adalah sisi dari , maka dan adalah simpul yang bertetangga (adjacent), Dua simpul yang bertetangga disebut sebagai tetangga satu sama lain. Himpunan dari tetangga dari simpul adalah disebut persekitaran (neighborhood) pada . Jika dan adalah sisi yang berdekatan di , maka dan adalah sisi yang bertetangga. Pada simpul dan sisi dikatakan melekat (incident) satu sama lain. Demikian pula, dan adalah bersisian. Derajat simpul v pada graf adalah banyaknya simpul di yang berdekatan dengan , dengan kata lain banyaknya sisi di yang bersisian dengan . Banyaknnya sisi yang melekat dengan simpul disebut derajat, dan dinotasikan dengan atau lebih sederhana dengan . Derajat tertinggi dari simpul pada disebut derajat maksimum (maximum degree) pada yang dinotasikan dengan ( ). Sebuah graf H dikatakan subgraf pada graf G jika ( ) ( ) dan ( ) ( ) Beberapa sisi yang terhubung membentuk suatu barisan yang tidak putus pada disebut jalan (walk). Lintasan (path) adalah jalan pada graf dimana tidak ada simpul yang berulang. Panjang (length) adalah banyaknya n-sisi yang dilalui pada jalan di . Siklus (cycle) adalah jalan (walk) dengan , dan simpul saling berbeda. Sebuah siklus (cycle) dengan panjang n dapat dikatakan n-cycle. Pada sebuah siklus (cycle) dapat dikatakan jika memiliki order sejumlah n. Dengan n adalah banyaknya simpul. Chord pada sebuah siklus di adalah sisi yang menghubungkan simpul yang ada pada . Cut-point adalah simpul pada graf yang terhubung bila dihilangkan maka graf menjadi tak terhubung Graf yang tidak mempunyai cut-point disebut block.[2] Dua graf dan adalah isomorfik (memiliki struktur yang ( ) sama) jika terdapat fungsi bijektif ( ). sedemikian hingga dua simpul dan adalah bertetangga di
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2013) 1-6 jika dan hanya jika ( ) dan ( ) adalah bertetangga di Jika dan adalah isomorfik, maka dapat ditulis .
2 .
B. Graf Planar Graf disebut graf planar (planar graph) jika dapat digambarkan pada sebuah bidang tanpa adanya dua sisi yang saling berpotongan, demikian gambar tersebut dikatakan tertanam (embedding) pada bidang. Graf yang telah digambar pada sebuah bidang yang tertanam maka disebut graf bidang (plane graph). Jelas bahwa setiap graf bidang adalah planar dan setiap graf planar dapat digambarkan sebagai graf bidang.[2] Sebuah graf outerplanar adalah jika graf planar saat tertanam pada bidang (graf bidang) maka semua simpul terletak pada wilayah/muka yang sama. Graf outerplanar dan Outerplane Tertanam (outerplane embedding) ditunjukkan pada Gambar 2.
Gambar 2 : Graf Outerplanar dan Outerplane embedding C. Pewarnaan Total Pewarnaan total (total coloring) pada graf adalah penentuan warna simpul dan sisi pada dimana perbedaan warna ditentukan oleh: (1). Setiap dua simpul saling bertetangga, (2). Setiap dua sisi yang saling bertetangga, (3). Setiap simpul dan sisi yang saling melekat. -warna total (ktotal coloring) pada graf adalah pewarnaan total pada dari himpunan warna. Bilangan kromatik total (total chromatic number) ( ) pada adalah jumlah warna minimum yang dibutuhkan untuk pewarnaan total pada . Jika adalah pewarnaan total pada graf dan adalah simpul dari dengan ( ), maka ditentukan dari yang melekat terhadap sisi, sehingga saling berbeda warna termasuk ( ) terhadap itu sendiri. Berakibat bahwa ( ) untuk semua graf .[2].
III. ANALISIS DAN PEMBAHASAN A. Graf Outerplanar dengan Preporsisi 4.1 Untuk setiap graf Outerplanar pada , maka Bukti: Misalkan sembarang Graf Outerplanar dengan ( ) , maka untuk setiap himpunan pada dan untuk [ ] . setiap himpunan pada sedemikian hingga Dengan kata lain bahwa untuk setiap lintasan (path) ( ) maka . Sehingga jelas memenuhi untuk ( )
Gambar 4 : Graf Outerplanar B. Graf Outerplanar dengan Preporsisi 4.2 Untuk setiap graf Outerplanar berbentuk dengan , maka dengan Bukti: Misalkan sembarang Graf Outerplanar ( ) ( ) ( ) , Asumsikan ambil dan , Dengan melalui induksi didapatkan graf , dengan terdiri dari ( ) dan ( ) Sehingga melalui ( ) didapat pewarnaan total dengan masing-masing ( ) dan . sehingga lintasan (path) Untuk membuat siklus maka didapat . kemudian setelah dilalakukan observasi didapat bahwa barisan dipetakan pada pewarnaan total ( ) sehingga . dapat diilustrasikan pada Gambar 6. Maka jelas untuk semua graf Outerplanar dengan , , maka memiliki ( )
Gambar 5 : Graf Outerplanar
Gambar 3 : Pewarnaan Total pada Graf H
, dengan
Preporsisi 4.3 Untuk setiap graf Outerplanar berbentuk , dengan , maka Bukti; Misalkan sembarang Graf Out er planar dengan ( ) , Asumsikan ( ) ( ) ambil dan , Dengan melalui induksi didapatkan graf , dengan terdiri dari ( ) dan ( ). Sehingga melalui didapat pewarnaan total dengan masing-masing ( ) dan ( ) . sehingga lintasan (path) . Untuk membuat siklus maka didapat . Pada kasus ini, setelah dilalakukan observasi didapat bahwa untuk ganjil maka barisan dipetakan terhadap pewarnaan total sehingga ( ) . dan untuk genap maka barisan dipetakan terhadap pewarnaan total sehingga
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2013) 1-6 ( ) . Sehingga dapat diilustrasikan pada G a m b a r 6. Maka jelas untuk semua graf Outerplanar berbentuk dengan , memiliki ( )
Gambar 6 : Graf Outerplanar
dengan
Preporsisi 4.4 Untuk setiap graf Outerplanar berbentuk dengan , maka Bukti: Misalkan sembarang Graf Outerplanar dengan ( ) , Asumsikan ( ) ( ) ambil dan , Dengan melalui induksi didapatkan graf , dengan terdiri dari ( ) dan ( ) Sehingga melalui didapat pewarnaan total dengan masing-masing ( ) ( ) . sehingga lintasan dan (path) . Untuk membuat siklus maka didapat . kemudian setelah dilalakukan observasi didapat bahwa barisan dipetakan pada pewarnaan ( ) Dapat total sehingga diilustrasikan pada Gambar 7. Maka jelas untuk semua graf Outerplanar berbentuk dengan , memiliki ( ) ,
Gambar 8 : Graf Outerplanar
dengan
C. Graf Outerplanar dengan Pada Graf Outerplanar penentuan bilangan kromatik total diawali dengan pembentukan siklus. Pada setiap siklus pada graf outerplanar setidaknya terdapat dua simpul yang tidak melekat pada chord, Sehingga dapat diambil salah satu dari dua simpul tersebut menjadi simpul awal untuk melakukan pewarnaan, pada pembahasan ini diambil sebagai simpul awal. Dari hasil observasi didapat Algoritma untuj pewarnaan yang mempunyai m-chord sebagai berikut: 1. Misalkan n adalah banyaknya order pada dan asumsikan 2. Ambil sebagai simpul awal sehingga diwarnai 1 3. Ambil dan sebagai sisi yang melekat pada sehingga diwarnai masing-masing 4 dan 2 4. Ambil dan sebagai simpul yang bertetangga pada sehingga diwarnai masing-masing 2 dan 3
3 5.
Ambil himpunan akar kanan dari dan akar kiri dari
sehingga didapat sehingga didapat
6.
Ambil himpunan akar kanan dari sehingga didapat dan akar kiri dari sehingga didapat { } 7. Tentukan ( ) dan ( ) masing-masing didapat ( ) diperoleh dari pewarnaan total pada sisi yang melekat pada dan simpul yang bertetangga pada , dan ( ) diperoleh dari pewarnaan total pada sisi yang melekat pada dan simpul yang bertetangga pada . ( ) Sehingga ambil ( ) 8. Tentukan ( ) dan ( ) masing-masing didapat ( ) diperoleh dari pewarnaan total pada sisi yang melekat pada dan simpul yang bertetangga pada , dan ( ) diperoleh dari pewarnaan total pada sisi yang melekat pada dan simpul yang bertetangga ) pada . Sehingga ambil ( ( ) 9. Ulangi langkah 7 dan 8, sehingga didapat: jika n=genap ) maka ( dan jika n=ganjil maka ( ) Ilustrasi algoritma ditampilkan pada gambar 9
Gambar 9 : Ilustrasi algoritma pembentukan untuk mchord Dari pengerjaan observasi didapat beberapa kondisi untuk masing-masing penentuan warna di persekitaran simpul pada chord. 1. Pada saat ( ) ( ) ) ( ) Kondisi (1). (
Gambar 10: Ilustrasi pewarnaan chord pada kondisi 1
Kondisi (2). | ( ) (
(
) )|
(
)
sehingga
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2013) 1-6
4 kemudian dipetakan pada ( ) pewarnaan total sehingga dapat diilustrasikan pada Gambar 5. Maka jelas memenuhi untuk ( )
Gambar 11: Ilustrasi pewarnaan chord pada kondisi 2 Kondisi (3). | ( ) (
(
)
(
)
Gambar 5 : Graf Outerplanar
)|
Gambar 12: Ilustrasi pewarnaan chord pada kondisi 3 2.
Pada saat ( ) ( ) Kondisi (4). ( ) ( )
Gambar 13: Ilustrasi pewarnaan chord pada kondisi 4 Kondisi (5). (
tanpa
sehingga
)
(
)
2. yang terhubung pada berbentuk Diberikan adalah s e m b a r a n g graf outerplanar dan adalah s e m b a r a n g graf dengan outerplanar dengan berbentuk dengan , Dengan demikian didapatkan path, sehingga dipetakan terhadap pewarnaan total menjadi dan didapatkan cycle dengan syarat ( ) dengan kata lain bahwa ) dan bahwa ( adalah cut-point. Ambil Karena merupakan sisi yang melekat pada cut-point di dengan pewarnaan , Dengan demikian pastilah untuk sisi yang melekat pada cut-point di adalah . dan karena merupakan simpul yang bertetangga pada cut-point di dengan pewarnaan , Maka kemungkinan untuk simpul yang bertetangga pada cut-point di adalah . Sehingga untuk memperoleh hasil yang minimal ambil . Berdasarkan proporsisi 4.1 didapat yang dipetakan menjadi dan preporsisi 4.2 didapat yang dipetakan menjadi . Sehingga graf outerplanar yang terdiri dari dan memenuhi untuk
Gambar 14 : Ilustrasi pewarnaan chord pada kondisi 5 Corolarry 4.5 Untuk semua graf Outerplanar dengan , , -chord, maka D. Block pada Graf Outerplanar saling terhubung 1. yang terhubung pada Misalkan sembarang Graf Outerplanar dengan ( ) , ( ) ( ) Asumsikan ambil dan , Dengan melalui induksi didapatkan graf , dengan terdiri dari ( ) dan ( ) Sehingga melalui ( ) didapat pewarnaan total dengan masing masing ( ) dan . sehingga lintasan (path)
Gambar 15 : Pewarnaan total dua block terhubung dengan dan 3. terhubung pada berbentuk Diberikan adalah s e m b a r a n g graf outerplanar dengan dan adalah s e m b a r a n g graf outerplanar dengan berbentuk . Dengan dengan demikian didapatkan path, sehingga dipetakan terhadap pewarnaan total menjadi dan didapatkan cycle dengan syarat
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2013) 1-6 bahwa ( ) ( ) dengan kata lain bahwa dan adalah cut-point. Ambil Karena merupakan sisi yang melekat pada cut-point di , Dengan demikian dengan pewarnaan pastilah untuk sisi yang melekat pada cut-point di adalah . dan karena merupakan simpul yang bertetangga pada cut-point di dengan pewarnaan , Dengan demikian kemungkinan untuk simpul yang bertetangga pada cut-point di adalah . Sehingga untuk memperoleh hasil yang minimal ambil . Berdasarkan preporsisi 4.1 didapat yang dipetakan menjadi dan preporsisi 4.3 jika ganjil didapat yang dipetakan menjadi dan jika genap didapat yang dipetakan menjadi Sehingga graf yang terdiri dari dan memenuhi untuk
Gambar 16 : Pewarnaan total dua block terhubung dengan dan 4. terhubung pada berbentuk Diberikan adalah s e m b a r a n g graf outerplanar dan adalah sembarang graf outerplanar dengan dengan berbentuk dan Maka dengan didapatkan path, sehingga dipetakan terhadap pewarnaan total menjadi dan didapatkan cycle, dengan syarat bahwa ( ) ( ) dengan kata lain bahwa dan adalah cut-point. Karena merupakan sisi yang melekat pada cut-point di dengan pewarnaan , Maka pastilah untuk sisi yang melekat pada cut-point di v2b2 adalah c :=e1b2 e2b2 →{1, 4}. dan karena v1b1 merupakan simpul yang bertetangga pada cut-point di dengan pewarnaan Dengan demikian kemungkinan untuk simpul yang bertetangga pada cut-point di adalah . Sehingga untuk memperoleh hasil yang minimal ambil . Berdasarkan preporsisi 4.1 didapat yang dipetakan menjadi dan preporsisi 4.4 didapat yang dipetakan menjadi . Sehingga graf yang terdiri dari dan memenuhi untuk
5
Gambar 17 : Pewarnaan total dua block terhubung dengan dan 5. ∆ = 1 yang terhubung pada ∆ = 3, berbentuk , m e m i l i k i m-chord Diberikan adalah s e m b a r a n g graf outerplanar dan adalah s e m b a r a n g graf dengan outerplanar dengan , -siklus dan - chord. Dengan demikian didapatkan path sehingga dipetakan terhadap pewarnaan total menjadi dan didapatkan cycle dengan syarat ( ) bahwa ( ) ( ) dan dengan kata lain bahwa dan adalah cut-point. Ambil , Karena merupakan sisi yang melekat pada cut-point di dengan pewarnaan , Maka pastilah untuk sisi yang melekat pada cut-point di v2b2 adalah c :=e1b2 e2b2 →{2, 4}. dan karena v1b1 merupakan simpul yang bertetangga pada cut-point di dengan pewarnaan Dengan demikian pastilah untuk simpul yang bertetangga pada cut-point di adalah . Sehingga memperoleh hasil minimal ambil Berdasarkan preoporsisi 4.1 dan corollary 4.5 d i d a p a t . Yang dipetakan menjadi . Sehingga graf yang terdiri dari dan memenuhi untuk
Gambar 18 : Pewarnaan total dua block terhubung dengan dan 6. , Diberikan sebelumnya
, dapat
yang sa ling te rhubung Maka menurut kondisi dikatakan bahwa ( ) ( )
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2013) 1-6 ) , dan didapat . Misalkan adalah , maka ambil path dari sembarang graf outerplanar sehingga didapat , Asumsikan adalah . Untuk persekitaran sisi cut-point, sehingga yang melekat pada dan maka didapatkan dua kondisi: kondisi apabila terdapat dua sisi dari yang melekat dan satu sisi dari yang melekat pada cut-point dan kondisi apabila terdapat satu sisi dari yang melekat dan dua sisi dari yang melekat pada cut-point. Pada kondisi , ambil , maka didapat dan . Sedangkan pada kondisi 2, ambil , maka didapat dan . Sehingga graf yang terdiri dari memenuhi untuk sehingga dapat dikatakan
(
IV. SIMPULAN Pada pembahasan bab sebelumnya telah dilakukan konstruksi beberapa preporsisi guna membuktikan bahwa ( ) maka untuk semua graf outerplanar, pada ( ) . Sehingga diperoleh beberapa kesimpulan dari hasil kontruksi sebagai berikut: , maka 1) Untuk setiap Graf Outerplanar dengan didapat ( ) , dan 2) Untuk setiap Graf Outerplanar dengan ( ) maka didapat . dan 3) Untuk setiap Graf Outerplanar dengan ( ) , maka didapat . 4) Untuk setiap Graf Outerplanar dengan dan ( ) , maka didapat . 5) Untuk setiap Graf Outerplanar dengan , , dan - chord, maka didapat ( ) . 6) Untuk setiap block yang saling terhubung dari sebuah Graf Outerplanar dengan , maka didapat ( ) DAFTAR PUSTAKA [1] [2]
[3] [4] [5]
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. in Springer - Verlag Heidelberg New York Yap, H, P. 1996. Total Colouring of Graph Springer Verlag Heidelberg Germany
6
