Teori Pewarnaan Graf dan Bilangan Kromatik

Peran Bagian: Mendukung bagian Teori Pewarnaan Graf dan Bilangan Kromatik saat dosen menjelaskan definisi formal, konsep bilangan kromatik, contoh-contoh graf standar, dan algoritma Welsh-Powell. Outline Slide: (1) Judul: Teori Pewarnaan Graf dan Bilangan Kromatik: Pengantar Konsep Dasar (2) Pendahuluan: Mengulang pertanyaan dari sesi sebelumnya tentang pewarnaan peta dan menghubungkannya dengan konsep pewarnaan graf. (3) Definisi Formal Pewarnaan Graf: Penugasan warna pada simpul graf sehingga tidak ada dua simpul bertetangga yang memiliki warna yang sama. Ilustrasi graf sederhana dengan simpul dan sisi. (4) Bilangan Kromatik (χ(G)): Definisi jumlah warna minimum yang dibutuhkan untuk mewarnai graf secara valid. Simbol χ(G). (5) Contoh Graf Standar: Graf Lengkap (K_n): menunjukkan pewarnaan dan bilangan kromatiknya (misalnya K_3 membutuhkan 3 warna). Visualisasi K_3, K_4. (6) Contoh Graf Standar: Graf Siklus (C_n): menunjukkan pewarnaan dan bilangan kromatiknya (C_4 membutuhkan 2 warna, C_5 membutuhkan 3 warna). Visualisasi C_4, C_5. (7) Contoh Graf Standar: Graf Bipartit: definisi dan pewarnaan (selalu 2 warna). (8) Algoritma Welsh-Powell: Langkah-langkah: (1) Hitung derajat setiap simpul. (2) Urutkan simpul berdasarkan derajat menurun. (3) Warnai simpul secara berurutan, menggunakan warna pertama yang tersedia yang tidak bertentangan dengan simpul yang sudah diwarnai. (9) Penerapan Algoritma Welsh-Powell: Ilustrasi langkah demi langkah pada contoh graf sederhana untuk menemukan bilangan kromatik. (10) Miskonsepsi Umum: Pewarnaan graf bukan tentang estetika, melainkan tentang optimasi dan pencegahan konflik, seperti dalam penjadwalan. Contoh konkret dan kosakata yang harus muncul: 'Pewarnaan Simpul' (Vertex Coloring), 'Simpul Bertetangga', 'Bilangan Kromatik' (Chromatic Number), simbol χ(G), Graf Lengkap (K_n), Graf Siklus (C_n), Graf Bipartit, Algoritma Welsh-Powell, 'derajat simpul'. Kaitan dengan bagian lain dari pelajaran: Membangun di atas pengenalan 'Simpul' dan 'Sisi' dari Bagian 1. Menyiapkan Bagian 3 di mana mahasiswa akan menerapkan algoritma pewarnaan secara langsung. Slide Penutup: 'Bagaimana Algoritma Welsh-Powell membantu kita menemukan solusi optimal untuk masalah pewarnaan graf?' — menyiapkan latihan aplikasi di sesi berikutnya.

Lara from Teachy