TUGAS AKHIR: STUDI TENTANG BILANGAN KROMATIK PADA GRAPH


Oleh: Didi Febrian

Abstract: Graph G adalah suatu himpunan berhingga tak kosong dari objek-objek yang disebut verteks (minimal tunggal) bersama-sama dengan suatu himpunan yang anggotanya adalah pasangan yang tak berurut dari verteks yang berbeda pada G yang disebut edge (mungkin kosong), dan dinotasikan dengan G \lbrace V (G),E(G) \rbrace . Himpunan verteks dari G dinotasikan dengan V(G) dan himpunan edge dinotasikan dengan E(G). pewarnaan dari graph G adalah suatu pemetaan warnawarna ke verteks-verteks dari G sedemikian hingga dua verteks yang berbeda dan adjacent mempunyai warna-warna yang berbeda. Bilangan kromatik dari G adalah banyaknya warna minimum yang diperlukan untuk mewarnai G, dan dinotasikan dengan (G). Algoritma Welch-Powell dapat digunakan untuk melakukan pewarnaan pada graph yang sederhana, artinya graph yang memiliki jumlah verteks dan edge yang kecil. Bilangan kromatik dari null graph adalah 1. Bilangan kromatik graph komplit K_n adalah n. Bilangan kromatik cycle, C_n adalah 2 jika n genap dan 3 jika n ganjil dan bilangan kromatik dari pohon adalah 2. Bilangan kromatik dari suatu graph sembarang dapat ditentukan dengan melihat beberapa kasus.

(TUGAS AKHIR INI TELAH DIUJIKAN DAN DINYATAKAN LULUS PADA DEPARTEMEN MATEMATIKA. FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM, UNIVERSITAS SUMATERA UTARA, MEDAN, 2006)

TUGAS AKHIR: STUDI TENTANG BILANGAN KROMATIK PADA GRAPH

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s