Skripsi

Indeks kromatik star pada graph dengan derajat maksimum empat / Usni Putri Rahayu

Abstrak
RINGKASAN Rahayu U. P. 2019. Indeks Kromatik Star pada Graph dengan Derajat Maksimum Empat. Skripsi Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam. Universitas Negeri Malang. Pembimbing Dra. Sapti Wahyuningsih M.Si. Kata kunci pewarnaan sisi strong pewarnaan sisi star derajat maksimum empat indeks kromatik. Pewarnaan merupakan suatu hal yang sangat penting di dalam teori graph. Pewarnaan dapat berupa pewarnaan titik dan pewarnaan sisi. Pewarnaan sisi merupakan pemberian warna pada setiap sisi dari suatu graph sedemikian sehingga tidak ada sisi adjacent yang mendapat warna yang sama. Warna minimum yang digunakan untuk mewarnai sisi disebut indeks kromatik atau sering dinotasikan 120594 8242 ( 119866 ). Di dalam pewarnaan sisi terdapat pewarnaan sisi strong dan pewarnaan sisi star. Pewarnaan sisi graph 119866 dikatakan pewarnaan sisi strong jika sembarang dua sisi yang berjarak dua mendapat warna yang berbeda. Warna minimum yang digunakan untuk mewarnai sisi strong disebut indeks kromatik strong atau 120594 119904 8242 ( 119866 ). Pewarnaan sisi graph 119866 dikatakan pewarnaan sisi star jika tidak ada lintasan bikromatik atau sikel dengan panjang empat. Dengan kata lain paling sedikit tiga warna yang digunakan untuk mewarnai sisi setiap lintasan dan sikel dengan panjang empat. Banyak minimum warna yang digunakan untuk mewarnai sisi star disebut indeks kromatik star atau dinotasikan 120594 119904 119905 8242 ( 119866 ). Pewarnaan sisi pada graph dengan derajat maksimum empat pernah diwarnai dengan pewarnaan sisi strong dan memiliki indeks kromatik strong besar sehingga pada skripsi ini akan dibahas mengenai pewarnaan sisi star pada graph dengan derajat maksimum empat untuk mencari indeks kromatik star pada pewarnaan sisi star. Langkah pembuktian yang pertama yaitu mengidentifikasi graph dengan derajat maksimum empat. Graph 119866 dipartisi menjadi dua subgraph 119866 1 dan 119866 2 dengan memenuhi syarat indeks kromatik star dan indeks kromatik strong. Setelah syarat dipenuhi mewarnai graph yang telah dipartisi tersebut. Graph 119866 berderajat maksimum empat dapat diwarnai dengan menggunakan pewarnaan sisi star. Menghasilkan indeks kromatik star yang lebih minimum dibandingkan pada pewarnaan sisi strong. Sehingga graph dengan derajat maksimum empat memiliki indeks kromatik star minimum.

Informasi Detail

DDC

Rs 511.5 RAH i

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2019.

Deskripsi Fisik

v, 29 lembar : il., tab. ; 30 cm

Bahasa

Indonesia

No Reg

03049/KI/19

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang. 2019

Subjek

1. GRAFIK
2. GRAPH

Pembimbing

1. Sapti Wahyuningsih

Lampiran Berkas